// by John P. Spurgeon
/* Of course, “nonnumerical analysis” is a terribly negative name for this
* field of study, and it would be much better to have a positive, descriptive term
* which characterizes the subject. “Information processing” is too broad a
* designation for the matter I am considering, and “programming techniques”
* is too narrow. Therefore, I wish to propose analysis of algorithms as an appro-
* priate name for the subject matter covered in these books; as explained more
* fully in the books themselves, this name is meant to imply “the theory of the
* properties of particular computer algorithms.”
*
* — DONALD E. KNUTH, The Art of Computer Programming, vol. 1 (1968)
*
*
* 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)
*
*
* In the late summer of that year we lived in a house in a village
* that looked across the river and the plain to the mountains.
*
* — ERNEST HEMINGWAY, A Farewell to Arms (1929)
*/
// On 30 April 2018, this was at:
// http://scribbledecobble.blogspot.com/2018/04/analysis-of-algorithms.html
/* In the last years of my twenty at the corporation, we built a house on a hill that looks across
* the Sunset Highway and the Willamette Valley to town. I worked in the IT department back then.
*/
/* An arm is an upper limb of the body.
* Arm or ARM may also refer to:
*
* Computing
*
* - ARM architecture, a RISC instruction set family
* - ARM Holdings, a multinational company that designs the ARM computer processors
* - Application Response Measurement, an open standard for diagnosing performance bottlenecks
* - Abstract rewriting machine, a virtual machine
* - Arm (software), a CLI status monitor for Tor
*
* Weaponry
*
* - Armaments or weapon, any device used with intent to inflict damage or harm
* - Firearm, a portable gun
* - Anti-radiation missile, a missile designed to detect and home in on an enemy radio emission source
*
* from https://en.wikipedia.org/wiki/Arm_(disambiguation)
*/
/* Edmund Callis Berkeley (February 22, 1909 – March 7, 1988) was an American computer scientist
* who co-founded the Association for Computing Machinery (ACM) in 1947. His 1949 book Giant Brains,
* or Machines That Think popularized cognitive images of early computers. He was also a social
* activist who worked to achieve conditions that might minimize the threat of nuclear war.
*
* Berkeley received a BA in Mathematics and Logic from Harvard in 1930. He pursued a career as an
* insurance actuary at Prudential Insurance from 1934–48, except for service in the United States
* Navy during World War II.
*
* from https://en.wikipedia.org/wiki/Edmund_Berkeley
*/
/* The leaders of North and South Korea agreed on Friday to work to remove all nuclear weapons from the
* Korean Peninsula and, within the year, pursue talks with the United States to declare an official end
* to the Korean War, which ravaged the peninsula from 1950 to 1953.
*
* from “North and South Korea Set Bold Goals: A Final Peace and No Nuclear Arms”
* by Choe Sang-Hun, The New York Times (April 27, 2018); accessed on 29 April 2018 at:
* https://www.nytimes.com/2018/04/27/world/asia/north-korea-south-kim-jong-un.html
*/
/***********************************/
/* PROGRAM SOURCE CODE BEGINS HERE */
/***********************************/
import java.lang.Iterable;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.List;
/**************/
/* INTERFACES */
/**************/
// Values comprise 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);
}
// Datasets yield fundamental metrics.
interface IntegralMetrics extends Labeled {
Long sum();
Long min();
Long max();
Double avg();
Double sd(); // standard deviation
}
// Fundamental metrics can be used to analyze algorithms.
interface TimeAnalysis { IntegralMetrics elapsedTime(); }
interface ComparisonAnalysis { IntegralMetrics comparisons(); }
interface ExchangeAnalysis { IntegralMetrics exchanges(); }
// Doers do.
interface Searcher<E extends Comparable<E>> { int search(E element, 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 Permuter<E> { List<List<E>> allPermutationsOf(List<E> list); }
interface Shuffler<E> { List<E> shuffle(List<E> list); }
interface ReadonlyCounter { long getCount(); }
interface Counter extends ReadonlyCounter { void increment(); }
// Some types are mashups, such as doers that think too.
interface ComparisonAlgorithmAnalysis extends TimeAnalysis, ComparisonAnalysis {}
interface ExchangeSortingAnalysis extends ComparisonAlgorithmAnalysis, ExchangeAnalysis {}
interface SearcherAnalyzer<E extends Comparable<E>>
extends Searcher<E>, ComparisonAlgorithmAnalysis, ReadonlyCounter {}
interface SorterAnalyzer<E extends Comparable<E>>
extends Sorter<E>, ComparisonAlgorithmAnalysis, ReadonlyCounter {}
interface ExchangeSorterAnalyzer<E extends Comparable<E>>
extends SorterAnalyzer<E>, ExchangeSortingAnalysis {}
/*****************************************/
/* COUNTERS, COMPARATORS, AND EXCHANGERS */
/*****************************************/
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(); }
}
/********************************/
/* EXTENSIBLE DATASET + METRICS */
/********************************/
final 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);
}
}
/* Doctrine and dogma are the enemies of good JavaScript. Beware of the overly
* protective mentor; reject the dry and narrow confines of computer science
* classes. Some developers thrive on rules and constraint, which is why there
* is Java. If 25 famous authors wrote Java, the result would be more or less
* the same every time. But JavaScript is much less prescriptive and appeals to
* those who value creativity over predictability.
*
* —ANGUS CROLL, If Hemingway Wrote JavaScript (2015)
*/
/*********************************/
/* COMPARISON ALGORITHM ANALYZER */
/*********************************/
abstract class AbstractComparisonAlgorithmAnalyzer<E extends Comparable<E>>
implements ComparisonAlgorithmAnalysis
{
private final ComparatorCounter<E> comparatorCounter;
private long startCompareCount, startTime;
private final ExtensibleDatasetMetrics
timeData = new ExtensibleDatasetMetrics("Time"),
compareData = new ExtensibleDatasetMetrics("Comparisons");
// Constructors
protected AbstractComparisonAlgorithmAnalyzer() {
this((E left, E right) -> left.compareTo(right));
}
protected AbstractComparisonAlgorithmAnalyzer(Comparator<E> cmp) {
this(new ComparatorCounter<E>(cmp));
}
protected AbstractComparisonAlgorithmAnalyzer(ComparatorCounter<E> cmpCtr) {
this.comparatorCounter = cmpCtr;
}
// Protected Operations
protected final Comparator<E> getComparator() {
return comparatorCounter;
}
protected final int compare(E left, E right) {
return comparatorCounter.compare(left, right);
}
protected void doBeforeCallingMethod() {
startCompareCount = comparatorCounter.getCount();
startTime = System.nanoTime();
}
protected void doAfterMethodReturns() {
timeData.add(System.nanoTime() - startTime);
compareData.add(comparatorCounter.getCount() - startCompareCount);
}
// Public Operations
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(); }
}
/************************/
/* ALL SORTS OF SORTERS */
/************************/
abstract class AbstractSorterAnalyzer<E extends Comparable<E>>
extends AbstractComparisonAlgorithmAnalyzer<E> implements SorterAnalyzer<E>
{
// Constructors
protected AbstractSorterAnalyzer() { super(); }
protected AbstractSorterAnalyzer(Comparator<E> cmp) { super(cmp); }
// Additional Operations
protected abstract void applySortMethod(List<E> list); // SORTING ALGORITHM GOES HERE
public final List<E> sort(List<E> list)
{
doBeforeCallingMethod(); // START COLLECTING DATA
applySortMethod(list); // EXECUTE SORTING ALGORITHM
doAfterMethodReturns(); // FINISH COLLECTING DATA
return list;
}
}
abstract class AbstractExchangeSorterAnalyzer<E extends Comparable<E>>
extends AbstractSorterAnalyzer<E> implements ExchangeSorterAnalyzer<E>
{
// Additional Values
private final ExchangerCounter<E> exchangerCounter = new ExchangerCounter<E>();
private long startExchangeCount;
private final ExtensibleDatasetMetrics exchangeData =
new ExtensibleDatasetMetrics("Exchanges");
// Constructors
protected AbstractExchangeSorterAnalyzer() { super(); }
protected AbstractExchangeSorterAnalyzer(Comparator<E> cmp) { super(cmp); }
// Method Overrides
protected final void doBeforeCallingMethod() {
startExchangeCount = exchangerCounter.getCount();
super.doBeforeCallingMethod();
}
protected final void doAfterMethodReturns() {
super.doAfterMethodReturns();
exchangeData.add(exchangerCounter.getCount() - startExchangeCount);
}
// Additional Operations
protected final void exchange(List<E> list, int i, int j) {
exchangerCounter.exchange(list, i, j);
}
protected final ReadonlyCounter getExchangeCounter() { return exchangerCounter; }
public final IntegralMetrics exchanges() { return exchangeData; }
}
final class BubbleSorter<E extends Comparable<E>> extends AbstractExchangeSorterAnalyzer<E>
{
public BubbleSorter() { super(); }
public BubbleSorter(Comparator<E> cmp) { super(cmp); }
protected void applySortMethod(List<E> list)
{
final int n = list.size();
final ReadonlyCounter xCtr = getExchangeCounter();
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.
final long xCt = xCtr.getCount(); // 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.
final int j = i + 1; // The index of left is i. Let j be the index of right.
final E left = list.get(i); // Get the value of left at position i.
final 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 (xCt == xCtr.getCount()) // 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!
}
final class SelectionSorter<E extends Comparable<E>> extends AbstractExchangeSorterAnalyzer<E>
{
public SelectionSorter() { super(); }
public SelectionSorter(Comparator<E> cmp) { super(cmp); }
private int indexOfMin(List<E> list, int i, int j)
{
int indexOfMin = i;
E min = list.get(indexOfMin);
for (int k = i + 1; k <= j; k++)
{
final 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:
{ //
final int k = indexOfMin(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.
}
final class InsertionSorter<E extends Comparable<E>> extends AbstractExchangeSorterAnalyzer<E>
{
public InsertionSorter() { super(); }
public InsertionSorter(Comparator<E> cmp) { super(cmp); }
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.
final 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.
final 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.
}
final class QuickSorter<E extends Comparable<E>> extends AbstractExchangeSorterAnalyzer<E>
{
public QuickSorter() { super(); }
public QuickSorter(Comparator<E> cmp) { super(cmp); }
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.
{ //
final 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); }
}
final class CollectionsSorter<E extends Comparable<E>> extends AbstractExchangeSorterAnalyzer<E>
{
public CollectionsSorter() { super(); }
public CollectionsSorter(Comparator<E> cmp) { super(cmp); }
protected void applySortMethod(List<E> list) { Collections.sort(list, getComparator()); }
}
/*
final class MergeSorter<E extends Comparable<E>> extends AbstractExchangeSorterAnalyzer<E>
{
private List<E> valuesToSort;
private List<E> mergedValues;
public MergeSorter() { super(); }
public MergeSorter(Comparator<E> cmp) { super(cmp); }
private void createMergedValues(int n) {
mergedValues = new ArrayList<E>(n);
while (n-- > 0) mergedValues.add(null);
}
private void merge(int iStart, int iEnd, int jStart, int jEnd) {
E nextValue;
int i = iStart, j = jStart;
int k = i;
// TO DO: FINISH
while (i <= iEnd && j <= jEnd) {
final E iValue = valuesToSort.get(i);
final E jValue = valuesToSort.get(j);
if (compare(iValue, jValue) < 0) {
nextValue = iValue;
i++;
}
else {
nextValue = jValue;
j++;
}
mergedValues.set(k++, nextValue);
}
while (i <= iEnd) {
nextValue = valuesToSort.get(i++);
mergedValues.set(k++, nextValue);
}
while (j <= jEnd) {
nextValue = valuesToSort.get(j++);
mergedValues.set(k++, nextValue);
}
}
private void mergeSort(int i, int j) {
final int n = (j - i) + 1;
if (n < 2) return;
int startRight = i + (n / 2);
int endLeft = startRight - 1;
// TO DO: FINISH
if (n > 1) {
mergeSort(i, endLeft);
mergeSort(startRight, j);
}
merge(i, endLeft, startRight, j);
for (int k = i; k <= j; k++)
valuesToSort.set(k, mergedValues.get(k));
}
protected void applySortMethod(List<E> list) {
final int n = list.size();
if (n < 2) return;
valuesToSort = list;
createMergedValues(n);
mergeSort(0, n - 1);
}
}
*/
/******************/
/* 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>());
//sorters.add(new MergeSorter<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;
}
}
/*************/
/* SHUFFLERS */
/*************/
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;
}
}
final class SortShuffler<E> implements Shuffler<E> {
public List<E> shuffle(List<E> list) {
Collections.sort(list, (E l, E r) -> (int)(Math.random() - 0.5));
return list;
}
}
/* A permutation of a finite set is an arrangement of its elements into a row.
*
* — DONALD E. KNUTH, The Art of Computer Programming, vol. 3 (1998)
*/
/************/
/* PERMUTER */
/************/
final class RecursivePermuter<E> implements Permuter<E>
{
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;
}
}
/********************/
/* ANALYSIS PRINTER */
/********************/
final class AnalysisPrinter<E extends Comparable<E>>
{
private final String TAB = "\t", NEW_LINE = "\n";
public final void printHeaderRow()
{
// OOPS! These headings are out of order!!
final String headings[] = { "row_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 printMetrics(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 printAnalysis(ComparisonAlgorithmAnalysis analysis)
{
printMetrics(analysis.elapsedTime());
printMetrics(analysis.comparisons());
}
private final void printAnalysis(ExchangeSortingAnalysis analysis)
{
printMetrics(analysis.elapsedTime());
printMetrics(analysis.comparisons());
printMetrics(analysis.exchanges());
}
public final void printDataRow(SearcherAnalyzer<E> searcher, int n)
{
System.out.print(searcher + TAB + n + TAB + searcher.getCount());
printAnalysis(searcher);
System.out.println();
}
public final void printDataRow(SorterAnalyzer<E> sorter, int n)
{
System.out.print(sorter + TAB + n + TAB + sorter.getCount());
printAnalysis(sorter);
System.out.println();
}
public final void printDataRow(ExchangeSorterAnalyzer<E> sorter, int n)
{
System.out.print(sorter + TAB + n + TAB + sorter.getCount());
printAnalysis(sorter);
System.out.println();
}
}
/* The time required to sort N records, using a decent general-purpose sorting algorithm,
* is roughly proportional to N log N; we make about log N “passes” over the data. This is
* the minimal time, as we shall see in Section 5.3.1 if the records are in random order
* and if sorting is done by pairwise comparisons of keys.
*
* — DONALD E. KNUTH, The Art of Computer Programming, vol. 3 (1998)
*/
/********************/
/* SORTING ANALYZER */
/********************/
final class SortingAnalyzer<E extends Comparable<E>>
{
private final int rowSizeTippingPoint, sampleSize;
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 final AnalysisPrinter<E> printer = new AnalysisPrinter<E>();
private List<ExchangeSorterAnalyzer<E>> sorters;
private boolean headerPrinted = false;
public SortingAnalyzer(int rowSizeTippingPoint, int sampleSize) {
this.rowSizeTippingPoint = rowSizeTippingPoint;
this.sampleSize = sampleSize;
}
private void sortCopiesOf(List<E> permutation) {
for (Sorter<E> sorter : sorters)
sorter.sort(Copier.copy(permutation));
}
private final void sortAllPermutationsOf(List<E> row) {
for (List<E> permutation : permuter.allPermutationsOf(row))
sortCopiesOf(permutation);
}
private final void sortShufflingsOf(List<E> row, int timesToSort) {
final List<E> list = Copier.copy(row);
while (timesToSort-- > 0)
sortCopiesOf(shuffler.shuffle(list));
}
public final void sortPermutationsOf(List<E> row) {
sorters = sorterFactory.makeExchangeSorters();
final int rowSize = row.size();
if (rowSize < rowSizeTippingPoint)
sortAllPermutationsOf(row);
else
sortShufflingsOf(row, sampleSize);
if (!headerPrinted) {
printer.printHeaderRow();
headerPrinted = true;
}
for (ExchangeSorterAnalyzer<E> sorter : sorters)
printer.printDataRow(sorter, rowSize);
}
}
/* The character is believed to have initiated a phenomenon referred to as
* “The Scully Effect”; as the medical doctor and the FBI Special Agent inspired
* many young women to pursue careers in science, medicine and law enforcement,
* and as a result brought a perceptible increase in the number of women
* in those fields.
*
* https://en.wikipedia.org/wiki/Dana_Scully (accessed on 30 April 2018)
*/
/**************************/
/* SORTING ANALYZER AGENT */
/**************************/
final class SortingAnalyzerAgent
{
private final SortingAnalyzer<String> analyzer;
public SortingAnalyzerAgent(int rowSizeTippingPoint, int sampleSize) {
analyzer = new SortingAnalyzer<String>(rowSizeTippingPoint, sampleSize);
}
private List<List<String>> makeRowsToSort(String[] args) {
final List<List<String>> rows = new LinkedList<List<String>>();
final int n = args.length;
for (int i = 1; i < n; i++) {
final List<String> row = new LinkedList<String>();
final int rowSize = Integer.parseInt(args[i]);
for (Integer element = 1; element <= rowSize; element++)
row.add(element.toString());
rows.add(row);
}
return rows;
}
private List<String> makeRowToSort(String[] args) {
final List<String> row = new LinkedList<String>();
final int n = args.length;
for (int i = 1; i < n; i++)
row.add(args[i]);
return row;
}
public final void analyzeSortingAlgorithms(String[] args, String arg0) {
if (arg0.equals("sort_rows_of_size")) {
System.out.println("Sorting permutations of zero or many rows...\n");
for (List<String> row : makeRowsToSort(args))
analyzer.sortPermutationsOf(row);
}
else if (arg0.equals("sort")) {
System.out.println("Sorting permutations of a single row...\n");
analyzer.sortPermutationsOf(makeRowToSort(args));
}
}
}
/* Ada Lovelace was the first person to publish an algorithm intended to be executed
* by the first modern computer, the Analytical Engine created by Charles Babbage.
* Because of this, she is often regarded as the first computer programmer, ...
*
* https://en.wikipedia.org/wiki/Women_in_computing (accessed on 30 April 2018)
*/
/***************/
/* MAIN METHOD */
/***************/
final public class AnalysisOfAlgorithms
{
private static final int ROW_SIZE_TIPPING_POINT = 8;
private static final int SAMPLE_SIZE = 1000;
private static void println(String s) { System.out.println(s); }
public static void main(String[] args)
{
final String arg0 = args.length > 0 ? args[0] : "";
final String arg2 = args.length > 2 ? args[2] : "";
if (arg0.equals("search_for") &&
(arg2.equals("in") || arg2.equals("in_rows_of_size"))) {
System.out.println("Sorry. Searching is not implemented yet.");
}
else if (arg0.equals("sort") || arg0.equals("sort_rows_of_size")) {
final SortingAnalyzerAgent agentLovelace = new SortingAnalyzerAgent(
ROW_SIZE_TIPPING_POINT, SAMPLE_SIZE);
agentLovelace.analyzeSortingAlgorithms(args, arg0);
}
else {
println("This program is designed to sort or search permutations of values and output an");
println("analysis of the sorting or searching algorithms used. When fully implemented,");
println("the program will respond to command-line arguments as follows.\n");
println("1. If the first command-line argument is sort or sort_rows_of_size, then");
println(" the program will attempt to sort several permutations of rows of values.\n");
println(" a) If the first argument is sort_rows_of_size, then the remaining arguments");
println(" should be non-negative integers specifying the sizes of rows of strings");
println(" to be generated, permuted, and sorted.");
println(" b) Otherwise, the remaining arguments will be the elements of a row of strings");
println(" to be permuted and sorted.\n");
println("2. If the first command-line argument is search_for and the third argument");
println(" is in or in_rows_of_size, then the program will attempt to search for");
println(" the string passed as the second argument.\n");
println(" a) If the third argument is in_rows_of_size, then the remaining arguments");
println(" should be non-negative integers specifying the sizes of rows of strings");
println(" to be generated, permuted, and searched.");
println(" b) Otherwise, the remaining arguments will be the elements of a row of strings");
println(" to be permuted and searched.\n");
println("3. Otherwise, this documentation is printed.\n");
println("An exception will be thrown if an argument that should represent a row size is not");
println("an integer or if the integral value is too large or too small.\n");
println("This version is not fully implemented. It doesn't support searching yet.");
}
}
}
/*********************************************************************************************************/
/* A SHORT ROW TO HOE: a title devised to avoid the word EXERCISES, which many students find frightening */
/*********************************************************************************************************/
/* 0. Use this program to sort the row: 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703
* Use it to sort permutations of rows of size: 0 1 2 3 4 ...
* Use it to sort permutations of rows of size: 1 2 4 8 16 ...
*
* Copy the program’s output and paste it into a spreadsheet application like Excel or Libre Office
* Calc. Use pivot tables and charts to study how execution time, comparison counts, and exchange
* counts vary across different sorting algorithms and row sizes. What did you learn? Did anything
* surprise you? Were any unanswered questions raised? If so, which question is most interesting to
* you, and how might you go about trying to find an answer? Where did those random numbers come from?
*
* 1. What is the largest row size you can sort permutations of using the program as it is written? How can
* you change the program to sort permutations of larger rows? What is the largest row size you can sort
* permutations of if you are only allowed to modify the AnalysisOfAlgorithms class? What did you change?
*
* 2. Using a slightly modified version of this program (you may modify the AnalysisOfAlgorithms class),
* what is the maximum number of times per sorting algorithm that you can sort the sixteen three-digit
* numbers shown above in exercise 1? What limits you? Your own patience? Some other finite resource?
*
* 3. How do the sorting algorithms implemented by the program compare in terms of execution time,
* comparison counts, and exchange counts? Which algorithm is best? Which algorithm is worst? Which
* algorithm is the most predictable? Which is the least predictable? What assumptions are you making?
*
* 4. How does the best algorithm compare to the second best algorithm? Define best. Can you make any
* improvements to either one? Can you implement an algorithm that is better than the best one? Are
* you encouraged or discouraged by what you’ve discovered? Are you motivated? In what sense?
*
* 5. Run this program on different computers. Try using different online Java IDEs. What can you learn
* about the capabilities of different platforms using this program? What did you learn?
*
* 6. Enhance this program so that it can be used, per the program’s documentation, to analyze searching
* algorithms in addition to sorting algorithms. Use the search-related interfaces provided, and
* extend the AbstractComparisonAlgorithmAnalyzer class. (Use the AbstractSorterAnalyzer class as
* an example.) Implement binary and linear search algorithms, and use the enhanced program to
* analyze your algorithms. What is an elephant in Cairo, and why is this question relevant?
*
* 7. List the basic features and capabilities of the Java programming language used by this program.
* What basic features are not used? What advanced features does this program use? Explain
* what the following terms mean and provide examples from this program of each: interface, class
* constructor, local variable, constant variable, instance variable, class variable, parameter
* argument, lambda expression, inheritance, subtyping, subclassing, polymorphism, method overriding,
* method overloading, lambda expression, generics, recursion. Cite your sources.
*
* 8. On page 453, the authors of Introduction to Computer Science: An Interdisiplinary Approach (2017)
* say that subclassing is controversial because its advantages over subtyping are debatable. What are
* some advantages and disadvantages of subclassing? Is the use of subclassing in this program safe?
* Is it justified? Why? How can subclassing be used responsibly? How can it be prevented? Should
* CounterMayThrowException be final? Which of the overloaded versions of Collections.sort exemplifies
* dependency injection? How are dependency injection and subtyping related? Is dependency injection
* dangerous? Is SortShuffler.shuffle using or being reckless with Collections.sort?
*
* 9. Is Java too full of rules and constraints? Do you value creativity over predictability?
*/
