The Shell Sort Algorithm is similar to the Insertion Sort algorithm in that we work through our dataset moving values forward when they are smaller than the values ahead, except that with Shell Sort we try to cheat a bit by not starting back at the beginning every time.
Here's a description from 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.
Hey, Tyler here. I'm currently working on some great web development and digital marketing products and services over at ZeroToDigital.
If that sounds interesting to you, please check it out!
We're going to implement the Shell Sort algorithm in JavaScript below.
JavaScript
shellSort = (array,gaps) => {
for (var g = 0; g < gaps.length; g++) {
var gap = gaps[g]
for (var i = gap; i < array.length; i++) {
var temp = array[i]
for (var j = i; j >= gap && array[j - gap] > temp; j -= gap) {
array[j] = array[j - gap]
}
array[j] = temp
}
}
return array
}We don't need any helper functions here, just the shellSort function.
It accepts 2 arrays, the array that holds our dataset and the gaps array that holds our list of gaps that will allow us to start our loop over in places other than just the front.
First, we'll loop through our gaps array and determine the gap that will be used during the pass. Then, we'll loop through our dataset starting at the gap and continuing to the end of the dataset. We'll sent the variable temp equal to the array value at the index of gap.
Our final inset loop will start at i, and if j is greater or equal to the gap and the array value at index j - gap is greater than the temporary array value then we'll assign the array at index j the value of temp and reloop after deducting j the value of gap. Then we'll return the array value.
JavaScript
var array = [8,3,5,9,1,5,9,2,3,8,4]
var gaps = [66,31,14,5,1]
shellSort(array,gaps)
// 5,3,5,9,1,8,9,2,3,8,4
// 5,3,5,9,1,8,9,2,3,8,4
// 5,3,2,9,1,8,9,5,3,8,4
// 5,3,2,3,1,8,9,5,9,8,4
// 4,3,2,3,1,5,9,5,9,8,8
// 3,4,2,3,1,5,9,5,9,8,8
// 2,3,4,3,1,5,9,5,9,8,8
// 2,3,3,4,1,5,9,5,9,8,8
// 1,2,3,3,4,5,9,5,9,8,8
// 1,2,3,3,4,5,9,5,9,8,8
// 1,2,3,3,4,5,9,5,9,8,8
// 1,2,3,3,4,5,9,5,9,8,8
// 1,2,3,3,4,5,9,5,9,8,8
// 1,2,3,3,4,5,5,9,9,8,8
// 1,2,3,3,4,5,5,8,9,9,8
// 1,2,3,3,4,5,5,8,8,9,9The Shell Sort algorithm requires a lot of looping, so the time complexity isn't very efficient at O(n^2). The space complexity is good at O(1). Something else to keep in mind is the Shell Sort is not a stable sorting algorithm as values of equal size are liable to change place.
Check out other sorting algorithm implementations in JavaScript: