Bubble Sort

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.

Example

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

Code

        type num_array is array (INTEGER range <>) of integer;
        num: num_array(1..9):=(11,34,26,90,37,58,10,47,36);



        procedure bubble_sort (sort: in out num_array) is

           sorted: BOOLEAN := false;
           last  : INTEGER := sort'LAST;
           temp  : INTEGER;

        begin
  
          while (not (sorted)) loop
             sorted := true;
             for check in range sort'FIRST .. (last-1) loop
                if sort(check) < sort(check+1) then
                   -- swap two elements
                   temp := sort(check);
                   sort(check) := sort(check+1);
                   sort(check+1) := temp;
                   -- wasn't already sorted after all
                   sorted := false;
                end if;
             end loop;
             last := last - 1;
          end loop;

        end bubble_sort;