/* SortsOfSorters
* By: John P. Spurgeon
* Updated: 21 April 2018
* - Bug fix: Instance variable swapCount needs to be reset in sort method.
* - Change: Removed the prefix "actually" from method names.
* At: http://scribbledecobble.blogspot.com/2018/04/sorts-of-sorters.html
*
* Classic Sequences to Sort
*
* 1. A Multiset
* Sequence: c a b d d a b d a d
* See: TAOCP, vol. 3, sec. 5.1.2
*
* 2. A Set
* Sequence: 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.List;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Collections;
/* Counters */
interface ComparisonCounter
{
int getComparisonCount();
}
interface ExchangeCounter
{
int getExchangeCount();
}
// meter: n. a device that measures and records the quantity, degree, or rate of something.
interface SortMeter extends ComparisonCounter, ExchangeCounter
{
boolean countsComparisons();
boolean countsExchanges();
}
// Note: lhs => left hand side, rhs => right hand side.
final class CountingComparator<E> implements Comparator<E>, ComparisonCounter
{
private Comparator<E> cmp;
private int comparisonCount = 0;
public CountingComparator(Comparator<E> cmp)
{
this.cmp = cmp;
}
public final int compare(E lhs, E rhs)
{
comparisonCount++;
return cmp.compare(lhs, rhs);
}
public final int getComparisonCount()
{
return comparisonCount;
}
}
/* 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).
*/
class Sorters
{
public static final String
ABSTRACTED_SORTER = "Abstracted Sorter",
ABSTRACTED_EXCHANGE_SORTER = "Abstracted Exchange Sorter",
BAD_BUBBLE_SORTER = "Bad Bubble Sorter",
BETTER_BUBBLE_SORTER = "Better Bubble Sorter",
BEST_BUBBLE_SORTER = "Best Bubble Sorter",
COLLECTIONS_SORTER = "Collections Sorter",
COMPARISON_COUNTING_SORTER = "Comparison Counting Sorter",
COMPARISON_EXCHANGE_COUNTING_SORTER = "Comparison/Exchange Counting Sorter",
INSERTION_SORTER = "Insertion Sorter",
MERGE_SORTER = "Merge Sorter",
QUICK_SORTER = "Quick Sorter";
}
/* Abstract Sorters */
abstract class Sorter implements SortMeter
{
protected abstract <E> void sortMethod(List<E> sequence, Comparator<E> cmp);
public <E> void sort(List<E> sequence, Comparator<E> cmp)
{
this.sortMethod(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);
}
// Sorter is abstracted (withdrawn from the contemplation of present objects),
// because although it implements the SortMeter interface, it doesn't actually
// count comparisons or exchanges; it has a habitually forgetful disposition.
public boolean countsComparisons() { return false; }
public boolean countsExchanges() { return false; }
public int getComparisonCount() { return -1; }
public int getExchangeCount() { return -1; }
public String toString()
{
return Sorters.ABSTRACTED_SORTER;
}
}
abstract class ComparisonCountingSorter extends Sorter
{
private int comparisonCount = 0;
public final <E> void sort(List<E> sequence, Comparator<E> cmp)
{
CountingComparator<E> cc = new CountingComparator<E>(cmp);
this.sortMethod(sequence, cc);
comparisonCount = cc.getComparisonCount();
}
public final boolean countsComparisons()
{
return true;
}
public final int getComparisonCount()
{
return comparisonCount;
}
public String toString()
{
return Sorters.COMPARISON_COUNTING_SORTER;
}
}
abstract class ExchangeSorter extends Sorter
{
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.ABSTRACTED_EXCHANGE_SORTER;
}
}
abstract class ComparisonExchangeCountingSorter extends ExchangeSorter
{
private int comparisonCount = 0, swapCount = 0;
protected final <E> void swap(List<E> sequence, int i, int j)
{
super.swap(sequence, i, j);
swapCount++;
}
public final <E> void sort(List<E> sequence, Comparator<E> cmp)
{
swapCount = 0;
CountingComparator<E> cc = new CountingComparator<E>(cmp);
this.sortMethod(sequence, cc);
comparisonCount = cc.getComparisonCount();
}
public final boolean countsComparisons()
{
return true;
}
public final int getComparisonCount()
{
return comparisonCount;
}
public final boolean countsExchanges()
{
return true;
}
public final int getExchangeCount()
{
return swapCount;
}
public String toString()
{
return Sorters.COMPARISON_EXCHANGE_COUNTING_SORTER;
}
}
/* Bubble Sort */
class BadBubbleSorter extends ComparisonExchangeCountingSorter
{
// 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)
{
final int n = sequence.size();
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);
}
lastIndex--;
}
}
public String toString()
{
return Sorters.BETTER_BUBBLE_SORTER;
}
}
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)
{
final int n = sequence.size();
int lastIndex = n - 1;
for (int count = 0; count < n; count++)
{
int exchangeCount = getExchangeCount();
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);
}
if (getExchangeCount() == exchangeCount) break;
lastIndex--;
}
}
public final String toString()
{
return Sorters.BEST_BUBBLE_SORTER;
}
}
/* Insertion Sort */
final class InsertionSorter extends ComparisonExchangeCountingSorter
{
/* Sorting an unordered sequence. */
protected <E> void sortMethod(List<E> sequence, Comparator<E> cmp)
{
// Exercise 2a: Implement insertion sort.
final int n = sequence.size();
for (int i = 1; i < n; i++)
{
for (int j = i; j > 0; j--)
{
int k = j - 1;
E rhs = sequence.get(j);
E lhs = sequence.get(k);
if (cmp.compare(lhs, rhs) > 0)
swap(sequence, k, j);
}
}
}
/* Inserting 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.
int i = 0;
for (E nextElement : sortedSeq)
{
if (cmp.compare(element, nextElement) < 0)
i++;
else if (cmp.compare(element, nextElement) >= 0)
break;
}
sortedSeq.add(i, element);
}
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);
}
/* Inserting 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.
int i = 0;
for (E nextElement : sortedSeq)
{
if (cmp.compare(element, nextElement) < 0)
i++;
else if (cmp.compare(element, nextElement) == 0)
return false;
else
break;
}
sortedSeq.add(i, element);
return true;
}
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 */
final class QuickSorter extends ComparisonExchangeCountingSorter
{
// lower is inclusive, upper is exclusive
private <E> void quickSort(List<E> sequence, Comparator<E> cmp, int lower, int upper)
{
if (upper - lower <= 1)
return;
int pivot = lower;
final E pivotValue = sequence.get(pivot);
int j = pivot + 1;
for (int i = j; i < upper; i++)
{
final int compareResult = cmp.compare(sequence.get(i), pivotValue);
if (compareResult <= 0)
{
if (i > j)
swap(sequence, i, j);
if (compareResult < 0)
swap(sequence, pivot, j);
pivot = j++;
}
}
quickSort(sequence, cmp, lower, pivot);
quickSort(sequence, cmp, j, upper);
}
protected <E> void sortMethod(List<E> sequence, Comparator<E> cmp)
{
// Exercise 3: Implement quick sort.
quickSort(sequence, cmp, 0, sequence.size());
}
public String toString()
{
return Sorters.QUICK_SORTER;
}
}
/* Merge Sort */
final class MergeSorter extends ComparisonCountingSorter
{
private <E> void merge(List<E> list, Comparator<E> cmp, int lower, int middle, int upper)
{
final int n = upper - lower;
List<E> buffer = new ArrayList<E>(n);
int i, j, k;
for (i = 0; i < n; i++)
buffer.add(null);
i = lower; j = middle; k = 0;
while (i < middle && j < upper)
{
int compareResult = cmp.compare(list.get(i), list.get(j));
if (compareResult <= 0)
buffer.set(k++, list.get(i++));
if (compareResult >= 0)
buffer.set(k++, list.get(j++));
}
while (i < middle)
buffer.set(k++, list.get(i++));
while (j < upper)
buffer.set(k++, list.get(j++));
for (i = 0; i < n; i++)
list.set(lower + i, buffer.get(i));
}
private <E> void mergeSort(List<E> list, Comparator<E> cmp, int lower, int upper)
{
final int n = upper - lower;
if (n <= 1)
return;
int middle = lower + (n / 2);
mergeSort(list, cmp, lower, middle);
mergeSort(list, cmp, middle, upper);
merge(list, cmp, lower, middle, upper);
}
protected <E> void sortMethod(List<E> sequence, Comparator<E> cmp)
{
// Exercise 4: Implement merge sort.
mergeSort(sequence, cmp, 0, sequence.size());
}
public String toString()
{
return Sorters.MERGE_SORTER;
}
}
/* A sorter that uses Java's Collections.sort method to sort. */
final class CollectionsSorter extends ComparisonCountingSorter
{
protected <E> void sortMethod(List<E> sequence, Comparator<E> cmp)
{
Collections.sort(sequence, cmp);
}
public String toString()
{
return Sorters.COLLECTIONS_SORTER;
}
}
/* String Utilities */
class StringTester
{
public static boolean isNumeric(String s)
{
try
{
double d = Double.parseDouble(s);
}
catch(NumberFormatException nfe)
{
return false;
}
return true;
}
public static boolean areNumeric(String[] strings)
{
if (strings == null || strings.length == 0)
return false;
else
for (String s : strings)
if (!isNumeric(s))
return false;
return true;
}
}
class StringSorter {
public static List<Double> sortAsNumbers(String[] strings, Sorter sorter) {
List<Double> list = new LinkedList<Double>();
for (String s : strings) list.add(Double.parseDouble(s));
sorter.sort(list);
return list;
}
public static List<Double> sortAsNumbersReverse(String[] strings, Sorter sorter) {
List<Double> list = new ArrayList<Double>();
for (String s : strings) list.add(Double.parseDouble(s));
sorter.sortReverse(list);
return list;
}
public static List<String> sortAsStrings(String[] strings, Sorter sorter) {
List<String> list = new ArrayList<String>();
for (String s : strings) list.add(s);
sorter.sort(list);
return list;
}
public static List<String> sortAsStringsReverse(String[] strings, Sorter sorter) {
List<String> list = new LinkedList<String>();
for (String s : strings) list.add(s);
sorter.sortReverse(list);
return list;
}
public static List<Double> insertNumbersIntoSet(String[] strings, InsertionSorter sorter) {
List<Double> list = new LinkedList<Double>();
for (String s : strings) sorter.insertIntoSet(Double.parseDouble(s), list);
return list;
}
public static List<Double> insertNumbersIntoMultiset(String[] strings, InsertionSorter sorter) {
List<Double> list = new ArrayList<Double>();
for (String s : strings) sorter.insertIntoMultiset(Double.parseDouble(s), list);
return list;
}
public static List<String> insertStringsIntoSet(String[] strings, InsertionSorter sorter) {
List<String> list = new ArrayList<String>();
for (String s : strings) sorter.insertIntoSet(s, list);
return list;
}
public static List<String> insertStringsIntoMultiset(String[] strings, InsertionSorter sorter) {
List<String> list = new LinkedList<String>();
for (String s : strings) sorter.insertIntoMultiset(s, list);
return list;
}
}
/* Main Program: SortsOfSorters */
public class SortsOfSorters
{
private static <E> void print(List<E> sequence, SortMeter counter, String label)
{
System.out.println(counter);
System.out.print(label + ":");
for (E element : sequence) System.out.print(" " + element);
System.out.println();
if (counter.countsComparisons())
System.out.println("Comparisons: " + counter.getComparisonCount());
if (counter.countsExchanges())
System.out.println("Exchanges: " + counter.getExchangeCount());
System.out.println();
}
public static void main(String[] args)
{
Sorter[] sortsOfSorters = {
new BadBubbleSorter(), new BetterBubbleSorter(), new BestBubbleSorter(),
new InsertionSorter(), new MergeSorter(), new QuickSorter(),
new CollectionsSorter(),
};
if (StringTester.areNumeric(args))
{
for (Sorter sorter : sortsOfSorters)
{
print(StringSorter.sortAsNumbers(args, sorter), sorter, "Sorted");
print(StringSorter.sortAsNumbersReverse(args, sorter), sorter, "Reversed");
if (sorter.toString().equals(Sorters.INSERTION_SORTER))
{
InsertionSorter iSrtr = (InsertionSorter) sorter;
print(StringSorter.insertNumbersIntoSet(args, iSrtr), iSrtr, "Set");
print(StringSorter.insertNumbersIntoMultiset(args, iSrtr), iSrtr, "Multiset");
}
}
}
else
{
for (Sorter sorter : sortsOfSorters)
{
print(StringSorter.sortAsStrings(args, sorter), sorter, "Sorted");
print(StringSorter.sortAsStringsReverse(args, sorter), sorter, "Reversed");
if (sorter.toString().equals(Sorters.INSERTION_SORTER))
{
InsertionSorter iSrtr = (InsertionSorter) sorter;
print(StringSorter.insertStringsIntoSet(args, iSrtr), iSrtr, "Set");
print(StringSorter.insertStringsIntoMultiset(args, iSrtr), iSrtr, "Multiset");
}
}
}
}
}
