(See the next iteration.)
I have this adaptive counting sort for integer arrays. Basically, it maintains a doubly-linked list of nodes. Each node knows its integer \$a_i\$ and contains the counter describing the number of \$a_i\$ encountered so far in the range. As you might know, the running time of counting sort is \$\mathcal{O}(n + k)\$, where \$k = \max a_i - \min a_i\$ is the "width" of the input array, which limits its applicability in general case. The linked list structure allows sorting even for large values of \$k\$. Also, as an optimization, the adaptive version knows the previous node incremented, which allows it to adapt to "closeness" of integers in the array.
The running time, in my opinion, varies between \$\Omega(n)\$ and \$\mathcal{O}(n^2)\$, although I don't have a formal proof. The space requirements are, however, easy to calculate: its the amount of distinct integers in the requested range.
As that adaptive sort seems to have quadratic running time in the worst case, I don't hope it to be comparable to java.util.Arrays.sort(int[]).
The included demonstration, however, compares my sort against an optimized insertion sort (called "straight insertion sort" as far as I can remember) that minimizes the number of assignments. I won't include all information that the included demonstration prints, but the total running time is of order:
Total insertion sort time: 29091 milliseconds. Total counting sort time: 4595 milliseconds.
In the demo, I considered two types of arrays: arrays with small number of distinct elements, and presorted arrays with small number of runs.
I know that intuition is not as good as a proof, yet it is a good starting point. If you plot in \$x,y\$ - plane points \$(i, a_i)\$, and then "draw" the curve through them, the intuition seems to be that the "smoother" the curve, the higher is performance of my implementation.
net.coderodde.util.sorting.CountingSort.java:
package net.coderodde.util.sorting;
/**
* This class implements an adaptive counting sort that adapts to the input.
*
* @author Rodion "rodde" Efremov
* @version 1.6
*/
public class CountingSort {
/**
* Sorts the entire input integer array.
*
* @param array the integer array to sort.
*/
public static void sort(int[] array) {
sort(array, 0, array.length);
}
/**
* Sorts the range {@code array[fromIndex], array[fromIndex + 1], ...,
* array[toIndex - 2], array[toIndex - 1]}.
*
* @param array the array containing the range to sort.
* @param fromIndex the starting, inclusive range index.
* @param toIndex the ending, exclusive range index.
*/
public static void sort(int[] array, int fromIndex, int toIndex) {
if (toIndex - fromIndex < 2) {
return;
}
int lastElement = array[fromIndex];
Node head = new Node(lastElement);
Node tail = head;
Node last = head;
for (int i = fromIndex + 1; i < toIndex; ++i) {
int currentElement = array[i];
if (currentElement < lastElement) {
Node tmp = last.prev;
while (tmp != null && tmp.element > currentElement) {
tmp = tmp.prev;
}
if (tmp == null) {
Node newnode = new Node(currentElement);
newnode.next = head;
head.prev = newnode;
head = newnode;
last = head;
} else if (tmp.element == currentElement) {
tmp.count++;
last = tmp;
} else {
// Insert a new node between 'tmp' and 'tmp.next'.
Node newnode = new Node(currentElement);
newnode.prev = tmp;
newnode.next = tmp.next;
newnode.prev.next = newnode;
newnode.next.prev = newnode;
last = newnode;
}
} else if (currentElement > lastElement) {
Node tmp = last.next;
while (tmp != null && tmp.element < currentElement) {
tmp = tmp.next;
}
if (tmp == null) {
Node newnode = new Node(currentElement);
newnode.prev = tail;
tail.next = newnode;
tail = newnode;
last = newnode;
} else if (tmp.element == currentElement) {
tmp.count++;
last = tmp;
} else {
// Insert a new node between 'tmp.prev' and 'tmp'.
Node newnode = new Node(currentElement);
newnode.prev = tmp.prev;
newnode.next = tmp;
tmp.prev.next = newnode;
tmp.prev = newnode;
last = newnode;
}
} else {
last.count++;
}
lastElement = currentElement;
}
// Now rebuild the requested range.
int index = fromIndex;
for (Node node = head; node != null; node = node.next) {
int element = node.element;
for (int i = 0; i < node.count; ++i) {
array[index++] = element;
}
}
}
private static final class Node {
Node(int element) {
this.element = element;
this.count = 1;
}
Node prev;
Node next;
int element;
int count;
}
}
net.coderodde.util.sorting.Insertionsort.java:
package net.coderodde.util.sorting;
/**
* This class provides a static method for sorting integer arrays using
* insertion sort.
*
* @author Rodion "rodde" Efremov
* @version 1.6
*/
public class Insertionsort {
/**
* Sorts the entire input integer array.
*
* @param array the integer array to sort.
*/
public static void sort(int[] array) {
sort(array, 0, array.length);
}
/**
* Sorts the range {@code array[fromIndex], array[fromIndex + 1], ...,
* array[toIndex - 2], array[toIndex - 1]}.
*
* @param array the array containing the range to sort.
* @param fromIndex the starting, inclusive range index.
* @param toIndex the ending, exclusive range index.
*/
public static void sort(int[] array, int fromIndex, int toIndex) {
for (int i = fromIndex + 1; i < toIndex; ++i) {
int element = array[i];
int j = i;
for (; j > fromIndex && array[j - 1] > element; --j) {
array[j] = array[j - 1];
}
array[j] = element;
}
}
}
Demo.java:
import java.util.Arrays;
import java.util.Random;
import java.util.stream.IntStream;
import net.coderodde.util.sorting.CountingSort;
import net.coderodde.util.sorting.Insertionsort;
public class Demo {
/**
* The number of iterations for each array type.
*/
private static final int OPERATION_COUNT = 30;
/**
* The maximum length of the array to profile against.
*/
private static final int LENGTH = 40000;
/**
* The assumed console window width in characters.
*/
private static final int CONSOLE_WIDTH = 80;
public static void main(final String... args) {
long seed = System.currentTimeMillis();
Random random = new Random(seed);
int[] array1;
int[] array2;
long totalMySort = 0L;
long totalInsertionsort = 0L;
System.out.println("Seed: " + seed);
System.out.println(title("Random arrays"));
//// RANDOM ARRAYS ////
for (int op = 0; op < OPERATION_COUNT; ++op) {
int maxValue = 20 + 20 * op;
System.out.println("Max value: " + maxValue);
array1 = getRandomIntegerArray(LENGTH, maxValue, random);
array2 = array1.clone();
int fromIndex = random.nextInt(LENGTH / 20);
int toIndex = LENGTH - random.nextInt(LENGTH / 20);
long startTime = System.currentTimeMillis();
CountingSort.sort(array1, fromIndex, toIndex);
long endTime = System.currentTimeMillis();
long duration = endTime - startTime;
System.out.println("Counting sort in " + duration
+ " milliseconds.");
totalMySort += duration;
startTime = System.currentTimeMillis();
Insertionsort.sort(array2, fromIndex, toIndex);
endTime = System.currentTimeMillis();
duration = endTime - startTime;
System.out.println("Insertion sort in " + duration
+ " milliseconds.");
System.out.println(bar());
totalInsertionsort += duration;
if (!Arrays.equals(array1, array2)) {
throw new RuntimeException("Sorts did not agree.");
}
}
System.out.println();
System.out.println(title("Presorted arrays"));
//// PRESORTED ARRAYS ////
for (int op = 0; op < OPERATION_COUNT; ++op) {
int runAmount = 20 + 20 * op;
System.out.println("Run amount: " + runAmount);
array1 = getPresortedIntegerArray(LENGTH, runAmount, random);
array2 = array1.clone();
int fromIndex = random.nextInt(LENGTH / 20);
int toIndex = LENGTH - random.nextInt(LENGTH / 20);
long startTime = System.currentTimeMillis();
CountingSort.sort(array1, fromIndex, toIndex);
long endTime = System.currentTimeMillis();
long duration = endTime - startTime;
System.out.println("Counting sort in " + duration
+ " milliseconds.");
totalMySort += duration;
startTime = System.currentTimeMillis();
Insertionsort.sort(array2, fromIndex, toIndex);
endTime = System.currentTimeMillis();
duration = endTime - startTime;
System.out.println("Insertion sort in " + duration
+ " milliseconds.");
System.out.println(bar());
totalInsertionsort += duration;
if (!Arrays.equals(array1, array2)) {
throw new RuntimeException("Sorts did not agree.");
}
}
System.out.println("Total insertion sort time: " +
totalInsertionsort + " milliseconds.");
System.out.println("Total counting sort time: " +
totalMySort + " milliseconds.");
}
private static int[] getRandomIntegerArray(int size,
int maxValue,
Random random) {
return IntStream.range(0, size)
.map((i) -> random.nextInt(maxValue))
.toArray();
}
private static int[] getPresortedIntegerArray(int size,
int runs,
Random random) {
int[] ret = getRandomIntegerArray(size, size, random);
int chunkSize = size / runs + 1;
int chunkId = 0;
for (; chunkId < size / chunkSize; chunkId++) {
Arrays.sort(ret,
chunkSize * chunkId,
Math.min(size, (chunkId + 1) * chunkSize));
}
return ret;
}
private static String title(String s) {
int textWithSpacesLength = s.length() + 2;
int leftBarLength = (CONSOLE_WIDTH - textWithSpacesLength) / 2;
int rightBarLength = CONSOLE_WIDTH - leftBarLength
- textWithSpacesLength;
StringBuilder sb = new StringBuilder(CONSOLE_WIDTH);
for (int i = 0; i < leftBarLength; ++i) {
sb.append('-');
}
sb.append(' ').append(s).append(' ');
for (int i = 0; i < rightBarLength; ++i) {
sb.append('-');
}
return sb.toString();
}
private static String bar() {
StringBuilder sb = new StringBuilder(CONSOLE_WIDTH);
for (int i = 0; i < CONSOLE_WIDTH; ++i) {
sb.append('-');
}
return sb.toString();
}
}
My questions are:
- How should I refactor the implementation in order to increase its maintainability/readability?
- Is there any room for optimization?
- What do you think of this algorithm?
