Sorting

Demos First

Videos...

• Sorting out Sorting from the University of Toronto

and (interactive) applets

• http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
• http://cg.scs.carleton.ca/~morin/misc/sortalg/

Classification of Algorithms

Actually you can classify sorting algorithms many ways

• Stable vs. non-stable
• By time or space complexity
• Whether it works by comparing items or not

Here are some characteristics of various sorting algorithms, adapted (er, taken) from the excellent Wikipedia page on sorting. (n = number of items to sort, k = number of distinct keys.)

There are probably hundereds of other sorting algorithms, including some extremely inefficient and evil ones.

Sorting in Java

In Java one would usually use Arrays.sort(). There are two versions

Arrays.sort(array)

Arrays.sort(array, comparator)

The array can be an array of Objects or an array of one of the primitive types. If the array contains primitives or objects of a class implementing Comparable you can use the simple form of Arrays.sort(). Otherwise a comparator is required.

package edu.lmu.cs.sorting;

import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Date;

import javax.swing.JPanel;

/**
 * A throwaway example class showing how to use the built-in sorting
 * methods in java.util.Arrays.
 */
public class BuiltInSortingDemo extends JPanel {

    private static class Employee {
        String id = "";
        String name = "";
        String address = "";
        String phone = "";
        Date birthday = new Date();
        BigDecimal salary = new BigDecimal(0);
    }

    static Comparator<Employee> increasingName = new Comparator<Employee>() {
        public int compare(Employee e1, Employee e2) {
            return e1.name.compareTo(e2.name);
        }
    };

    static Comparator<Employee> decreasingSalary = new Comparator<Employee>() {
        public int compare(Employee e1, Employee e2) {
            return e2.salary.compareTo(e1.salary);
        }
    };

    static Employee alice = new Employee();
    static Employee bob = new Employee();

    public static void main(String[] args) {
        Arrays.sort(new int[]{3, 5, 1, 2, 4});
        Arrays.sort(new char[]{'d', 'q', 'a'});
        Arrays.sort(new byte[]{5, -3});
        Arrays.sort(new short[]{322, 98, -11111});
        Arrays.sort(new long[]{234234234, 23435112, 4214124214L});
        Arrays.sort(new float[]{4.3F});
        Arrays.sort(new double[]{9.9E-7, Double.MAX_VALUE});
        Arrays.sort(new String[]{"abc", "abb", "dog"});
        Arrays.sort(new Date[]{});
        // Will throw exception --> Arrays.sort(new Employee[]{bob, alice});

        // Comparators are necessary for Employee objects since the
        // Employee class does not implement Comparable.
        Arrays.sort(new Employee[]{bob, alice}, increasingName);
        Arrays.sort(new Employee[]{bob, alice}, decreasingSalary);
    }

}

Some Algorithms

Okay, big deal, Arrays.sort() exists. But you still need to study sorting algorithms and implement some yourself because

• There is no one best algorithm — different algorithms work best in different situations, and a canned library routine might not work in your particular situation.
• You might find yourself programming in an environment without a sort method in a library.

Selection Sort

First, find the smallest element and swap it with the first. Sort the rest of the list the same way.

for i in 0 .. n-2
    small := i
    for j in i+1 .. n-1
        if (a[j] < a[small]) small := j
    swap(a[i], a[small])

Sample trace:

    20 54 16 36 99 11 74 88
    11 54 16 36 99 20 74 88
    11 16 54 36 99 20 74 88
    11 16 20 36 99 54 74 88
    11 16 20 36 54 99 74 88
    11 16 20 36 54 99 74 88
    11 16 20 36 54 74 99 88
    11 16 20 36 54 74 88 99

Notes:

• Quadratic run time
• No swapping in inner loop
• After pass k, the first k elements are in their final absolute positions

Insertion Sort

For the 2nd, 3rd, 4th, etc. element: slide backwards into proper relative sorted position.

for i in 1 .. n-1
    current := a[i]
    j := i
    while (j > 0 and current < a[j-1])
        a[j] := a[j-1]
        j--
    a[j] = current

Sample trace:

    20 54 16 36 99 11 74 88
    20 54 16 36 99 11 74 88
    16 20 54 36 99 11 74 88
    16 20 36 54 99 11 74 88
    16 20 36 54 99 11 74 88
    11 16 20 36 54 99 74 88
    11 16 20 36 54 74 99 88
    11 16 20 36 54 74 88 99

Notes

• Quadratic run-time on average (though linear if already sorted)
• After pass k, the first k+1 elements are in relative sorted order
• This is the way most people would sort a hand of cards
• In practice, does far fewer compares than selection sort
• But has moves in the inner loop
• If data sorted, or nearly sorted, this algorithm shines
• If data is reversed, this algorithm is worst
• Better than selection sort if moves are cheap; worse if expensive.

Bubble Sort

Systematically examine all pairs of adjacent elements, swapping them when they are out of order.

for i in 0 .. n-2
    for j in i .. n-1
        if (a[j] > a[j+1]) swap(a[j], a[j+1])

Ack, that examines every pair of elements. We need to stop when we make a pass that doesn't swap anything.

for i in 0 .. n-2
    swapped := false
    for j in i .. n-1
        if (a[j] > a[j+1])
            swap(a[j], a[j+1])
            swapped := true
    return if not swapped

Notes

• Exchanges only adjacent elements, which is really slow
• Doesn't need a temporary variable; just swap.
• The swapped flag is important because in practice you often find yourself working on data that is "nearly" sorted.
• Large elements near the beginning of the array (rabbits) move quickly to the other end, but small elements near the end (turtles) bubble up to the front very, very slowly.
• Bubblesort basically sucks: "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems." (D. Knuth)

Cocktail Sort

This is a bidirectional bubble sort. Also called Shaker Sort or Shuttle Sort.

Shell Sort

Multiple-pass insertion-sort variant in which items are sifted more than one location at a time at first. The intervals decrease at each pass until they finally get down to one.

Read Sedgewick's short paper on the complexity of Shellsort.

Tree Sort

For each item in the array, add it to a binary search tree. Traverse the tree inorder, writing each item back into the array.

for x in a
    insert x into binary search tree T
refill a by traversing T inorder

Notes

• Will have Θ(n²) worst-case complexity unless you use a tree that can balance itself (like a Red-Black) tree, in which case you get the Θ(n log n).
• Needs lots of extra space

Quick Sort

Partition the array so one of the elements is in its final position with smaller elements to its left and larger ones to its right, then (recursively) sort each side.

Notes

• Fastest known comparison-based sort on average
• Has Θ(n²) worst-case complexity, so is not suitable as a service to sort user input where users cannot be trusted.
• Choice of pivot is crucial -- the median would be the best choice but computing it is WAY too expensive!
• Common choice is median of the first, middle and last elements (called the median-of-three)
• However, an attacker can still compute a median-of-three killer sequence
• One way to avoid this is to choose the pivot at random, but median-of-three is still faster....
• A common approach is to stop recursing when sublists get small and switch algorithms. Usually the "stopper" was insertion sort and "small" was a constant size like 10 or 15.
• David Musser's Introsort is better though: it switches to heapsort when the algorithm detects the partitioning is tending toward the nasty quadratic behavior.

Heap Sort

First rearrange the array into a heap by sifting up each element in the latter half of the array one at a time. Then for each element starting at the beginning, sift it down. Voila!

Merge Sort

Recursively: split the list in half, sort each half, then merge the sorted halves together.

Sample trace:

    20 54 16 36 99 11 74 88
    20 54 16 36 11 99 74 88
    16 20 36 54 11 74 88 99
    11 16 20 36 54 74 88 99

Notes

• Pretty easy to see that this is Θ(n log n)
• Amenable to parallelism
• Basic algorithm requires Θ(n) space, but there does exist an in-place variant.

Bucket Sort

Partition the items into buckets. Sort each bucket. Read items out of buckets into final array.

Counting Sort

This one only works when the items to be sorted have fairly small integer keys. Set up an array called frequency whose indices are the range of the values you have to sort. Fill it with zeros. Go through the array you want to sort, incrementing the frequenccy array incrementing the count for each item you see. Then you can "read" out the sorted array from the frequencies. (Details in the code below.)

Radix Sort

This one only works when the items can be expressed as strings of bits, digits, characters, whatever — and these symbols are ordered. The algorithm is to repeatedly place in buckets (labeled with the symbols) from the least significant symbol to the most significant.

Example with decimal integers:

Input sequence is 759, 43, 989, 6, 206, 855, 209, 903, 102, 199, 721, 188, 5. First place in buckets on least significant digit.

    0:
    1:    721
    2:    102
    3:    043,903
    4:
    5:    855,005
    6:    006,206
    7:
    8:    188
    9:    759,989,209,199

The go through the buckets in order, writing into buckets based on the second digit

    0:    102,903,005,006,206,209
    1:
    2:    721
    3:
    4:    043
    5:    855,759
    6:
    7:
    8:    188,989,
    9:    199

The go through the buckets in order, writing into buckets based on the first digit

    0:    005,006,043
    1:    102,188,199
    2:    206,209
    3:
    4:
    5:
    6:
    7:    721,759
    8:    855
    9:    903,989

Now just read them out in order. Note that this is easy for binary numbers and strings, too.

An Animated Sort Application

package edu.lmu.cs.sorting;

import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.event.ActionEvent;
import java.util.Arrays;
import java.util.Random;

import javax.swing.*;

/**
 * A class containing a number of classic sorting algorithms,
 * implemented from scratch.  The algorithms each operate on arrays
 * of ints only, and are animated.
 */
public class Sorter extends JPanel {

    private static Random randomizer = new Random();
    private static final int ARRAY_LENGTH = 600;
    private static final int MAX_VALUE = 400;
    private final int[] array = new int[ARRAY_LENGTH];
    private transient boolean shouldStop = false;

    /**
     * Swaps a[i] and a[j].
     */
    private void swap(int[] a, int i, int j) {
        int old = a[i];
        a[i] = a[j];
        a[j] = old;
    }

    /**
     * Fills an array with random values between 0 and MAX_VALUE.
     */
    private void reload(int[] a) {
        for (int i = 0; i < a.length; i++) {
            a[i] = randomizer.nextInt(MAX_VALUE);
        }
    }

    /**
     * Sorts an array using Selection Sort.  The algorithm is to first
     * put the smallest item in the first position, then the next
     * smallest in the second position, and so on.
     */
    public void selectionSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int small = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[small]) small = j;
                PAUSE();
            }
            swap(a, i, small);
        }
    }

    /**
     * Sorts an array using Insertion Sort.  The algorithm is to first
     * slide the second element back as far as it should go, then slide
     * the third back, and so on.
     */
    public void insertionSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int current = a[i];
            int j = i;
            for (; j > 0 && current < a[j-1]; j--) {
                a[j] = a[j-1];
                PAUSE();
            }
            a[j] = current;
        }
    }

    /**
     * Sorts an array using Bubble Sort.
     */
    public void bubbleSort(int[] a) {
        for (int i = a.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (a[j] > a[j + 1]) swap(a, j, j + 1);
                PAUSE();
            }
        }
    }

    /**
     * Sorts an array using Gnome Sort.
     */
    public void gnomeSort(int[] a) {
        for (int i = 0; i < a.length;) {
            PAUSE();
            if (i == 0 || a[i-1] <= a[i]) {
                i++;
            } else {
                swap(a, i, i - 1);
                i--;
            }
        }
    }

    /**
     * Sorts an array using Shell Sort.  This is a lousy Shell Sort.
     * I need to make a new one.
     */
    public void shellSort(int[] a) {
        int distance = a.length / 2;
        while (distance > 0) {
            boolean changed = false;
            for (int i = 0; i < a.length - distance; i++) {
                if (a[i] > a[i + distance]) {
                    swap(a, i, i + distance);
                    changed = true;
                }
                PAUSE();
            }
            if (!changed) distance /= 2;
        }
    }

    /**
     * Sorts an array using Quick Sort.  This version of quicksort uses
     * the leftmost item as the pivot, but since this gives disastrous
     * performance on sorted and nearly sorted arrays, we scramble the
     * array first.
     */
    public void quickSort(int[] a) {
        // First shuffle (permute) the array
        for (int i = 0; i < a.length; i++) {
            swap(a, i, randomizer.nextInt(ARRAY_LENGTH));
        }

        // Call the recursive helper
        quickSort(a, 0, a.length - 1);
    }

    private void quickSort(int[] a, int left, int right) {
        if (left < right) {
            int i = left;
            int j = right;
            while (i < j) {
                while (a[j] > a[left]) {j--; PAUSE();}
                while (i < j && a[i] <= a[left]) {i++; PAUSE();}
                if (i < j) swap(a, i, j);
            }
            swap(a, left, j);
            quickSort(a, left, j-1);
            quickSort(a, j+1, right);
        }
    }

    /**
     * Sorts an array using Heap Sort.
     */
    public void heapSort(int[] a) {
        // Phase 1: make a heap by sifting down all non-leaf
        // elements, one after another, starting with the last
        // non-leaf element and going backwards.
        for (int i = a.length / 2 - 1; i >= 0; i--) {
            for (int j = i; j * 2 + 1 < a.length;) {
                PAUSE();
                int k = j * 2 + 1;
                if (k + 1 < a.length && a[k] < a[k + 1]) k++;
                if (a[j] < a[k]) swap(a, j, k); else break;
                j = k;
            }
        }
        // Phase 2: Successively place the biggest, then next biggest
        // items at the end of the array. each time reconstructing the
        // heap in the slots of the array not yet sorted.
        for (int i = a.length - 1; i > 0; i--) {
            swap(a, 0, i);
            for (int j = 0; j * 2 + 1 < i;) {
                PAUSE();
                int k = j * 2 + 1;
                if (k + 1 < i && a[k] < a[k + 1]) k++;
                if (a[j] < a[k]) swap(a, j, k); else break;
                j = k;
            }
        }
    }

    /**
     * Sorts an array using merge sort, the classic version with
     * the extra storage.
     */
    public void mergeSort(int[] a) {
        int[] scratch = new int[a.length];
        mergeSort(a, 0, a.length - 1, scratch);
    }

    private void mergeSort(int[] a, int lo, int hi, int[] scratch) {
        if (lo >= hi) return;

        int mid = (lo + hi) / 2;
        mergeSort(a, lo, mid, scratch);
        mergeSort(a, mid + 1, hi, scratch);

        // Merge sorted sublists into temporary storage
        for (int i = lo, j = mid + 1, k = lo; k <= hi; k++) {
            if ((i <= mid) && ((j > hi) || (a[i] < a[j]))) {
                scratch[k] = a[i++]; PAUSE();
            } else {
                scratch[k] = a[j++]; PAUSE();
            }
        }

        // Copy back from temporary storage
        for (int k = lo; k <= hi; k++) {
            a[k] = scratch[k]; PAUSE();
        }
    }

    /**
     * Sorts an array using counting sort, provided all values in the
     * array are non-negative.  If there are negative values in the array,
     * the method will not sort but rather leave the array undefined.
     * Furthermore, the method will likely throw an OutOfMemoryError
     * if there are large integers in the array.
     */
    public void countingSort(int[] a) {
        int max = 0;
        for (int i = 0; i < a.length; i++) {
            max = Math.max(max, a[i]);
            PAUSE();
        }
        System.out.println(max);
        int[] counts = new int[max + 1];
        Arrays.fill(counts, 0);
        for (int i = 0; i < a.length; i++) {
            counts[a[i]]++;
            PAUSE();
        }
        for (int i = 0, j = 0; j < counts.length; j++) {
            for (int k = 0; k < counts[j]; k++) {
                a[i++] = j;
                PAUSE();
            }
        }
    }

    public static void main(String[] args) {
        Sorter sorter = new Sorter();
        JFrame frame = new JFrame("Sorting");
        frame.getContentPane().add(sorter.toolbar, "North");
        frame.getContentPane().add(sorter, "Center");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.pack();
        frame.setVisible(true);
        sorter.runAnimation();
    }

    Action startAction = new AbstractAction("Start") {
        public void actionPerformed(ActionEvent e) {
            final String methodName = (String)comboBox.getSelectedItem();
            new Thread(new Runnable() {
                public void run() {
                startButton.setEnabled(false);
                stopButton.setEnabled(true);
                reload(array);
                try {
                    Sorter.class.getMethod(methodName,
                        new Class[]{array.getClass()})
                        .invoke(Sorter.this, new Object[]{array});
                } catch (Exception e) {
                }
                stopButton.setEnabled(false);
                startButton.setEnabled(true);
            }}
        ).start();
    }
    };

    Action stopAction = new AbstractAction("Stop") {
        public void actionPerformed(ActionEvent e) {
            shouldStop = true;
        }
    };

    private JToolBar toolbar = new JToolBar();
    private JButton startButton = new JButton(startAction);
    private JButton stopButton = new JButton(stopAction);
    JComboBox comboBox = new JComboBox(new String[]{
        "selectionSort",
        "insertionSort",
        "bubbleSort",
        "gnomeSort",
        "shellSort",
        "quickSort",
        "mergeSort",
        "heapSort",
        "countingSort"
    });

    public Sorter() {
        setPreferredSize(new Dimension(ARRAY_LENGTH, MAX_VALUE));
        setBorder(BorderFactory.createEtchedBorder());
        toolbar.add(comboBox);
        toolbar.add(startButton);
        toolbar.add(stopButton);
        comboBox.setMaximumRowCount(12);
    }

    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        for (int i = 0, n = array.length; i < n; i++) {
            g.drawLine(i, MAX_VALUE, i, MAX_VALUE - array[i]);
        }
    }

    /**
     * Causes the screen to be repainted every 30 ms or so.
     */
    private void runAnimation() {
        while (true) {
            repaint();
            try {Thread.sleep(30);} catch (InterruptedException e) {}
        }
    }

    /**
     * Something to call periodically during sorting.
     */
    private void PAUSE() {
        try {
            Thread.sleep(1);
            if (shouldStop) {
                shouldStop = false;
                // Can't think of a better way to stop than this
                throw new RuntimeException();
            }
        } catch (InterruptedException e) {
        }
    }
}

Choosing a Sorting Algorithm in Practice

Which algorithm (or combination of algorithms!) is right for you depends on your particular application. Ask yourself:

• Are you sorting large or small numbers of items?
• Are the items themselves large or small?
• Is the item size fixed?
• Are there only a small number of possible input values?
• Are you sorting in-memory or external files?
• Are you sorting just indices, or must you move data?
• Is stability a requirement?
• Is the code running on an embedded device, or a richly endowed system with plenty of extra memory?
• Do you know what kind of input you are likely to get, for example, is there a good chance the initial data might already be sorted or nearly sorted?
• Is security an issue, that is, are you sorting user-supplied data which is subject to algorithmic complexity attacks?