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;  //