Introduction
Shellsort is an interesting sort algorithm that I came across a while ago. The most amazing part is that a different gap sequences can significantly improve the speed of the algorithm. I did a few reading (not extensively) and it seem that Tokuda's sequence is recommendeded for practical applications.
Another interesting part is that the sequence of ratio 2.20~2.25 tends to be more efficient. So I did a small search thought the sequence of ratio from 2.20 to 2.50 and tried to search for which ratio that can performance averagely good. I come across this ratio: 2.48 that seem to averagely performance good in many different trials.
Then, I came up with sequence generator: 2.48k-1 (lets call it 248 sequence) and tried to compare it with Tokuda's sequence. It turned out that they averagely equal in speed. 248 sequences tends to use slightly more number of comparison.
Benchmark Methods
- Instead of using millisecond as a measurement, I use the number of comparision and number of swap.
- I did 100 trials each on the following array size (50,000; 100,000; 200,000; 300,000; 500,000; 1,000,000) and keep track of their number of comparison and number of swap.
- The following is my data (here in CSV format).
- Full Code: http://pastebin.com/pm7Akpqh
Questions
I know I might be wrong that is why I come here to seek for more opinion from more experienced programmers here. In case you don't get the question, here is my question in short:
- Does 2.48k-1 is as good as Tokuda's sequence?
- If it is as good as Tokuda's sequence, would it be more practical to use it since 2.48k-1 sequence is easier to generate than Tokuda's sequence.
248 Sequence:
ROUNDUP ( 2.48(k-1) )
eg: 1, 3, 7, 16, 38, 94, 233, 577, 1431, 3549, 8801, 21826, ...
Tokuda's Sequence
ROUNDUP ( (9k - 4k) / (5 * 4k - 1) )
eg: 1, 4, 9, 20, 46, 103, 233, 525, 1182, 2660, 5985, 13467, ...
As @woolstar suggested me to also test with edge cases such as reversed and sorted. As expectedly, 248 sequence is faster in edge cases because 248 sequence gap is larger so it moves the inverse faster.
Shellsort Implementation
public static int compare = 0;
public static int swap = 0;
public static bool greaterthan(int a, int b) {
compare++;
return a > b;
}
public static int shellsort(int[] a, int[] gaps) {
// For keeping track of number of swap and comparison
compare = 0;
swap = 0;
int temp, gap, i, j;
// Finding a gap that is smaller than the length of the array
int gap_index = gaps.Length - 1;
while (gaps[gap_index] > a.Length) gap_index--;
while (gap_index >= 0) {
// h-sorting
gap = gaps[gap_index];
for (i = gap; i < a.Length; i++) {
temp = a[i];
for(j = i; (j >= gap) && (greaterthan(a[j - gap], temp)); j -= gap) {
a[j] = a[j - gap];
}
// swapping
a[j] = temp;
swap++;
}
gap_index--;
}
return compare;
}