Home | Gaming | Programming | Play Online | Contact | Keyword Query
Games++ Games & Game Programming

GAMES++
Games++ Home
Games++ Gaming
Games++ Programming
Beta Testing Games
Free Online Games
Hints & Cheats

BROWSER UTILITIES
E-mail This Page
Add to Favorites

SITE SEARCH

Web Games++

AFFILIATES
Cheat Codes
Trickster Wiki
Game Ratings
Gameboy Cheats
PlayStation Cheats
BlackBerry Games
Photoshop Tutorials
Illustrator Tutorials
ImageReady Tutorials

ADVERTISEMENT

Bubble Sort Algorithm

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.

Copyright © 1998-2007, Games++ All rights reserved. | Privacy Policy