Continuing our sorting algorithm discussion, today’s article will cover a technique known as Shell Sort.
Shell sort is a quadratic (O(n2)) in-place comparison sort algorithm developed by Donald Shell in 1959 that is basically Insertion Sort with a gap between comparing indexes. The assumption is that comparing farther apart elements can move some out-of-place elements into position faster.
How do it…
The first thing we need is an algorithm to calculate the gaps to evaluate. Here is a simple algorithm that was created by Shell (gaps are an array of values created by n / 2 ^ k):
function createGaps(a) {
// if a is an array of 100, gaps would be [50, 25, 12, 6, 3, 1]
var gaps = [];
for (var i = 0, j = a.length, t; 1 <= (t = Math.floor(j / Math.pow(2, i + 1))); i += 1) {
gaps[i] = t;
if (t === 1) {
break;
}
}
if (gaps[i] !== 1) {
gaps.push(1);
}
return gaps;
}
Here is a the shell sort algorithm in JavaScript:
function shellSort(a) {
var gaps = createGaps(a),
temp;
for (var i = 0, j = gaps.length, gap; i < j; i += 1) {
gap = gaps[i];
for (var x = gap, y = a.length; x < y; x += 1) {
temp = a[x];
// this performs insertion sort on subarrays
for (var z = x; z >= gap && a[z - gap] > temp; z -= gap) {
a[z] = a[z - gap];
}
a[z] = temp;
}
}
}
Here it is in action:
Restart Shell Sort With a New Array
If we take a 10,000 element array and sort it, here is how shell sort compares to native array sort (prints to the console):
How it works…
The gap algorithm is simple and there are more efficient ones (see the wikipedia article), but I choose it because it was easy to implement and understand. It creates an array of values n / 2 ^ k, where n is the length of the array and k is an incrementing integer. We stop appending to the array when the final value of 1 is reached. The gap algorithm is critical to reducing the number of swaps made by the inner insertion sort.
The shell sort algorithm breaks the array up into sub-arrays and order them. This is a little tricky to understand by looking at the code, so we’ll analyze the first few comparisons made to a 100 value array. The initial gap will be 50, so we will perform insertion sort on the two element sub-arrays made from the values at 0 and 50, 1 and 51, 2 and 52, etc. (i.e. 50 sub-arrays with two values). The second gap will be 25, so we perform insertion sort on the four element sub-arrays made from the values at indexes: 0, 25, 50, and 75; 1, 26, 51, and 76; 2, 27, 52, and 77; etc. (i.e. 25 sub-arrays with four values). And so on until we perform a complete insertion sort on all values once (the complete array with all 100 values).
For a random distribution shell sort tends to perform better than other quadratic comparison sorting algorithms, because it moves the values farthest from their final position to that position quicker. However, it will perform worse when the array is sorted already, or the values at each index are near their final position. Additionally, the number of elements in the gap array will affect the performance of this algorithm, so the better the gap the better the performance of shell sort.
There’s more…
For more information on shell sort and creating shell gaps, see the Shell Sort Wikipedia article.