Chapter 3: Sorting Algorithms

Sorting is the process of rearranging a sequence of objects so as to put them in some logical order. For example, your credit card bill presents transactions in order by date, and you put your books in order on your bookshelf alphabetically by author and title. Sorting is a fundamental operation in computer science, and it plays a critical role in many applications. There are a variety of classic sorting algorithms that embody different approaches to this problem.

In this chapter, we consider several classic sorting methods and an important data structure known as the priority queue. We begin with a discussion of several elementary sorting methods, including selection sort, insertion sort, and shellsort. These methods are appropriately used in many applications, but for large problems, we turn to mergesort and quicksort, two recursive sorting algorithms that can be used to sort huge numbers of items. We conclude with a discussion of priority queues and their use in sorting and other applications.

Elementary Sorts

The simplest sorting algorithms perform the following operations:

Selection sort: Find the smallest item and exchange it with the first entry, then find the second smallest item and exchange it with the second entry, etc.
Insertion sort: Take each item in turn and insert it into the appropriate position among those already considered (keeping them sorted).

These operations mirror how humans typically perform sorting tasks and are effective for small problem sizes. However, they do not scale well and become impractical for sorting large arrays.

Selection Sort

Selection sort is a simple sorting algorithm that works as follows: First, find the smallest item in the array and exchange it with the first entry (itself if the first entry is already the smallest). Then, find the next smallest item and exchange it with the second entry. Continue in this way until the entire array is sorted.

The inner loop of selection sort is used to find the minimum element in the unsorted subarray a[i..N-1]. The index of the minimum element is stored in min. Then, a[i] is exchanged with a[min], which puts the minimum element in its final position. As the index i travels from left to right, the elements to its left are in sorted order in the array and will not be touched again.

Here is an implementation of selection sort in Java:

public static void selectionSort(Comparable[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
        int min = i;
        for (int j = i+1; j < N; j++) {
            if (less(a[j], a[min])) min = j;
        }
        exch(a, i, min);
    }
}

Selection sort uses ~N^2/2 compares and N exchanges to sort an array of length N. The running time is insensitive to input - it takes about as long to run selection sort for an array that is already in order or for an array with all keys equal as it does for a randomly-ordered array.

Insertion Sort

Insertion sort is another simple sorting algorithm that works by building the final sorted array one item at a time. It is much less efficient on large arrays than more advanced algorithms such as quicksort, heapsort, or merge sort, but it has some advantages:

It is efficient for small data sets.
It is more efficient in practice than selection sort.
It is stable; i.e., it does not change the relative order of elements with equal keys.
It is in-place; i.e., only requires a constant amount O(1) of additional memory space.
It is online; i.e., can sort a list as it receives it.

Here is an implementation of insertion sort in Java:

public static void insertionSort(Comparable[] a) {
    int N = a.length;
    for (int i = 1; i < N; i++) {
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            exch(a, j, j-1);
        }
    }
}

The inner loop of insertion sort moves larger elements one position to the right, making room to insert the current element. The running time of insertion sort depends on the initial order of the items in the input. For example, if the array is large and its entries are already in order (or nearly in order), then insertion sort is much, much faster than if the entries are randomly ordered or in reverse order.

Shellsort

Shellsort is a simple extension of insertion sort that gains speed by allowing exchanges of array entries that are far apart, to produce partially sorted arrays that can be efficiently sorted, eventually by insertion sort.

The idea is to rearrange the array to give it the property that taking every hth entry (starting anywhere) yields a sorted subsequence. Such an array is said to be h-sorted. Put another way, an h-sorted array is h independent sorted subsequences, interleaved together. By h-sorting for some large values of h, we can move items in the array long distances and thus make it easier to h-sort for smaller values of h. Using such a procedure for any sequence of values of h that ends in 1 will produce a sorted array: that is shellsort.

Here is an implementation of shellsort in Java:

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;
    private int N;
    
    public MaxPQ(int capacity) {
        pq = (Key[]) new Comparable[capacity+1];
    }
   
    public boolean isEmpty() {
        return N == 0;
    }
   
    public void insert(Key key) {
        pq[++N] = key;
        swim(N);
    }
   
    public Key delMax() {
        Key max = pq[1];
        exch(1, N--);
        sink(1);
        pq[N+1] = null;
        return max;
    }
   
    private void swim(int k) {
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }
   
    private void sink(int k) {
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
   
    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }
 
    private void exch(int i, int j) {
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
}

This code implements a max-oriented binary heap using an array pq to store the heap-ordered complete binary tree. The insert() and delMax() operations maintain the heap invariant by using the swim() and sink() helper methods to restore the heap order by exchanging keys with a parent larger than a child or a child larger than its parent respectively.

Stopwatch

A more useful abstract data type is a simple and effective abstraction for a stopwatch, shown on the facing page. To use it, create a Stopwatch object when you want to start the timer, then use the elapsedTime() method to get the elapsed time in seconds since the object was created. The implementation uses Java's System.currentTimeMillis() to get the current time in milliseconds since midnight January 1, 1970.

The instance variable start records the time the stopwatch was created, and elapsedTime() uses start to compute the elapsed time. The client shown is typical: it does some computation and uses a Stopwatch to time how long the computation takes. The Stopwatch data type is an effective abstraction because it separates the concept of a stopwatch (the interface) from the implementation (using Java's System.currentTimeMillis()). This separation of interface and implementation is a fundamental characteristic of abstract data types that we will see in every ADT throughout the book.

Summary

Abstract data types are an essential element of object-oriented programming that are widely used in modern programming. In this section, we have seen:

Defining an abstract data type as a Java class, with instance variables to define the data-type values and instance methods to implement the operations on those values.
Developing multiple implementations of the same API, using different representations of the same abstract data type.
Distinguishing APIs, clients, and implementations of an abstract data type.
Designing APIs for abstract data types.
Developing clients and test clients for use in testing and debugging.
Reasoning about the correctness of an abstract data type implementation, using assertions.
Comparing the performance of different implementations of the same API.

These activities are an essential part of the development of any Java program. Every Java program that we write will involve the use of abstract data types from libraries; many will involve the development of new abstract data types. In the next section, we consider three fundamental abstract data types that are essential components in a vast number of programs, and in Section 1.4 we consider the process of analyzing the performance characteristics of implementations in detail.

Chapter 2 Algorithms Fundamentals Chapter 4 Searching Algorithms