Java Notes

Bubble Sorts

People like bubble sorts -- could it be the name? One nice aspect of bubble sorts is that they can quit early if the elements are almost sorted.

NOTE: As always, it's better if you don't write your own sorts. Java has better sort methods in java.util.Arrays.sort(...) and java.util.Collections.sort(...). But sorts are excellent practice, and are a technique that all students are expected to understand to some extent.

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.

public static void bubbleSort1(int[] x) {
    int n = x.length;
    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;
            }
        }
    }
}

Bubble Sort -- stop when no exchanges

This version of bubble sort continues making passes over the array as long as there were any exchanges. If the array is already sorted, this sort will stop after only one pass.

public static void bubbleSort2(int[] x) {
    boolean doMore = true;
    while (doMore) {
        doMore = false;  // assume this is last pass over array
        for (int i=0; i<x.length-1; i++) {
            if (x[i] > x[i+1]) {
               // exchange elements
               int temp = x[i];  x[i] = x[i+1];  x[i+1] = temp;
               doMore = true;  // after an exchange, must look again 
            }
        }
    }
}

Bubble Sort -- stop when no exchanges, shorter range each time

This version of bubble sort combines ideas from the previous versions. It stops when there are no more exchanges, and it also sorts a smaller range each time.

public static void bubbleSort3(int[] x) {
    int n = x.length;
    boolean doMore = true;
    while (doMore) {
        n--;
        doMore = false;  // assume this is our last pass over the array
        for (int i=0; i<n; i++) {
            if (x[i] > x[i+1]) {
                // exchange elements
                int temp = x[i];  x[i] = x[i+1];  x[i+1] = temp;
                doMore = true;  // after an exchange, must look again 
            }
        }
    }
}//end method bubbleSort3

Bubble Sort -- Sort only necessary range

After a pass on bubble sort, it's only necessary to sort from just below the first exchange to just after the last exchange, because everything that wasn't exchanged must be in the correct order. This version of bubble sort remembers the lowest and highest locations where there was an exchange, and sorts only that part of the array. Although it is a little more complicated, it is more efficient than the other bubble sorts.

public static void bubbleSort4(int[] x) {
    int newLowest = 0;            // index of first comparison
    int newHighest = x.length-1;  // index of last comparison
  
    while (newLowest < newHighest) {
        int highest = newHighest;
        int lowest  = newLowest;
        newLowest = x.length;    // start higher than any legal index
        for (int i=lowest; i<highest; i++) {
            if (x[i] > x[i+1]) {
               // exchange elements
               int temp = x[i];  x[i] = x[i+1];  x[i+1] = temp;
               if (i<newLowest) {
                   newLowest = i-1;
                   if (newLowest < 0) {
                       newLowest = 0;
                   }
               } else if (i>newHighest) {
                   newHighest = i+1;
               }
            }
        }
    }
}//end method bubbleSort4

Other bubble sorts

Note that the part of the array that is completely sorted grows at only one end of the array. The ability to quit early is not symmetrical. The extreme values move all the way to the end in one direction, but only one place in the other direction. The algorithm can be improved by "bubbling" in opposite directions on alternate passes. This is left as an exercise.