I spent some time reading (section 2.1 in the Algorithms fourth edition by Robert Sedgewick and Kevin Wayne) and experimenting with the Shell Sort algorithm.
The Shell sort algorithm is an optimized Insertion sort. The idea is to reduce the number of exchanges by presorting elements in sub sequences.
According to Wikipedia, Shell sort is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. Starting with far apart elements, it can move some out-of-place elements into position faster than a simple nearest neighbor exchange.
Donald Shell published the first version of this sort in 1959. The running time of Shell sort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem. The book proposes the following expression: 3x + 1 for the increment sequence: 1, 4, 13, 40, 121, 364, 1093, …
The Shell sort is faster that it counterpart Insertion sort. This is especially true when the number of elements increases. For example, from the console of the Eclipse IDE:
main <<< alg1 ==>Insertion<==
main <<< alg2 ==>Shell<==
main <<< N: 100000
main <<< T: 100
main <<< t1: 3730382.00 ms
main <<< t2: 7312.00 ms
main <<< Shell is 510.17 times faster than Insertion
A set of 100,000 random double numbers is used to compare the performance of Insertion versus Shell sorts. In this particular case Shell sort is over 510 times faster than Insertion sort. The book quotes passes that are about 600 times faster. It is quite interesting to note that the base algorithm has two inner loops. Based on that the cost should be O(n^2). The pre sorting helps considerable with the number of long exchanges found in the Insertion sort.
The results for only 10,000 random double values follows:
main <<< alg1 ==>Insertion<==
main <<< alg2 ==>Shell<==
main <<< N: 10000
main <<< T: 100
main <<< t1: 23835.00 ms
main <<< t2: 374.00 ms
main <<< Shell is 63.73 times faster than Insertion
Now the difference was reduced by almost an order of magnitude.
WIth even less numbers (1,000) in the following case:
main <<< alg1 ==>Insertion<==
main <<< alg2 ==>Shell<==
main <<< N: 1000
main <<< T: 100
main <<< t1: 218.00 ms
main <<< t2: 46.00 ms
main <<< Shell is 4.74 times faster than Insertion
The ratio diminished considerable.
The test code for this exercise follows:
package john.canessa.sort;
import java.util.Random;
public class SortCompare {
/*
*
*/
public static double time(String alg, Double[] a) throws Exception {
double begin = System.currentTimeMillis();
switch (alg) {
case “Insertion”:
Insertion.sort(a);
break;
case “Selection”:
Selection.sort(a);
break;
case “Shell”:
ShellSort.sort(a);
break;
default:
throw new Exception(“unknown alg ==>” + alg + “<==”);
}
double end = System.currentTimeMillis();
return end – begin;
}
/*
* for specified algorithm sort N random values T times
*/
public static double timeRandomInput(String alg, int N, int T) throws Exception {
double totalTime = 0.0;
Double[] a = new Double[N];
Random rand = new Random();
for (int t = 0; t < T; t++) {
for (int n = 0; n < N; n++) {
a[n] = rand.nextDouble();
}
totalTime += time(alg, a);
}
return totalTime;
}
/*
* test code
*/
public static void main(String[] args) throws Exception {
final String alg1 = “Insertion”;
final String alg2 = “Shell”;
final int N = 100000;
final int T = 100;
System.out.println(“main <<< alg1 ==>” + alg1 + “<==”);
System.out.println(“main <<< alg2 ==>” + alg2 + “<==”);
System.out.println(“main <<< N: ” + N);
System.out.println(“main <<< T: ” + T);
double t1 = timeRandomInput(alg1, N, T);
System.out.printf(“main <<< t1: %8.2f ms\n”, t1);
double t2 = timeRandomInput(alg2, N, T);
System.out.printf(“main <<< t2: %8.2f ms\n”, t2);
if (t1 < t2) {
System.out.printf(“main <<< %s is %.2f times faster than %s\n”, alg1, t2 / t1, alg2);
} else {
System.out.printf(“main <<< %s is %.2f times faster than %s\n”, alg2, t1 / t2, alg1);
}
}
}
The ShellSort class written in Java follows:
package john.canessa.sort;
public class ShellSort {
/*
* sort
*/
public static void sort(Comparable[] a) {
int n = a.length;
// **** 3x + 1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, … ****
int h = 1;
while (h < (n / 3)) {
h = (3 * h) + 1;
}
// **** sort the array ****
while (h >= 1) {
// **** h-sort the array ****
for (int i = h; i < n; i++) {
for (int j = i; (j >= h) && less(a[j], a[j-h]); j -= h) {
exch(a, j, j – h);
}
}
// **** update h ****
h /= 3;
}
}
/*
* determine if the array is h-sorted
*/
private static boolean isHSorted(Comparable[] a, int h) {
for (int i = h; i < a.length; i++) {
if (less(a[i], a[i – h])) {
return false;
}
}
return true;
}
/*
* determine if v is less than w
*/
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
/*
* exchange two elements
*/
private static void exch(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
/*
* show
*/
private static void show(Comparable[] a) {
System.out.print(“sort <<< a: “);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + ” “);
}
System.out.println();
System.out.print(” “);
for (int i = 0; i < a.length; i++) {
System.out.print((i % 10) + ” “);
}
System.out.println();
}
/*
* check if array is or is not sorted
*/
public static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++) {
if (!less(a[i – 1], a[i])) {
return false;
}
}
return true;
}
/*
* test code
*/
public static void main(String[] args) {
Comparable[] a = { “S”, “H”, “E”, “L”, “L”, “S”, “O”, “R”, “T”, “E”, “X”, “A”, “M”, “P”, “L”, “E” };
ShellSort.sort(a);
ShellSort.isSorted(a);
ShellSort.show(a);
}
}
I recommend reading the entire chapter on Sorting in the Algorithms book and try some of the exercises. That appears to be the best way to solidify the concepts.
If you have comments or questions, please do not hesitate and send me a message via email.
John
john.canessa@gmail.com