Data Structures and Algorithms Show(4): Shell Sort

Shell Sort has no relationship with shells in the ocean at all. This name comes from Donald Shell who created this algorithm several decades ago. If you read the sample code, it is easy to find out that this sort algorithm is based on Insertion Sort. The big difference inside Shell Sort is that gaps concept injection.

We have already known that comparison always happens between two adjacent elements and exchange them if necessary. What is going to happen if we compare two elements far away to each other? I know you do not feel much difference with this idea, but the gaps between the elements comparisons make the sort more efficient. This kind of comparison and long distance movement can reduce a huge amount of disorder very fast.

For example, we can define a gaps array which include three gap values: [3, 2, 1]. Then, we go through Insertion Sort three times:

1. Compare the elements with gap size 3: element 4 compare to element 1; element 5 compare to element 2; element 6 compare to element 3; element 7 compare to element 4; element 7 compare to element 1 (7-3-3=1); element 8 compare to element 5; element 8 compare to element 2; to the end of the array.
2. Compare the elements with gap size 2: element 3 compare to element 1; element 4 compare to element 2; element 5 compare to element 3; element 5 compare to element 1(5-2-2=1); element 6 compare to element 4; element 6 compare to element 2; to the end of the array.
3. Compare the elements with gap size 1: This is the original Insertion Sort.

I believe you just began to realize that there is a problem of Shell Sort. What are the best gaps to define? [3, 2, 1] or [256, 100, 40, 15, 6, 2, 1]? Unfortunately, the answer is still in the air. Some people do find some rules to get a reasonable gaps array, but with different data, we have no unified answer for it.

I think that is a reason why Shell Sort has no a big role in real application world. But spending some time on it is worthy. Now we understand that making a difference to those existed algorithm can generate a better (or worse) one. Anything is possible.

var gaps = [3,2,1];
for(var g = 0; g < gaps.length; g++){
    for(var i = gaps[g]; i < list.length; i++){
        var tmp = list[i];
        var insPos = i;
        for(var j = i; j - gaps[g] >= 0; j -= gaps[g]){
            if(tmp < list[j-gaps[g]]){
                list[j] = list[j - gaps[g]];
                insPos = j - gaps[g];
            }else{
                break;
            }
        }
        list[insPos] = tmp;
    }
}