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