COMP1927 - Bubble Sort

Bubble Sort is a very very basic sort. Each element is compared to the one next to it, and if they are out of order, swapped. The list is traversed in this manner as many times as needed until sorted.

Type

Adaptive (with early exit)
Stable
In-Place

Complexity

Bubble Sort has a worst case of O(n2) (although each traversal the list becomes one element shorter, as the biggest always bubbles to the top and is hence sorted).

It has a best case of O(n), as if the list is already sorted (no swaps are made) it early exits.

(There's actually a more efficient version; cocktail sort where the smallest and biggest element are shifted appropriately each time).

Example

bubble-fig-7.png

Code

void bubbleSort (int array[], int length) {
 
   int temp;
 
   int sorted = FALSE;
   int swapped = FALSE;
 
   // We access i+1, so we need to stop i at one before the end.   
   int lengthToTraverse = length-1; 
   int i;
 
   // While there is an unsorted part of the list   
   while ((lengthToTraverse > 0) && (!sorted)) {
 
      for (i = 0; i < lengthToTraverse; i++) {
         // If they're out of order, swap them
         if (array[i] > array[i+1]) {
            temp = array[i];
            array[i] = array[i+1];
            array[i+1] = temp;
            swapped = TRUE;
         }       
      }
 
      // If no swaps were made, early exit
      if (!swapped) {
         sorted = TRUE;
      }
 
      swapped = FALSE;
      lengthToTraverse--;
   }
 
}