I'm reading chapter about sorting in Sedgewick's "Algorithms". Along the way I wrote 3 basic algorithms for sorting: selection, insertion and shell sort. The book says, that, despite the fact that all three have quadratic worst case complexity, shell sort should be much faster than insertion sort on random data. In the book they get 600x performance boost.
But I get following multipliers (almost do not change with increasing of array size) on my laptop:
- selection: 5.5x
- insertion: 1x
- shell: 1.8x !
The question that bothers me is - why shell sort is almost two times slower, than insertion sort?!
I guess, something is wrong with my shellsort implementation. But I almost copied it from the book:
class ShellSort extends Sort {
//precalculate sequence: 1, 4, 13, 40, 121, 364, 1093, ...
//(3^20 - 1)/2 is enough for any array I sort
private static final int[] SEQUENCE = new int[20];
static {
for(int i = 1; i <= SEQUENCE.length; i++)
SEQUENCE[i - 1] = (int)(Math.pow(3, i) - 1) / 2;
}
public void sort(int[] a) {
int length = a.length;
int seqLen = SEQUENCE.length;
int nth;
int j;
for(int seqi = seqLen - 1; seqi >= 0; seqi--) {
if(SEQUENCE[seqi] < length / 3) {
nth = SEQUENCE[seqi];
for(int n = 0; n < length; n+=nth) {
j = n;
while(j > 0 && a[j] < a[j - nth]) {
exch(a, j, j-nth);
j -= nth;
}
}
}
}
}
}
Rest of the code for those, who would like to run test on their machine (doubling array size test with JVM heat up has no significant effect on the results, so this simple test is good enough for N > ~ 200 000).
main:
int N = 500_000;
Random rand = new Random();
int[] a = new int[N];
for(int i = 0; i < N; i++)
a[i] = rand.nextInt();
//insertion sort
int[] aCopy = Arrays.copyOf(a, a.length);
long start = System.nanoTime();
new InsertionSort().sort(aCopy);
System.out.println("insert:\t" + (System.nanoTime() - start));
//shell sort
aCopy = Arrays.copyOf(a, a.length);
start = System.nanoTime();
new ShellSort().sort(aCopy);
System.out.println("shell:\t" + (System.nanoTime() - start));
InsertionSort and Sort classes:
class InsertionSort extends Sort {
public void sort(int[] a) {
int length = a.length;
int j;
int x;
for(int i = 1; i < length; i++) {
j = i;
x = a[i];
while(j > 0 && x < a[j-1]) {
a[j] = a[--j];
}
a[j] = x;
}
}
}
abstract class Sort {
abstract public void sort(int[] a);
protected static final void exch(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}