Thread: Bubble Sort

  1. #1
    Unregistered
    Guest

    Talking Bubble Sort

    Hi can someone plz explain the basics of a bubble sort thank you

  2. #2
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    you need two loops

    one for the number of passes.
    one inside (x) to do one pass
    {
    is array[x]>array[x+1] if so then swap them else leave them be.
    }

    number of passes is related to array size-1
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    I will be using the following sequence of numbers...

    3 6 8 2 9 0 1 4 7 5

    The basic action we're going to is compare two numbers, and if they're out of order, we'll switch them. We're going to do this to every pair of numbers... here's basically how the process goes
    Code:
    3 6 8 2 9 0 1 4
    3 6 8 2 9 0 1 4 (3 & 6, no change)
    3 6 8 2 9 0 1 4 (6 & 8, no change)
    3 6 2 8 9 0 1 4 (8 & 2, swapped)
    3 6 2 8 9 0 1 4  (8 & 9, no change)
    3 6 2 8 0 9 1 4  (9 & 0, swapped)
    3 6 2 8 0 1 9 4  (9 & 1, swapped)
    3 6 2 8 0 1 4 9 (9 & 4, swapped)
    7 steps for an awway of 8 elements... Notice that when we were running down the list with this process, we carried the largest number we had yet encountered with us...we started with the 6, picked up the 8, got the 9 after that, and carried the 9 untill the end. So we end up with the largest number, 9, at the end of the list. The code for this process is...
    Code:
    void runThroughList (int a[], int n)
    {
     int i, temp;
     for (i = 0; i < n - 1; i++)
     {
      if (a[i] > a[i + 1])
      {
       // I will refer to the following 3 lines as the swap routine.
       temp = a[i];
       a[i] = a[i + 1];
       a[i + 1] = temp;
      }
     }
     return;
    }
    Now if we could just put the numbers before the 9 in order, then we'd have a sorted list, so we'll do the bubble sort on this part of the array...
    3 6 2 8 0 1 4 (9)

    So let's look what happens when we keep doing this sort on the left-over part of the array...
    3 6 8 2 9 0 1 4
    3 6 2 8 0 1 4 (9)
    3 2 6 0 1 4 (8) (9)
    2 3 0 1 4 (6) (8) (9)
    2 0 1 3 (4) (6) (8) (9)
    0 1 2 (3) (4) (6) (8) (9)
    0 1 (2) (3) (4) (6) (8) (9)
    0 (1) (2) (3) (4) (6) (8) (9)
    (0) (1) (2) (3) (4) (6) (8) (9)
    So, we just have to perform this sort on succesively smaller runs of the array. The code would look like this...
    Code:
    void bubbleSort (int a[], int n)
    {
     int i;
     for (i = n; i > 0; i--)
     {
      runThroughList (int a[], int n);
     }
     return;
    }
    For the sake of efficiency however, we don't use a wrapper function for runThroughList. Notice that it really doesn't need it's own function. The only problem is that it needs it's own local variable for it's cound, and temp. We won't use i as the variable for it, since the bubbleSort function already has a variable i. We instead use j.
    Code:
    void bubbleSort (int a[], int n)
    {
     int i, j, temp;
     for (i = n; i > 0; i--)
     {
      for (j = 0; j < i - 1; j++)
      {
       if (a[j] > a[j + 1])
       {
        temp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = temp;
       }
      }
     }
     return;
    }
    The runTrhoughList function is practically copy and pasted. The only changes are that it's instances of 'i' were changed to 'j', and instead of n - 1 as the stopping condition, we had to use i - 1, since we no longer had i being passed to the function under the name 'n'.


    An interesting improvement to the bubbleSort function is to make it recognize if the list is sorted on one of it's runs. Notice that in my example, the function could have stopped at
    0 1 2 (3) (4) (6) (8) (9)
    if it were able to realise this array was already sorted.

    Hint: if a list is sorted, then there will be 0 swap routines in runThroughList.
    Callou collei we'll code the way
    Of prime numbers and pings!

  4. #4
    Registered User
    Join Date
    Oct 2001
    Posts
    197

    Use the Quicksort algorithm!

    The Quicksort is much faster if you have enough memory!!

    klausi
    When I close my eyes nobody can see me...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. bubble sort not working... wats d prob?
    By Huskar in forum C Programming
    Replies: 8
    Last Post: 03-31-2009, 11:59 PM
  2. My bubble sort only sorts once
    By Muller in forum C Programming
    Replies: 8
    Last Post: 03-27-2009, 04:36 PM
  3. Bubble Sort... which type?
    By gflores in forum C++ Programming
    Replies: 8
    Last Post: 08-15-2004, 04:48 AM
  4. Bubble Sort, Qucik Sort
    By insomniak in forum C Programming
    Replies: 2
    Last Post: 03-15-2003, 04:54 PM
  5. Help with Bi-Directional Bubble Sort in C
    By cunninglinguist in forum C Programming
    Replies: 0
    Last Post: 04-19-2002, 02:32 PM