// 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(); } }