Computer & Web Solutions

Bubble Sort Logic

To understand bubble sort, think of an air bubble rising in water

To sort N items, N passes are made through the data.

1. The result of the first pass is that the smallest item is in the last location of the array.
2. The result of the second pass is that the second smallest item is in the second last location of the array.
3. etc.
4. After N passes, the entire array is sorted.

The operation in each pass is as follows:

1. First, the values in the first two locations are compared. If necessary the values are exchanged, so that the smaller one is last.
2. Then, the values in the second and third locations are compared. If necessary the values are exchanged, so that again the smaller one is last.
3. This process repeats to the end of the array.
4. In effect, the smaller item bubbles its way towards the top. It keeps on going until either it reaches the top (and the pass ends), or it strikes a smaller item. In that case it stops itself, and gives that smaller item a nudge to start it on its way.

If a complete pass is made without any exchanges being made, the data must already be sorted. This is easily checked. Thus it might be possible to halt the algorithm without going through all N passes.

Algorithm

last := length;
sorted := false;
while not (sorted) loop
    sorted := true; -- assume list sorted
    for check in (1 .. last-1) loop
        if list (check) < list (check+1)
            swap list(check) and list(check+1)
            sorted := false
        end if
    end loop
    last := last - 1;
end loop

Graphical look to the Bubble sort

Basic Code

MyArray(50)
Number 
Count 
'*** Make an array of random numbers ***

CLS
PRINT
PRINT "Initial random array :-"
PRINT

RANDOMIZE TIMER
                                             
FOR Count = 1 TO UBOUND(MyArray)
        Number = (RND * 5000) + 1
        MyArray(Count) = Number
        PRINT MyArray(Count);
NEXT Count

Number = UBOUND(MyArray)

'*** Do the Bubblesort ***

FOR Count = 1 TO Number
        FOR Counter = 1 TO Number
                IF MyArray(Counter) > MyArray(Count) THEN SWAP MyArray(Count), MyArray(Counter)
        NEXT Counter
NEXT Count

'*** Print the sorted array ***

PRINT
PRINT
PRINT "Bubble sorted array :-"
PRINT

FOR Count = 1 TO Number
        PRINT MyArray(Count);
NEXT Count

END