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