Bubble Sort

{                                Bubble Sort

Bubble Sort is an elementary sorting algorithm. It is so inefficient that
it should never be used in practice. What makes it inefficient is the
excessive number of exchanges that it performs. Much time is wasted by
needlessly moving data in memory. Good alternatives, when seeking a simple,
easy-to-implement sorting algorithm, for a relatively small number of
values, include: Selection Sort, Insertion Sort, and Shell Sort.

A good way to begin thinking about sorting algorithms is to ask: How can we
check whether an array, a[ ], is already sorted in increasing order? One
easy way would be to scan the array, checking that adjacent pairs were in
the proper order. As soon as we found a single pair out of order, we could
stop, and report the error. On the other hand, if we manage to scan through
the whole array and each pair was in order, then the entire array must be
sorted. Here's a Pascal function that does exactly that.

     -----------------------------------------------------------------}

     function is_sorted : boolean;
       var
         ok  : boolean;
         i   : integer;
       begin
         i := 1;
         repeat
           ok := a[i+1] >= a[i] ;
           i := i+1;
         until i = N or not ok;
         is_sorted := ok;
       end;

{     -----------------------------------------------------------------

Verifying that an array is already sorted requires just N-1 comparisons
(and fewer if we find that it isn't sorted.) With a few modifications, this
function can transformed into a sorting procedure that works by
interchanging any out-of-order pairs that are found.

Bubble Sort works by repeatedly scanning the array, checking adjacent pairs
of values to see if they are in the proper order. In the implementation
below, the boolean value ok is used to indicate whether the array is "ok",
meaning "in sorted order". Whenever a pair of values is found to be out of
order, they are interchanged and ok is set to "false", to indicate the
array must be scanned again. This procedure will eventually end when the
array is scanned and all adjacent values are found to be in their proper
sorted order.

Here is a procedure that implements Bubble Sort, assuming a global array a[
] with n elements, and a procedure called swap( ).

     -----------------------------------------------------------------}

     procedure bubble_sort;
       var
         ok          : boolean;
         i           : integer;
       begin
         repeat
           ok := true;
           for i := 1 to n-1 do
             if a[i] > a[i+1] then
               begin
                 swap(a[i],a[i+1]);
                 ok := false
               end
         until ok
       end;

{     -----------------------------------------------------------------

This implementation of Bubble Sort requires about N2 comparisons and about
N2 exchanges in the worst case, which occurs when the input data are sorted
in reverse order. The best case scenario for this implementation occurs
when the input data are already sorted in the proper order. In this case,
one pass over the array (with just N comparisons and 0 exchanges) confirms
the array is sorted. The amount of work (comparisons/exchanges) done by
Bubble Sort in average case is difficult to analyze, but it is quite close
to the work needed in the worst case.

---------------------------------------------------------------------------}
Discuss this article in the forums
Date this article was posted to GameDev.net: 7/16/1999
(Note that this date does not necessarily correspond to the date the article was written)
See Also:
Sorting Algorithms