/* Program: AnalysisOfSortingAlgorithms
* By: John P. Spurgeon
* Created: 21 April 2018
* Updated: 23 April 2018
* URL: http://scribbledecobble.blogspot.com/2018/04/analysis-of-sorting-algorithms.html
*
* Some (multi)sets to try to sort.
*
* 0. Simple Sets: a b c d e f g h ...
*
* 1. A Multiset: c a b d d a b d a d
* See: TAOCP, vol. 3, sec. 5.1.2.
*
* 2. A Set: 503 087 512 061 908 170 897 275 653 426 154 509 612 677 765 703
* See: TAOCP, vol. 3 (2nd ed.), p. 76.
*/
// With a little help from my friends...
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.List;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Collections;
/* abstracted adj.
*
* 1. Drawn off; separate, apart from 1660.
* 2. Withdrawn from the contemplation of present objects; absent in mind 1643.
* *3. Separated from the concrete, ideal, abstruse (replaced by ABSTRACT a. 4) - 1823.
*
* The Evil one a. stood From his own evil MILT.
*
* * disinterestedness.
*
* Source: The Sorter Oxford English Dictionary on Historical Principles,
* Third Edition, Revised with Addenda (1947).
*/
interface ComparisonCounter
{
int getComparisonCount();
}
interface ExchangeCounter
{
int getExchangeCount();
}
interface ExecutionTimer
{
long getElapsedTime();
}
/* Counting Comparator */
final class CountingComparator<E> implements Comparator<E>, ComparisonCounter
{
private Comparator<E> cmp;
private int comparisonCount = 0;
public CountingComparator(Comparator<E> cmp)
{
this.cmp = cmp;
}
// lhs: left hand side.
// rhs: right hand side.
public final int compare(E lhs, E rhs)
{
comparisonCount++;
return cmp.compare(lhs, rhs);
}
public final int getComparisonCount()
{
return comparisonCount;
}
}
/* All Sorts of Sorters */
final class Sorters
{
public static final String
PARTIALLY_ABSTRACTED_SORTER = "Partially Abstracted Sorter",
COUNTING_SORTER = "Counting Sorter",
EXCHANGE_SORTER = "Exchange Sorter",
COUNTING_EXCHANGE_SORTER = "Counting Exchange Sorter",
BAD_BUBBLE_SORTER = "Bad Bubble Sorter",
BETTER_BUBBLE_SORTER = "Better Bubble Sorter",
BEST_BUBBLE_SORTER = "Best Bubble Sorter",
INSERTION_SORTER = "Insertion Sorter",
MERGE_SORTER = "Merge Sorter",
QUICK_SORTER = "Quick Sorter",
COLLECTIONS_SORTER = "Collections Sorter";
}
// Generic, Possibly-Partially-Disinterested (in performance) Sorters
interface Sorter extends ComparisonCounter, ExchangeCounter, ExecutionTimer
{
<E> void sort(List<E> sequence, Comparator<E> cmp);
<E extends Comparable<E>> void sort(List<E> sequence);
<E extends Comparable<E>> void sortReverse(List<E> sequence);
// Does it actually count?
boolean countsComparisons();
boolean countsExchanges();
}
// Certainly partially disinterested...
abstract class PartiallyAbstractedSorter implements Sorter
{
private long elapsedTime;
//******************************************//
// ALL YOU HAVE TO DO IS SUPPLY THE METHOD! //
//******************************************//
protected abstract <E> void sortMethod(List<E> sequence, Comparator<E> cmp);
// This Sorter is not entirely abstracted: it pays close attention to time.
protected final <E> void timeSortMethod(List<E> sequence, Comparator<E> cmp)
{
long start = System.nanoTime();
this.sortMethod(sequence, cmp);
elapsedTime = System.nanoTime() - start;
}
public <E> void sort(List<E> sequence, Comparator<E> cmp)
{
timeSortMethod(sequence, cmp);
}
public final <E extends Comparable<E>> void sort(List<E> sequence)
{
Comparator<E> cmp = (E lhs, E rhs) -> lhs.compareTo(rhs);
sort(sequence, cmp);
}
public final <E extends Comparable<E>> void sortReverse(List<E> sequence)
{
Comparator<E> cmp = (E lhs, E rhs) -> rhs.compareTo(lhs);
sort(sequence, cmp);
}
public boolean countsComparisons()
{
return false;
}
public boolean countsExchanges()
{
return false;
}
public int getComparisonCount()
{
throw new UnsupportedOperationException();
}
public int getExchangeCount()
{
throw new UnsupportedOperationException();
}
public String toString()
{
return Sorters.PARTIALLY_ABSTRACTED_SORTER;
}
public long getElapsedTime()
{
return elapsedTime;
}
}
abstract class CountingSorter extends PartiallyAbstractedSorter
{
private int comparisonCount = 0;
public final <E> void sort(List<E> sequence, Comparator<E> cmp)
{
CountingComparator<E> cc = new CountingComparator<E>(cmp);
timeSortMethod(sequence, cc);
comparisonCount = cc.getComparisonCount();
}
public final boolean countsComparisons()
{
return true;
}
public final int getComparisonCount()
{
return comparisonCount;
}
public String toString()
{
return Sorters.COUNTING_SORTER;
}
}
abstract class ExchangeSorter extends PartiallyAbstractedSorter
{
protected <E> void swap(List<E> sequence, int i, int j)
{
E tmp = sequence.get(i);
sequence.set(i, sequence.get(j));
sequence.set(j, tmp);
}
public String toString()
{
return Sorters.EXCHANGE_SORTER;
}
}
abstract class CountingExchangeSorter extends ExchangeSorter
{
private int comparisonCount = 0, exchangeCount = 0;
protected final <E> void swap(List<E> sequence, int i, int j)
{
super.swap(sequence, i, j);
exchangeCount++;
}
public final <E> void sort(List<E> sequence, Comparator<E> cmp)
{
exchangeCount = 0;
CountingComparator<E> cc = new CountingComparator<E>(cmp);
timeSortMethod(sequence, cc);
comparisonCount = cc.getComparisonCount();
}
public final boolean countsComparisons()
{
return true;
}
public final boolean countsExchanges()
{
return true;
}
public final int getComparisonCount()
{
return comparisonCount;
}
public final int getExchangeCount()
{
return exchangeCount;
}
public String toString()
{
return Sorters.COUNTING_EXCHANGE_SORTER;
}
}
// Bubble Sort
class BadBubbleSorter extends CountingExchangeSorter
{
// Exercise 1a: Fix the problem with the bubble sort implementation below.
protected <E> void sortMethod(List<E> sequence, Comparator<E> cmp)
{
/*
* This method sorts. But it sorts in the wrong direction!
*/
final int n = sequence.size();
final int lastIndex = n - 1;
for (int count = 0; count < n; count++)
{
for (int i = 0; i < lastIndex; i++)
{
int j = i + 1;
E lhs = sequence.get(i);
E rhs = sequence.get(j);
if (cmp.compare(lhs, rhs) < 0) swap(sequence, i, j);
}
}
}
public String toString()
{
return Sorters.BAD_BUBBLE_SORTER;
}
}
class BetterBubbleSorter extends BadBubbleSorter
{
// Exercise 1b: Implement bubble sort again. Make it better this time.
// Specifically: On each pass, do one fewer comparison than before.
protected <E> void sortMethod(List<E> sequence, Comparator<E> cmp)
{
}
public String toString()
{
return Sorters.BETTER_BUBBLE_SORTER;
}
}
// Best: not Bestest, MoreBestest, or MostBestest. (But it's not final.)
class BestBubbleSorter extends BetterBubbleSorter
{
// Exercise 1c: Implement bubble sort one more time. Make it even better.
// Specifically: Stop as soon as you know you're done.
protected <E> void sortMethod(List<E> sequence, Comparator<E> cmp)
{
}
public final String toString()
{
return Sorters.BEST_BUBBLE_SORTER;
}
}
// Insertion Sort
final class InsertionSorter extends CountingExchangeSorter
{
// Sort an unordered sequence...
protected <E> void sortMethod(List<E> sequence, Comparator<E> cmp)
{
// Exercise 2a: Implement insertion sort.
}
// Insert into a sorted multiset...
public <E> void insertIntoMultiset(E element, List<E> sortedSeq, Comparator<E> cmp)
{
// Exercise 2b: Write code that inserts an element into a multiset (duplicates allowed).
// Assume that the list passed to the method is in sorted order.
}
public final <E extends Comparable<E>>
void insertIntoMultiset(E element, List<E> sortedSeq)
{
Comparator<E> cmp = (E lhs, E rhs) -> lhs.compareTo(rhs);
insertIntoMultiset(element, sortedSeq, cmp);
}
public final <E extends Comparable<E>>
void insertIntoMultisetReverse(E element, List<E> sortedSeq)
{
Comparator<E> cmp = (E lhs, E rhs) -> rhs.compareTo(lhs);
insertIntoMultiset(element, sortedSeq, cmp);
}
// Insert into a sorted set...
public <E> boolean insertIntoSet(E element, List<E> sortedSeq, Comparator<E> cmp)
{
// Exercise 2c: Write code that inserts an element into a set (duplicates not allowed).
// Assume that the list passed to the method is in sorted order.
return false; // Modify this line if necessary.
}
public final <E extends Comparable<E>>
boolean insertIntoSet(E element, List<E> sortedSeq)
{
Comparator<E> cmp = (E lhs, E rhs) -> lhs.compareTo(rhs);
insertIntoSet(element, sortedSeq, cmp);
return false;
}
public final <E extends Comparable<E>>
boolean insertIntoSetReverse(E element, List<E> sortedSeq)
{
Comparator<E> cmp = (E lhs, E rhs) -> rhs.compareTo(lhs);
insertIntoSet(element, sortedSeq, cmp);
return false;
}
public String toString()
{
return Sorters.INSERTION_SORTER;
}
}
// Quick Sort (What about Quicker? Quickest? MostQuickest?)
class QuickSorter extends CountingExchangeSorter
{
protected <E> void sortMethod(List<E> sequence, Comparator<E> cmp)
{
// Exercise 3: Implement quick sort.
}
public String toString()
{
return Sorters.QUICK_SORTER;
}
}
// Merge Sort
final class MergeSorter extends CountingSorter
{
protected <E> void sortMethod(List<E> sequence, Comparator<E> cmp)
{
// Exercise 4: Implement merge sort.
}
public String toString()
{
return Sorters.MERGE_SORTER;
}
}
// Using Java's Collections.sort method to sort.
final class CollectionsSorter extends CountingSorter
{
protected <E> void sortMethod(List<E> sequence, Comparator<E> cmp)
{
Collections.sort(sequence, cmp);
}
public String toString()
{
return Sorters.COLLECTIONS_SORTER;
}
}
/*
* n. permuter 1. One who permutes.
*/
final class Permuter
{
public static <E> List<List<E>> getAllPermutations(Set<E> set)
{
ArrayList<E> list = new ArrayList<E>(set.size());
for (E element : set) list.add(element);
return getAllPermutations(list, 0);
}
public static <E> List<List<E>> getAllPermutations(List<E> list)
{
return getAllPermutations(list, 0);
}
private static <E> List<List<E>> getAllPermutations(List<E> list, int headIndex)
{
final int permutationLength = list.size() - headIndex;
List<List<E>> permutations = new ArrayList<List<E>>();
if (permutationLength > 0)
{
E theHeadElement = list.get(headIndex);
List<List<E>> permutationsOfTail = getAllPermutations(list, headIndex + 1);
for (List<E> permutationOfTail : permutationsOfTail)
{
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);
}
permutations.add(newPermutation);
}
}
}
else
{
// There is one way to arrange no elements.
permutations.add(new ArrayList<E>());
}
return permutations;
}
}
/* A Statistics Utility */
final class Statistics
{
public static Double getMin(List<Double> values)
{
final int n = values.size();
if (n == 0) return null;
Double smallest = values.get(0);
for (int i = 1; i < n; i++)
{
Double value = values.get(i);
if (value < smallest)
smallest = value;
}
return smallest;
}
public static Double getMax(List<Double> values)
{
final int n = values.size();
if (n == 0) return null;
Double largest = values.get(0);
for (int i = 1; i < n; i++)
{
Double value = values.get(i);
if (value > largest)
largest = value;
}
return largest;
}
public static Double getSum(List<Double> values)
{
Double sum = 0.0;
for (Double value : values) sum += value;
return sum;
}
public static Double getAvg(List<Double> values)
{
return getSum(values) / values.size();
}
public static Double getStdDev(List<Double> values, Double avg)
{
final List<Double> diffsSquared = new ArrayList<Double>(values.size());
for (Double value : values )
{
Double diff = avg - value;
Double diffSquared = diff * diff;
diffsSquared.add(diffSquared);
}
return Math.sqrt(getAvg(diffsSquared));
}
public static Double getStdDev(List<Double> values)
{
return getStdDev(values, getAvg(values));
}
}
/* Count, Min, Max, Avg, SD (standard deviation)
*
* Count is not one of the Gang of Four statistics, but it's good to know.
*
* SEE: Stanford Lecture - Don Knuth: The Analysis of Algorithms
* Donald Knuth recreates his very first lecture taught at Stanford University.
* https://www.youtube.com/watch?v=jmcSzzN1gkc (JUMP TO 25:45)
*/
final class DataSet
{
private final String description;
private final List<Double> values;
private Double min = null, max = null, avg = null, stdDev = null, sum = 0.0;
private boolean statsAreCurrent = true;
public DataSet(String description, int initialCapacity)
{
this.description = description;
values = new ArrayList<Double>(initialCapacity);
}
public DataSet(String description)
{
this.description = description;
values = new LinkedList<Double>();
}
public final void add(Integer value)
{
add(value.doubleValue());
}
public final void add(Double value)
{
statsAreCurrent = false;
values.add(value);
sum += value;
if (values.size() == 1)
{
min = value;
max = value;
}
else
{
if (value < min) min = value;
if (value > max) max = value;
}
}
private void analyzeThis()
{
if (!statsAreCurrent)
{
avg = sum / values.size();
stdDev = Statistics.getStdDev(values, avg);
statsAreCurrent = true;
}
}
public final String toString()
{
List<DataSet> listOfThis = new LinkedList<DataSet>();
listOfThis.add(this);
return DataSet.toString(listOfThis);
}
private static String toFixed(Double d)
{
return String.format("%.1f", d);
}
private static String toFixed(String string)
{
final int length = 6;
return String.format("%1$" + length + "s", string);
}
public static String toString(List<DataSet> dataSets)
{
String description = "";
final String SEP = " ";
for (DataSet ds : dataSets)
{
description = ds.description;
ds.analyzeThis();
}
StringBuilder sb = new StringBuilder();
sb.append("Dataset:" + SEP + description + "\n");
sb.append("\n Count:");
for (DataSet ds : dataSets) sb.append(SEP + toFixed(((Integer)ds.values.size()).toString()));
sb.append("\n Min:");
for (DataSet ds : dataSets) sb.append(SEP + toFixed(toFixed(ds.min)));
sb.append("\n Max:");
for (DataSet ds : dataSets) sb.append(SEP + toFixed(toFixed(ds.max)));
sb.append("\n Avg:");
for (DataSet ds : dataSets) sb.append(SEP + toFixed(toFixed(ds.avg)));
sb.append("\n SD:");
for (DataSet ds : dataSets) sb.append(SEP + toFixed(toFixed(ds.stdDev)));
sb.append("\n");
return sb.toString();
}
}
/* Mathematicians */
interface MathProfessor
{
<E extends Comparable<E>> void analyze(List<E> sequence);
String getAnalysis();
void nextDataSet();
}
class ExecutionTimeAnalyst implements MathProfessor
{
private final String HR = "********************************\n";
private DataSet executionTimes;
private final List<DataSet> executionTimesDataSets;
private final Sorter sorter;
public ExecutionTimeAnalyst(Sorter sorter)
{
this.sorter = sorter;
executionTimesDataSets = new LinkedList<DataSet>();
}
public <E extends Comparable<E>> void analyze(List<E> sequence)
{
sorter.sort(sequence);
Long time = sorter.getElapsedTime();
executionTimes.add(time.doubleValue() / 1000);
}
public void nextDataSet()
{
executionTimes = new DataSet("Execution Time (microseconds)");
executionTimesDataSets.add(executionTimes);
}
protected final int getComparisonCount()
{
return sorter.getComparisonCount();
}
protected final int getExchangeCount()
{
return sorter.getExchangeCount();
}
public String getAnalysis()
{
return HR + sorter.toString() + "\n\n" +
DataSet.toString(executionTimesDataSets) + "\n";
}
}
class ComparisonCountAnalyst extends ExecutionTimeAnalyst
{
private DataSet comparisons;
private final List<DataSet> comparisonsDataSets;
public ComparisonCountAnalyst(Sorter sorter)
{
super(sorter);
comparisonsDataSets = new LinkedList<DataSet>();
}
public <E extends Comparable<E>> void analyze(List<E> sequence)
{
super.analyze(sequence);
comparisons.add(getComparisonCount());
}
public void nextDataSet()
{
super.nextDataSet();
comparisons = new DataSet("Number of Comparisons");
comparisonsDataSets.add(comparisons);
}
public String getAnalysis()
{
return super.getAnalysis() +
DataSet.toString(comparisonsDataSets) + "\n";
}
}
final class ExchangeCountAnalyst extends ComparisonCountAnalyst
{
private DataSet exchanges;
private final List<DataSet> exchangesDataSets;
public ExchangeCountAnalyst(Sorter sorter)
{
super(sorter);
exchangesDataSets = new LinkedList<DataSet>();
}
public <E extends Comparable<E>> void analyze(List<E> sequence)
{
super.analyze(sequence);
exchanges.add(getExchangeCount());
}
public void nextDataSet()
{
super.nextDataSet();
exchanges = new DataSet("Number of Exchanges");
exchangesDataSets.add(exchanges);
}
public final String getAnalysis()
{
return super.getAnalysis() +
DataSet.toString(exchangesDataSets) + "\n";
}
}
/* Educational Entities */
final class StanfordUniversity
{
public static MathProfessor getProfessor(Sorter sorter)
{
if (sorter.countsComparisons())
{
if (sorter.countsExchanges())
return new ExchangeCountAnalyst(sorter);
else
return new ComparisonCountAnalyst(sorter);
}
else
{
return new ExecutionTimeAnalyst(sorter);
}
}
}
final class ComputerScienceStudent
{
private Sorter sorter;
private final MathProfessor donKnuth;
public ComputerScienceStudent(Sorter sorter)
{
this.sorter = sorter;
donKnuth = StanfordUniversity.getProfessor(sorter);
}
public final void analyze(List<List<String>> permutations)
{
donKnuth.nextDataSet();
for (List<String> permutation : permutations)
{
// Analyzing a permutation PERMUTES the permutation, and we
// will need to use permutations again, so make a copy and
// analyze the copy instead of the original permutation.
List<String> copy = new ArrayList<String>(permutation.size());
for (String element : permutation)
{
copy.add(element);
}
donKnuth.analyze(copy);
}
}
public final String getResults()
{
return donKnuth.getAnalysis();
}
}
final class TeachingAssistant
{
private final List<List<List<String>>> setsOfAllPermutations;
private final SortedSet<String> sortedSet = new TreeSet<String>();
public TeachingAssistant(String[] args)
{
final int n = args.length;
setsOfAllPermutations = new ArrayList<List<List<String>>>(n);
List<List<String>> permutations;
for (String string : args)
{
sortedSet.add(string);
permutations = Permuter.getAllPermutations(sortedSet);
setsOfAllPermutations.add(permutations);
}
}
public String getSuperset()
{
String superset = "SUPERSET:";
for (String element : sortedSet)
{
superset += " " + element;
}
return superset;
}
public final void createExercisesFor(List<ComputerScienceStudent> students)
{
for (List<List<String>> setOfAllPermutations : setsOfAllPermutations)
{
for (ComputerScienceStudent student : students)
{
student.analyze(setOfAllPermutations);
}
}
}
}
// The Main Program: It's about time...
final public class AnalaysisOfSortingAlgorithms
{
// What kind of class doesn't have students?
private static List<ComputerScienceStudent> students;
// All sorts of sorters for students to study.
private static Sorter[] allSortsOfSorters =
{
new CollectionsSorter(),
new BadBubbleSorter(), new BetterBubbleSorter(), new BestBubbleSorter(),
new InsertionSorter(), new MergeSorter(), new QuickSorter(),
};
public static void main(String[] args)
{
// Recruit the students.
students = new LinkedList<ComputerScienceStudent>();
for (Sorter sorter : allSortsOfSorters)
{
// Assign a sorter to each student.
students.add(new ComputerScienceStudent(sorter));
}
// Hire a TA and put her to work creating exercises for the students.
TeachingAssistant annaKarlin = new TeachingAssistant(args);
annaKarlin.createExercisesFor(students);
// Print the results.
System.out.println(annaKarlin.getSuperset() + "\n");
for (ComputerScienceStudent student : students)
{
System.out.println(student.getResults());
}
// finis ... (Retire early and write books.)
}
}
