Home  Back Topics CD Orders  INDEX 
Bubble Sort

Searching for Data

If you had to find a name in a very long list...is it quicker if the list is jumbled up or sorted into alphabetical order? Well the answer is obvious...and gives us the reason why sorting data is useful.

To sort data  is to place the data  in order (numerical or alphabetic)

Some sorting algorithms work faster if the data is completely jumbled, and some work faster if the data is 'nearly sorted' - the data may have been sorted before, but new data has been added onto the end.

 
 

Bubble sort

Example : Sort the number from smallest to largest.

23 12 34 17 21 18

Start from the left and compare each pair of numbers. If the smallest is on the left, leave them. If they are in the wrong order...swap them over.

C = Number of comparisons
E = number of exchanges (swaps)

After First Pass : 12 23 17 21 18 34 C=5 E=4

(after the first pass the largest number should be at the end...so on the next pass, we need one less comparison)

After 2nd Pass : 12 17 21 18 23 34 C=4 E=3

(the last two numbers are in the correct position)

After 3rd Pass : 12 17 18 21 23 34 C=3 E=1
After 4th Pass : 12 17 18 21 23 34 C=2 E=0

Once a pass produces no exchanges then the file is sorted and the algorithm can stop.

Notes :

The bubble sort is quick for 'nearly sorted' files. For example, files which have been recently sorted but may have had a few more records added at the end.

Pseudocode :

repeat
set a flag to False
for each pair of keys
         if the keys are in the wrong order then
               swap the keys
               set the flag to True
         end if
next pair
until flag is False.

A more detailed (and more helpful) pseudo-code :
Assume records are held in an array key[1..n]

Set n to number of records to be sorted
repeat
  flag = false;
  for counter = 1 to n-1 do
    if key[counter] > key[counter+1] then  
      swap the records;
      set flag = true;
    end if  
  end do    
  n = n-1;    
until flag = false or n=1