C++ Notes: Algorithms: Bubble Sort - Fixed Number of Passes

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.

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.