I have this implementation of Quicksort for strings. The algorithm sorts the requested range by first character, then by second, third, and so on. (Please, do not confuse this with radix sort; it is not.)
The pseudocode might look like this:
# Public API
Sort(R):
Sort(R, 0)
Sort(R, len):
if |R| < 2 return R
R_p = all strings of length 'len'
select pivot X from R
R< = all strings S for which S[len] < X[len]
R= = all strings S for which S[len] = X[len]
R> = all strings S for which S[len] > X[len]
R< = Sort(R<, len)
R= = Sort(R=, len + 1) # Note 'len + 1'!
R> = Sort(R>, len)
return < R_p, R<, R=, R> > # Concatenate sorted sublists
StringQuicksort.java:
package net.coderodde.util;
import java.util.Arrays;
import java.util.Random;
/**
* This class implements a Quicksort for strings.
*
* @author Rodion "rodde" Efremov
* @version (Dec 17, 2015)
*/
public class StringQuicksort {
private static final int ALPHABET_SIZE = 26;
public static void sort(String[] array) {
sort(array, 0, array.length);
}
public static void sort(String[] array, int fromIndex, int toIndex) {
if (toIndex - fromIndex < 2) {
return;
}
sortImpl(array, fromIndex, toIndex, 0);
}
private static void sortImpl(String[] array,
int fromIndex,
int toIndex,
int stringLength) {
int rangeLength = toIndex - fromIndex;
if (rangeLength < 2) {
return;
}
int finger = fromIndex;
// Put all strings of length 'stringLength' to the beginning of the
// requested sort range.
for (int index = fromIndex; index < toIndex; ++index) {
String current = array[index];
if (current.length() == stringLength) {
String tmp = array[finger];
array[finger] = current;
array[index] = tmp;
++finger;
}
}
fromIndex = finger;
// Choose a pivot string by median.
String probeLeft = array[fromIndex];
String probeRight = array[toIndex - 1];
String probeMiddle = array[fromIndex + rangeLength >> 1];
String pivot = median(probeLeft, probeMiddle, probeRight);
// Process strings S for which S[stringLength] < X[stringLength].
for (int index = fromIndex; index < toIndex; ++index) {
String current = array[index];
if (current.charAt(stringLength) < pivot.charAt(stringLength)) {
String tmp = array[finger];
array[finger] = current;
array[index] = tmp;
++finger;
}
}
sortImpl(array, fromIndex, finger, stringLength);
fromIndex = finger;
int processed = 0;
for (int index = fromIndex; index < toIndex; ++index) {
String current = array[index];
if (current.charAt(stringLength) == pivot.charAt(stringLength)) {
String tmp = array[finger];
array[finger] = current;
array[index] = tmp;
++finger;
}
}
sortImpl(array, fromIndex, finger, stringLength + 1);
sortImpl(array, finger, toIndex, stringLength);
}
private static String median(String a, String b, String c) {
if (a.compareTo(b) <= 0) {
if (c.compareTo(a) <= 0) {
return a;
}
return b.compareTo(c) <= 0 ? b : c;
}
if (c.compareTo(b) <= 0) {
return b;
}
return a.compareTo(c) <= 0 ? a : c;
}
public static void main(final String... args) {
long seed = System.nanoTime();
Random random = new Random(seed);
String[] array1 = createRandomStringArray(400_000, 20, random);
String[] array2 = array1.clone();
System.out.println("Seed = " + seed);
long startTime = System.nanoTime();
Arrays.sort(array1);
long endTime = System.nanoTime();
System.out.format("Arrays.sort in %.2f milliseconds.\n",
(endTime - startTime) / 1e6);
startTime = System.nanoTime();
StringQuicksort.sort(array2);
endTime = System.nanoTime();
System.out.format("StringQuicksort.sort in %.2f milliseconds.\n",
(endTime - startTime) / 1e6);
System.out.println("Arrays equal: " + Arrays.equals(array1, array2));
}
private static String[] createRandomStringArray(int size,
int maxLength,
Random random) {
String[] ret = new String[size];
for (int i = 0; i < size; ++i) {
ret[i] = randomString(maxLength, random);
}
return ret;
}
private static String randomString(int maxLength, Random random) {
int length = random.nextInt(maxLength + 1);
StringBuilder sb = new StringBuilder(length);
for (int i = 0; i < length; ++i) {
sb.append((char)('a' + random.nextInt(ALPHABET_SIZE)));
}
return sb.toString();
}
}
Some performance figures:
Seed = 110240813919222
Arrays.sort in 823.63 milliseconds.
StringQuicksort.sort in 441.81 milliseconds.
Arrays equal: true
What can I improve? Performance? Coding style? API? Naming? Any critique much appreciated!
