Pages

Sorters

// by John P. Spurgeon

/*            Although dictionaries of the English language define “sorting” as the process
 *          of separating or arranging things according to class or kind, computer program-
 *               mers traditionally use the word in a much more special sense of marshaling
 *          things into ascending or descending order. The process should perhaps be called
 *            ordering, not sorting; but anyone who tries to call it “ordering” is soon led
 *              into confusion because of the many different meaning attached to that word.
 *
 *                        — DONALD E. KNUTH, The Art of Computer Programming, vol. 3 (1998)
 *
 *
 *                                              Ernest Hemingway’s work is characterized by
 *                                          direct, uncomplicated prose and a lack of arti-
 *                                     fice. In his fiction, he describes only the tangible
 *                                      truths: dialog, action, superficial traits. He does
 *                                      not attempt to explain emotion; he leaves it alone.
 *                                           This is not because Hemingway doesn’t want his
 *                                      stories to convey feeling — quite the opposite: his
 *                                         intent is to create a vacuum so that it might be
 *                                        filled by the reader’s own experience. After all,
 *                                          emotion is more easily felt than described with
 *                                                                                   words:
 *
 *                                            I have tried to eliminate everything unneces-
 *                                            sary to conveying experience to the reader so
 *                                          that after he or she has read something it will
 *                                               become a part of his or her experience and
 *                                                          seem actually to have happened.
 *
 *                                                Hemingway’s prose is never showy, and his
 *                                           syntax is almost obsessively conventional. The
 *                                            short, unchallenging sentences and absence of
 *                                       difficult words add a childlike quality to his ca-
 *                                        dence. He assumes the role of naive observer, all
 *                                        the better to draw his readers into the emotional
 *                                                                            caos beneath.
 *
 *                                      — ANGUS CROLL, If Hemingway Wrote JavaScript (2015)
 */

// On 29 April 2018, this was at: http://scribbledecobble.blogspot.com/2018/04/sorters.html

// With a little help from my friends...

import java.lang.Iterable;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.TreeSet;
import java.util.List;
import java.util.Set;

/**************/
/* INTERFACES */
/**************/

// In the late execution of the program, values live in datasets.

interface Labeled { String label(); }
interface Dataset<E> extends Labeled {
    int size();
    E getValue(int i);
    E lastAdded();
}
interface ExtensibleDataset<E> extends Dataset<E> {
    void add(E element);
}

// The datasets yield fundamental integer metrics.

interface IntegralMetrics extends Labeled {
    Long sum();
    Long min();
    Long max();
    Double avg();
    Double sd(); // standard deviation
}

// And the metrics are used to analyze algorithms.

interface TimeAnalysis       { IntegralMetrics elapsedTime(); }
interface ComparisonAnalysis { IntegralMetrics comparisons(); }
interface ExchangeAnalysis   { IntegralMetrics exchanges(); }

// Actions are performed by actors.

interface Shuffler<E>                     { List<E> shuffle(List<E> list); }
interface Sorter<E extends Comparable<E>> { List<E> sort(List<E> list); }
interface Exchanger<E>                    { void exchange(List<E> list, int i, int j); }
interface ReadonlyCounter                 { long getCount(); }
interface Counter extends ReadonlyCounter { void increment(); }
interface Permuter<E> {
    List<List<E>> allPermutationsOf(Set<E> set);
    List<List<E>> allPermutationsOf(List<E> list);
}

// Some types are merely mashups.

interface SortingAnalysis extends TimeAnalysis, ComparisonAnalysis {}
interface ExchangeSortingAnalysis extends SortingAnalysis, ExchangeAnalysis {}

interface SorterAnalyzer<E extends Comparable<E>>
    extends Sorter<E>, SortingAnalysis, ReadonlyCounter {}

interface ExchangeSorterAnalyzer<E extends Comparable<E>>
    extends SorterAnalyzer<E>, ExchangeSortingAnalysis {}

/***************************************************/
/* COUNTERS, COMPARATORS, AND EXCHANGERS (oh my!)  */
/***************************************************/

class CounterMayThrowException implements Counter
{
    private long count = 0;
    private long overflowCount = 0;
    private final boolean throwExceptionIfCounterOverflows;

    public CounterMayThrowException() { this(true); }
    public CounterMayThrowException(boolean throwExceptionIfCounterOverflows) {
        this.throwExceptionIfCounterOverflows = throwExceptionIfCounterOverflows;
    }
    public final long getCount() { return count; }
    public final long getOverflowCount() { return overflowCount; }
    public final void increment()
    {
        if (++count < 0) // Increment count first and then check the value.
        {
            count = 1;
            onOverflow();
        }
    }
    protected void onOverflow() {
        if (throwExceptionIfCounterOverflows)
            throw new ArithmeticException("Counter overflowed.");
        if (++overflowCount < 0)
            throw new ArithmeticException("Overflow counter overflowed. (Wow!)");
    }
}

final class ComparatorCounter<E> implements Comparator<E>, ReadonlyCounter
{
    private final Comparator<E> comparator;
    private final Counter comparisonCounter = new CounterMayThrowException();
    public ComparatorCounter(Comparator<E> comparator) { this.comparator = comparator; }
    public final int compare(E left, E right)
    {
        comparisonCounter.increment();
        return comparator.compare(left, right);
    }
    public final long getCount() { return comparisonCounter.getCount(); }
}

final class ExchangerCounter<E> implements Exchanger<E>, ReadonlyCounter
{
    private final Counter exchangeCounter = new CounterMayThrowException();
    public final void exchange(List<E> list, int i, int j)
    {
        exchangeCounter.increment();
        final E tmp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, tmp);
    }
    public final long getCount() { return exchangeCounter.getCount(); }
}

/*********************/
/* DATA AND ANALYSIS */
/*********************/

class ExtensibleDatasetMetrics implements ExtensibleDataset<Long>, IntegralMetrics 
{
    private final String label;
    private List<Long> values = new ArrayList<Long>();
    private Long lastAdded = null;
    private Long sum = null;
    private Long min = null;
    private Long max = null;
    private Double sd;
    private boolean isDirty = false;

    public ExtensibleDatasetMetrics(String label) { this.label = label; }

    public final String label() { return label; }
    public final int size() { return values.size(); }
    public final Long getValue(int i) { return values.get(i); }
    public final Long lastAdded() { return lastAdded; }
    public final Long sum() { return sum; }
    public final Long max() { return max; }
    public final Long min() { return min; }
    public final Double avg() { return ((double)sum) / values.size(); }
    public final Double sd() {
        if (isDirty) {
            sd = computeStdDev(values, this.avg());
            isDirty = false;
        }
        return sd;
    }
    public void add(Long value) {
        isDirty = true;
        values.add(value);
        lastAdded = value;
        if (sum == null) min = max = sum = value;
        else {
            sum += value;
            if (value < min) min = value;
            else if (value > max) max = value;
        }
    }
    private double computeStdDev(List<Long> values, double average) {
        final int n = values.size();
        double sumOfSquares = 0;
        for (long value : values) {
            final double difference = value - average;
            sumOfSquares += difference * difference;
        }
        final double avgSquaredDifference = sumOfSquares / n;
        return Math.sqrt(avgSquaredDifference);
    }
}

/***********/
/* SORTING */
/***********/

/** Implementations of this.applySortMethod should use this.compare.
 */
abstract class AbstractSorterAnalyzer<E extends Comparable<E>> implements SorterAnalyzer<E>
{
    private final ComparatorCounter<E> comparatorCounter;
    private long startCompareCount, startTime;
    private final ExtensibleDatasetMetrics
        timeData = new ExtensibleDatasetMetrics("Time"),
        compareData = new ExtensibleDatasetMetrics("Comparisons");

    // Constructors

    protected AbstractSorterAnalyzer() {
        this((E left, E right) -> left.compareTo(right));
    }
    protected AbstractSorterAnalyzer(Comparator<E> comparator) {
        this(new ComparatorCounter<E>(comparator));
    }
    protected AbstractSorterAnalyzer(ComparatorCounter<E> comparatorCounter) {
        this.comparatorCounter = comparatorCounter;
    }

    // Other Protected Methods

    protected abstract void applySortMethod(List<E> list); /*** THE PROTAGONIST ***/
    protected final Comparator<E> getComparator() { return comparatorCounter; }
    protected final int compare(E left, E right) {
        return comparatorCounter.compare(left, right);
    }
    protected void doBeforeSorting() {
        startCompareCount = comparatorCounter.getCount();
        startTime = System.nanoTime();
    }
    protected void doAfterSorting() {
        timeData.add(System.nanoTime() - startTime);
        compareData.add(comparatorCounter.getCount() - startCompareCount);
    }

    // Public Methods

    public final List<E> sort(List<E> list) {
        doBeforeSorting();
        applySortMethod(list);
        doAfterSorting();
        return list;
    }
    public final long getCount() { return timeData.size(); }
    public final IntegralMetrics elapsedTime() { return timeData; }
    public final IntegralMetrics comparisons() { return compareData; }
    public String toString() { return this.getClass().getSimpleName(); }
}

/* Sorting by Exchanging */

/** Implementations of this.applySortMethod should use this.compare and this.exchange.
 */
abstract class AbstractExchangeSorterAnalyzer<E extends Comparable<E>>
extends AbstractSorterAnalyzer<E> implements ExchangeSorterAnalyzer<E>
{
    // Private Instance Variables

    private final ExchangerCounter<E> exchangerCounter = new ExchangerCounter<E>();
    private long startExchangeCount;
    private final ExtensibleDatasetMetrics exchangeData =
        new ExtensibleDatasetMetrics ("Exchanges");

    // Protected Constructor Methods

    protected AbstractExchangeSorterAnalyzer() {
        super();
    }
    protected AbstractExchangeSorterAnalyzer(Comparator<E> comparator) {
        super(comparator);
    }
    protected AbstractExchangeSorterAnalyzer(ComparatorCounter<E> comparatorCounter) {
        super(comparatorCounter);
    }

    // Other Protected Methods

    protected final void exchange(List<E> list, int i, int j) {
        exchangerCounter.exchange(list, i, j);
    }
    protected final void doBeforeSorting() {
        startExchangeCount = exchangerCounter.getCount();
        super.doBeforeSorting();        
    }
    protected final void doAfterSorting() {
        super.doAfterSorting();
        exchangeData.add(exchangerCounter.getCount() - startExchangeCount);
    }
    protected final ReadonlyCounter getExchangeCounter() { return exchangerCounter; }    

    // Public Methods

    public final IntegralMetrics exchanges() { return exchangeData; }
}

/* Bubble Sort */

final class BubbleSorter<E extends Comparable<E>> extends AbstractExchangeSorterAnalyzer<E>
{
    final ReadonlyCounter exchangeCounter;
    private long exchangeCount;

    public BubbleSorter() { exchangeCounter = getExchangeCounter(); }

    protected void applySortMethod(List<E> list)
    {
        final int n = list.size();
        for (int k = n - 1; k > 0; k--)        // The next largest value bubbles up to its spot each pass,
        {                                      // so we don't need to go all the way to the end each time.
            noteExchangeCount();               //   Note the current exchange count; we'll use it later.
            for (int i = 0; i < k; i++)        //   We'll compare successive pairs of elements beginning at
            {                                  //   at index zero, proceeding as far to the right as necessary.
                int j = i + 1;                 //     The index of left is i. Let j be the index of right.
                E left = list.get(i);          //     Get the value of left at position i.
                E right = list.get(j);         //     Get the value of right at position j.
                if (compare(left, right) > 0)  //     If left is greater than right,
                    exchange(list, i, j);      //       then exchange.
            }                                  //     Increment i and compare the next pair of elements.
            if (!madeMoreExchanges())          //   If we didn't make any more exchanges, then
                return;                        //     the list must be sorted, so return to whence you came.
        }                                      //   Repeat until done: bubble up the next largest value.
    }                                          // Done. (Shake a cocktail and celebrate.)
    private void noteExchangeCount()
    {
        exchangeCount = exchangeCounter.getCount();
    }
    private boolean madeMoreExchanges()
    {
        return exchangeCounter.getCount() > exchangeCount;
    }
}

/* Selection Sort */

final class SelectionSorter<E extends Comparable<E>> extends AbstractExchangeSorterAnalyzer<E>
{
    private int getIndexOfMin(List<E> list, int i, int j)
    {
        int indexOfMin = i;
        E min = list.get(indexOfMin);
        for (int k = i + 1; k <= j; k++)
        {
            E curr = list.get(k);
            if (compare(curr, min) < 0)
            {
                min = curr;
                indexOfMin = k;
            }
        }
        return indexOfMin;
    }
    protected void applySortMethod(List<E> list)
    {
        final int n = list.size();             // Let n be the number of elements to sort.
        final int j = n - 1;                   // Let j be the index of the last element.
        for (int i = 0; i < j; i++)            // Consider each successively smaller tail of the list:
        {                                      //
            int k = getIndexOfMin(list, i, j); //   Find the index of the smallest element in the tail.
            if (k != i)                        //   If the element is not at the front of the tail,
                exchange(list, i, k);          //     then exchange it with the head of the tail.
        }                                      //   Repeat until the tail is no more.
    }                                          // Done.
}

/* Insertion Sort */

final class InsertionSorter<E extends Comparable<E>> extends AbstractExchangeSorterAnalyzer<E>
{
    protected void applySortMethod(List<E> list)
    {
        final int n = list.size();            // Let n be the number of elements to insert in order.
        for (int i = 1; i < n; i++)           // Insert elements one by one into a sorted part.
        {                                     // The next element to insert, if any, is at index i.
            E right = list.get(i);            //   Let right be the value of the element at index i.
            for (int j = i - 1; j >= 0; j--)  //   Start just to the left of right and move left.
            {                                 //   The next already inserted element is at index j.
                E left = list.get(j);         //     Let left be the value of the element at index j.
                if (compare(right, left) < 0) //     If right is less than left, then
                    exchange(list, j, j + 1); //       exchange left and right (right must be at j + 1);
                else                          //     otherwise,
                    break;                    //       right is inserted. Go insert the next element.
            }                                 //     Consider the next already inserted element, if any.
        }                                     //   Insert the next element until all are inserted. 
    }                                         // Done.
}

/* Quick Sort */

final class QuickSorter<E extends Comparable<E>> extends AbstractExchangeSorterAnalyzer<E>
{
    private void quickSort(List<E> list, int i, int j)
    {
        if (j <= i) return;                  // (There might be nothing to do.)
        int p = i;                           // Let p be the index of the pivot.
        final E left = list.get(p);          // Let left be the value of the pivot.
        for (int k = i + 1; k <= j; k++)     // Consider each element to the right of the pivot.
        {                                    //
            E right = list.get(k);           //   Let right be the value under consideration.
            if (compare(right, left) < 0)    //   If right is less than left, then
            {                                //     move right to the other side of left:
                if (k > p + 1)               //     If right isn't already next to left, then
                  exchange(list, p + 1, k);  //        move right immediately to the right of left.
                exchange(list, p, p + 1);    //     Exchange left and right.
                p++;                         //     Increment the index of the pivot.
            }                                //   
        }                                    //   Consider the next element, if any.
        quickSort(list, i, p - 1);           // Sort the elements to the left of the pivot.
        quickSort(list, p + 1, j);           // Sort the elements to the right of the pivot.
    }                                        // Done.

    protected void applySortMethod(List<E> list)
    {
        quickSort(list, 0, list.size() - 1);
    }
}

/* Java Library's Collections.sort */

final class CollectionsSorter<E extends Comparable<E>> extends AbstractExchangeSorterAnalyzer<E>
{
    protected void applySortMethod(List<E> list)
    {
        Collections.sort(list, getComparator());
    }
}

/******************/
/* SORTER FACTORY */
/******************/

final class SorterFactory<E extends Comparable<E>>
{
    public List<ExchangeSorterAnalyzer<E>> makeExchangeSorters()
    {
        List<ExchangeSorterAnalyzer<E>> sorters;
        sorters = new LinkedList<ExchangeSorterAnalyzer<E>>();
        sorters.add(new BubbleSorter<E>());
        sorters.add(new SelectionSorter<E>());
        sorters.add(new InsertionSorter<E>());
        sorters.add(new QuickSorter<E>());
        sorters.add(new CollectionsSorter<E>());
        return sorters;
    }
}

/**********/
/* COPIER */
/**********/

final class Copier
{
    public static <E> List<E> copy(Iterable<E> list) {
        List<E> copyOfList = new LinkedList<E>();
        for (E element : list) copyOfList.add(element);
        return copyOfList;
    }
}

/************/
/* SHUFFLER */
/************/

final class KnuthShuffler<E> implements Shuffler<E>
{
    private int getRandomIntegerBetween(int lower, int upper)
    {
        final int diff = upper - lower;
        return lower + (int)(Math.random() * (diff + 1));
    }
    public List<E> shuffle(List<E> list)
    {
        final int lastIndex = list.size() - 1;
        for (int i = 0; i < lastIndex; i++) {
            int j = getRandomIntegerBetween(i, lastIndex);
            E tmp = list.get(i);
            list.set(i, list.get(j));
            list.set(j, tmp);
        }
        return list;
    }
}

/************/
/* PERMUTER */
/************/

final class RecursivePermuter<E> implements Permuter<E>
{
    public final List<List<E>> allPermutationsOf(Set<E> set)
    {
        ArrayList<E> list = new ArrayList<E>(set.size());
        for (E element : set) list.add(element);
        return allPermutationsOf(list, 0);
    }
    public final List<List<E>> allPermutationsOf(List<E> list)
    {
        return allPermutationsOf(list, 0);
    }
    private List<List<E>> allPermutationsOf(List<E> list, int headIndex)
    {
        final int permutationLength = list.size() - headIndex;
        List<List<E>> allPermutations = new ArrayList<List<E>>();
        if (permutationLength > 0) {
            E theHeadElement = list.get(headIndex);
            List<List<E>> allPermutationsOfTail = allPermutationsOf(list, headIndex + 1);
            for (List<E> permutationOfTail : allPermutationsOfTail) {
                final int lastIndex = permutationLength - 1;
                for (int putHeadAtIndex = 0; putHeadAtIndex <= lastIndex; putHeadAtIndex++) {
                    List<E> newPermutation = new ArrayList<E>(permutationLength);
                    for (int i = 0; i < lastIndex; i++) {
                        E nextTailElement = permutationOfTail.get(i);
                        if (putHeadAtIndex == i) {
                            newPermutation.add(theHeadElement);
                        }
                        newPermutation.add(nextTailElement);
                    }
                    if (putHeadAtIndex == lastIndex) {
                        newPermutation.add(theHeadElement);
                    }
                    allPermutations.add(newPermutation);
                }                
            }
        }
        else {
            allPermutations.add(new ArrayList<E>()); // There is one way to arrange no elements.
        }
        return allPermutations;
    }
}

/***********/
/* PRINTER */
/***********/

final class Printer<E extends Comparable<E>>
{
    private final String TAB = "\t", NEW_LINE = "\n";
    
    private final void printHeader() {
        final String headings[] = { "subset_size", "times_sorted",
            "min_cmp", "max_cmp", "avg_cmp", "sd_cmp",
            "min_xch", "max_xch", "avg_xch", "sd_xch",
            "min_nano_sec", "max_nano_sec", "avg_nano_sec", "sd_nano_sec" };
        final StringBuilder sb = new StringBuilder("sorter");
        for (String heading : headings) sb.append( TAB + heading);
        System.out.print(sb + NEW_LINE);
    }
    private final void print(IntegralMetrics metrics) {
        System.out.print(TAB + metrics.min());
        System.out.print(TAB + metrics.max());
        System.out.print(TAB + metrics.avg());
        System.out.print(TAB + metrics.sd());
    }
    private final void print(ExchangeSorterAnalyzer<E> sorter, int n) {
        System.out.print(sorter + TAB + n + TAB + sorter.getCount());
        print(sorter.comparisons());
        print(sorter.exchanges());
        print(sorter.elapsedTime());
        System.out.println();
    }
    public final void printSortingAnalysis(
            List<List<ExchangeSorterAnalyzer<E>>> setsOfSorters,
            List<Integer> countsOfElementsSorted) {
        printHeader();
        final int n = setsOfSorters.size();
        if (n == 0) return;
        final int m = setsOfSorters.get(0).size(); // Every set has the same number of sorters.
        for (int i = 0; i < n; i++) {
            final List<ExchangeSorterAnalyzer<E>> setOfSorters = setsOfSorters.get(i);            
            final int numberOfElementsSorted = countsOfElementsSorted.get(i);
            for (int j = 0; j < m; j++)
                print(setOfSorters.get(j), numberOfElementsSorted);
        }
    }
}

/***********/
/* SORTERS */
/***********/

final class Sorters<E extends Comparable<E>>
{
    private final List<List<ExchangeSorterAnalyzer<E>>> setsOfSorters =
        new LinkedList<List<ExchangeSorterAnalyzer<E>>>();
    private List<ExchangeSorterAnalyzer<E>> sorters;
    private final List<Integer> countsOfElementsSorted = new LinkedList<Integer>();
    private final Printer<E> printer = new Printer<E>();
    private final Permuter<E> permuter = new RecursivePermuter<E>();
    private final SorterFactory<E> sorterFactory = new SorterFactory<E>();
    private final Shuffler<E> shuffler = new KnuthShuffler<E>();

    private void makeNextSetOfSorters(Set<E> set) {
        sorters = sorterFactory.makeExchangeSorters();
        setsOfSorters.add(sorters);        
        countsOfElementsSorted.add(set.size());
    }
    private void sortCopiesOf(List<E> permutation) {
        for (Sorter<E> sorter : sorters)
          sorter.sort(Copier.copy(permutation));
    }
    private final void sortAllPermutationsOf(Set<E> set) {
        makeNextSetOfSorters(set);
        for (List<E> permutation : permuter.allPermutationsOf(set))
            sortCopiesOf(permutation);
    }
    private final void sortShufflingsOf(Set<E> set, int timesToSort) {
        makeNextSetOfSorters(set);
        final List<E> list = Copier.copy(set);
        while (timesToSort-- > 0)
            sortCopiesOf(shuffler.shuffle(list));
    }
    public final void sortPermutationsOf(Set<E> set) {
        final int setSize = set.size();
        if (setSize <= 8) {
            sortAllPermutationsOf(set);
        }
        else {
            sortShufflingsOf(set, 10000);
        }
    }
    public final void report() {        
        printer.printSortingAnalysis(setsOfSorters, countsOfElementsSorted);
    }
}

/****************/
/* MAIN PROGRAM */
/****************/

final public class SortPermutationsOfAllSubsetsAndReport
{
    private static final Sorters<String> sorters = new Sorters<String>();

    private static void sortPermutationsOfAllSubsetsOf(String[] array)
    {
        final Set<String> set = new TreeSet<String>();

        sorters.sortPermutationsOf(set);      // Sort permutations of the empty set.
        for (String string : array) {         // Sort permutations of all nonempty subsets:
            set.add(string);                  //   Add an element to the set.
            sorters.sortPermutationsOf(set);  //   Sort permutations of the larger set.
        }
    }
    public static void main(String[] args)
    {
        sortPermutationsOfAllSubsetsOf(args);
        sorters.report();
    }
}