C++ Notes: Algorithms: Bubble Sorts

Bubble sort compares two values next to each other and exchanges them if necessary to put them in the correct order. There are many variations on bubble sort, but they all examine adjacent pairs.

Performance

Bubble sorts are O(N²) on the average (and worst), but have O(N) best case performance. The one efficient aspect of bubble sorts is that they can quit early if the elements are almost sorted.

If you need a faster sort, use Quicksort (best O(log N), average O(log N), worst O(N²)) or heap sort (best, average, and worst are all O(log N)) in the library.

Bubble Sort -- fixed number of passes

This version of bubble sort makes a fixed number of passes (length of the array - 1). Each inner loop is one shorter than the previous one because the largest elements are being moved to the end of the array.

void bubbleSort1(int x[], int n) {
   for (int pass=1; pass < n; pass++) {  // count how many times
       // This next loop becomes shorter and shorter
       for (int i=0; i < n-pass; i++) {
           if (x[i] > x[i+1]) {
               // exchange elements
               int temp = x[i]; x[i] = x[i+1]; x[i+1] = temp;
           }
       }
   }
}

Because this version of the bubble sort always makes n-1 passes over the array, it can't stop early if the array is already sorted. See More Bubble Sorts for improvements.

Students like bubble sorts -- could it be the name or the intuitive algorithm? Instructors also like bubble sorts, perhaps for the many interesting programming variations. However, the sad truth is that they often aren't very efficient. They should only be used with small arrays or almost sorted data.