The#sorting-algorithms series is a collection of posts about reimplemented sorting algorithms in JavaScript.

If you are not familiar with sorting algorithms, a quick introduction and the full list of reimplemented sorting algorithms can be found in theintroduction post of the series on sorting algorithms in JavaScript.

If you feel comfortable with the concept of each sorting algorithm and only want to see the code, have a look at the summary post of the series. It removes all explanations and contains only theJavaScript code for all sorting algorithms discussed in the series.

Get the code on Github

Of course, all the code can also be found on Github in the repositorysorting-algorithms-in-javascript.

A good way to compare all of them

Unlike thedata structures, allsorting algorithms have the same goal and they can all take the same input data. So, for every sorting algorithms of the series, we are going sort anarray of 10 numbers from 1 to 10.

By doing so we will be able to compare the different sorting algorithms more easily. Sorting algorithms are very sensitive to the input data so we will also try different input data to see how they affect the performances.

The Shellsort algorithm

Definition

Shellsort is an in-place comparison sort which 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 can move some out-of-place elements into position faster than a simple nearest neighbor exchange.FromWikipedia

Shellsort is a generalization of insertion sort that allows the exchange of items that are far apart. It is worth noting that for a value ofgap equals to 1, this algorithm is equal toinsertion sort. Have a look at the code below and you will quickly notice the similarities.

Visualization

If you want to have a nice visualization of the algorithm, thevisualgo.net website is a nice resource. You can play with many parameters and see which part of the algorithm is doing what.

Complexity

Note that the complexity of the Shellsort algorithm depends of the sequence of number that you use as gaps and there are a lot of different possible sequences. I think that it is nice to have a look atthis table to get an overview of those possible sequences and see the resulting complexity.

I didn’t mention any specific complexity above because the sequence that I am using in my example (the last one of the previous table) makes calculating the complexity impossible (it is an empirically sequence of numbers unrelated to n).

Anyway, you can still have an overview of the time and space complexity of the Shellsort algorithm with this excellentBig O cheat sheet. Be careful because they look wrong to me at the time of writing this post, but hopefully they will be fixed in the future.

The code

For each sorting algorithm, we are going to look at 2 versions of the code. The first one is the final/clean version, the one that you should remember. The second one implements some counters in order to demonstrate the different time complexities depending of the inputs.

Clean version

// array to sortvararray=[9,2,5,6,4,3,7,10,1,8];// gapsvargaps=[701,301,132,57,23,10,4,1];functionshellsort(array){for(varg=0;g<gaps.length;g++){vargap=gaps[g];for(vari=gap;i<array.length;i++){vartemp=array[i];for(varj=i;j>=gap&&array[j-gap]>temp;j-=gap){array[j]=array[j-gap];}array[j]=temp;}}returnarray;}console.log(shellsort(array));// => [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

Version with counters

// sample of arrays to sortvararrayRandom=[9,2,5,6,4,3,7,10,1,8];vararrayOrdered=[1,2,3,4,5,6,7,8,9,10];vararrayReversed=[10,9,8,7,6,5,4,3,2,1];// gapsvargaps=[701,301,132,57,23,10,4,1];functionshellsort(array){varcountOuter=0;varcountInner=0;varcountSwap=0;for(varg=0;g<gaps.length;g++){vargap=gaps[g];for(vari=gap;i<array.length;i++){countOuter++;vartemp=array[i];for(varj=i;j>=gap&&array[j-gap]>temp;j-=gap){countInner++;countSwap++;array[j]=array[j-gap];}array[j]=temp;}}console.log('outer:',countOuter,'inner:',countInner,'swap:',countSwap);returnarray;}shellsort(arrayRandom.slice());// => outer: 15 inner: 11 swap: 11shellsort(arrayOrdered.slice());// => outer: 15 inner: 0 swap: 0shellsort(arrayReversed.slice());// => outer: 15 inner: 13 swap: 13