Next: None. Up: Computational complexity. Previous: Big-O.

Sorting techniques

As you'll quickly learn, sorting an array is one of computer science's favorite topics. It's highly useful, simple, and nonetheless interesting. No fewer than four of the required classes for a major address the topic (150, 160, 200, 338).

Selection sort

There are lots of techniques. Personally, my favorite technique - just because it's the simplest to understand and implement - is selection sort. The selection sort algorithm involves finding the smallest element of the array, and swapping it with the first element. Then finding the smallest element after the first element, and swapping it with the second element. Then finding the smallest element after the second element and swapping it with the third element, etc. Once you're done, the array is sorted.

public class SelectionSort {
    public static void sort(int[] elts) {
        for(int i = 0; i < elts.length; i++) {
            int min = i; // min will be index of minimum starting at i
            for(int j = i + 1; j < elts.length; j++) {
                if(elts[j] < elts[min]) min = j;
            }
            if(i != min) { // swap elts[i] and elts[min]
                int temp = elts[i];
                elts[i] = elts[min];
                elts[min] = temp;
            }
        }
    }
}

Insertion sort

Insertion sort is a different algorithm, which you may remember from a CSCI 150 lab: In insertion sort, you begin with the first element, which by itself is already sorted. But then you insert the second element into the list (possibly swapping the first and second elements). Then you insert the third element into the first two elements where it fits.

public class InsertionSort {
    public static void sort(int[] elts) {
        for(int i = 1; i < elts.length; i++) {
            int k = elts[i]; // store element i in k
            int j;
            for(j = i - 1; j >= 0 && elts[j] > k; j--) {
                elts[j + 1] = elts[j]; // shift elts[j] up one slot
            }
            elts[j + 1] = k; // place k into vacated slot
        }
    }
}

(Notice the use of the short-circuit property of && in the condition for the for loop: We test whether j >= 0 first, and then we test whether elts[j] > k. This order is important. If we tested whether elts[j] > k first, then it might happen that j was -1, in which case this would throw an ArrayIndexOutOfBoundsException.)

Although insertion sort and selection sort both consume O(n²) time, insertion sort is considered to be faster, since it at least sometimes does better. For example, if somehow we knew the array was already sorted, insertion sort would only take O(n) time. Of course, if we knew it were already sorted, why would we call it? But insertion sort also does well if the list is almost sorted.

Given these two sorting techniques, you might be inclined to give up: Is there any hope for doing better than O(n²)? It turns out there is, but that's a topic for later.

Next: None. Up: Computational complexity. Previous: Big-O.