Jump to content
  • Advertisement
  • 07/16/99 05:58 PM
    Sign in to follow this  

    Bubble Sort

    General and Gameplay Programming

    {                                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;
             ok  : boolean;
             i   : integer;
             i := 1;
               ok := a[i+1] >= a ;
               i := i+1;
             until i = N or not ok;
             is_sorted := ok;
    {     -----------------------------------------------------------------
    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;
             ok          : boolean;
             i           : integer;
               ok := true;
               for i := 1 to n-1 do
                 if a > a[i+1] then
                     ok := false
             until ok
    {     -----------------------------------------------------------------
    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.

      Report Article
    Sign in to follow this  

    User Feedback

    There are no comments to display.

    Create an account or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!