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).

If the amount of data  is small enough to be held in memory then an internal sort may be used.

 
 

Bubble sort

Example :

23 12 34 17 21 18

Start from the left and compare each pair of numbers. If the smallest is on the left, then leave them. If not...swap them over.

Move on to compare the next pair of numbers.

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 right...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 not set.

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)