Data Structures/bubble sort

From

---

Revision as of 01:29, 13 January 2009

File:Merge-split-transwiki default.svg

A Wikibookian suggests that this book or chapter be merged into Algorithms. Please discuss whether or not this merge should happen on the [[Template:TALKPAGENAME:Algorithms|discussion page]].

The bubble sort is also known as the ripple sort. The bubble sort is probably the first, reasonably complex module that any beginning programmer has to write. It is a very simple construct which introduces the student to the fundamentals of how sorting works.

A bubble sort makes use of an array and some sort of "swapping" mechanism. Most programming languages have a built-in function to swap elements of an array. Even if a swapping function does not exist, only a couple of extra lines of code are required to store one array element in a temporary field in order to swap a second element into its place. Then the first element is moved out of the temporary field and back into the array at the second element's position.

Here is a simple example of how a bubble sort works: Suppose you have a row of children's toy blocks with letters on them. They are in random order and you wish to arrange them in alphabetical order from left to right.

Step 1. Begin with the first block. In this case, the letter G. (Fig. 1.)

File:Bubble01.png
Fig. 1

Step 2. Look at the block just to the right of it.

Step 3. If the block to the right should come before the block on the left, swap them so that they are in order (Fig. 2.)

File:Bubble02.png
Fig. 2

If you were doing this by hand, you might just pick the blocks to be moved with one in each hand and cross your arms to swap them. Or you might move the first one out of it's position temporarily, move the second one in its place, them move the first one to the now empty position (this is the difference between having a single function to do the swap, or writing some code to do it).

Step 4. Compare the next block in line with the first, and repeat step 3. Do this until you run out of blocks. Then begin step one again with the second block. (Fig. 3,4,5,6)

File:Bubble03.png
Fig. 3 - Pass #2 File:Bubble04.png
Fig. 4 - Pass #3 File:Bubble05.png
Fig. 5 - Pass #4 File:Bubble06.png
Fig. 6 - Completed Sort

Why is it called a bubble sort?

The bubble sort gets its name because elements tend to move up into the correct order like bubbles rising to the surface. ←×

Code example in Quick Basic:

CLS

DIM NameArray$(1000)

i = 0

' Seed read ...
READ Name$

' Loop through and read names in data ...
DO WHILE Name$ <> "*EOD"
      i = i + 1
      NameArray$(i) = Name$
      READ Name$
LOOP

' The value of i is now the number of names in the array ...
ArraySize = i


' Bubble (or ripple) sort ...
FOR i = 1 TO ArraySize - 1
  FOR j = 1 TO ArraySize - 1
      IF NameArray$(j) > NameArray$(j + 1) THEN
         SWAP NameArray$(j), NameArray$(j + 1)
      END IF
  NEXT j
NEXT i

' Print out the sorted results ...
FOR i = 1 TO ArraySize
        PRINT NameArray$(i)
NEXT i

DATA Crowe,
DATA Adams,
DATA Zimmerman,
DATA Goodhead,
DATA Smith,
DATA Jones,
DATA *EOD

Code example in C:

/**
 * An example of bubble sort written in C.
 * Author: Nebu Pookins (nebu@gta.igs.net)
 *
 * I've tried to keep the "logic" of this program as close to the
 * QuickBasic example as possible.
 */

int main(void) {
  const int numberOfElements = 6;
  char arrayOfCharsToSort[numberOfElements];
  //Fill in the array with the unsorted data.
  arrayOfCharsToSort[0] = 'C';
  arrayOfCharsToSort[1] = 'A';
  arrayOfCharsToSort[2] = 'Z';
  arrayOfCharsToSort[3] = 'G';
  arrayOfCharsToSort[4] = 'S';
  arrayOfCharsToSort[5] = 'J';
  
  //Start sorting
  int i, j; //variables used for for loops.
  char temporaryCharHolder; //used to swap values of two array entries
  for (i = 0; i < numberOfElements; i++) {
    for (j = 0; j < numberOfElements - 1; j++) {
      if (arrayOfCharsToSort[j] > arrayOfCharsToSort[j + 1]) {
        temporaryCharHolder = arrayOfCharsToSort[j];
        arrayOfCharsToSort[j] = arrayOfCharsToSort[j + 1];
        arrayOfCharsToSort[j + 1] = temporaryCharHolder;
      }
    }
  }
  
  //Print out the sorted results
  for (i = 0; i < numberOfElements; i++) {
    printf("%c\n", arrayOfCharsToSort[i]);
  }
  
  return 0;
}

[[File:File:Example.jpg

]]