Shellsort

Shellsort

Shellsort, also known as Shell sort or Shell's method, 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).^[2] 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. Donald Shell published the first version of this sort in 1959.^[3][4] The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem.

ShellSort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. The idea of shellSort is to allow exchange of far items. In shellSort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element is sorted.

Pseudocode

# Sort an array a[0...n-1].

gaps = [701, 301, 132, 57, 23, 10, 4, 1]

# Start with the largest gap and work down to a gap of 1

foreach (gap in gaps)

{

    # Do a gapped insertion sort for this gap size.

    # The first gap elements a[0..gap-1] are already in gapped order

    # keep adding one more element until the entire array is gap sorted

    for (i = gap; i < n; i += 1)

    {

        # add a[i] to the elements that have been gap sorted

        # save a[i] in temp and make a hole at position i

        temp = a[i]

        # shift earlier gap-sorted elements up until the correct location for a[i] is found

        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)

        {

            a[j] = a[j - gap]

        }

        # put temp (the original a[i]) in its correct location

        a[j] = temp

    }

}

Algorithmic Implementation : 

First use a loop to get different value of slots/gaps from the gap array.Use first inner loop to compare the values with (array[gap],array[0]),(array[gap+1],array[1])...and so on . Now use the inner most loop to compare the above value and use swapping after comparing them intelligently as below :-

temp = a[j]  //here j points to a[gap] and same thing will be pointed by a[k] in the inner most loop.
So now a[k] will be emptied before we entered into the inner most loop. So we can make it to hold some value as below :
a[k]=a[k-gap].

Now here again the algorithm works in a smarter way .When you come out of the inner most loop again we are making a[k] as a[0] or a[1]... so after the end of inner loop the statement : 
 a[k]=temp;

we are again swapping the value of a[k]/a[j]/[gap] with a[gap -k].

So in short ,with this algorithm we are using swapping the compared value intelligently. 

Java Implementation

int gaps[]={12,9,8,6,4,3,2,1};
    int gap = 0;
    int j=0;
    int k=0;
    int a[]= {23,12,5,7,25,3,15,1};
    //take the gap from gaps array
    for(int i=0;i<gaps.length;i++){
        gap=gaps[i];
    //now start with the gap value such that it is less than the array length
        for(j = gap ;j<a.length;j++){
            int temp = a[j];
        //now use insertion shorting logic here
            for(k=j;k>=gap && a[k-gap]>temp;k-=gap){
                a[k]=a[k-gap];
            }
            a[k]=temp;
        }
        }
    System.out.println("Sorted");
    for(int element : a)
        System.out.print(element +"||");
  
  
    }

Gap sequences

The question of deciding which gap sequence to use is difficult. Every gap sequence that contains 1 yields a correct sort; however, the properties of thus obtained versions of Shellsort may be very different.
The table below compares most proposed gap sequences published so far. Some of them have decreasing elements that depend on the size of the sorted array (N). Others are increasing infinite sequences, whose elements less than N should be used in reverse order.

General term (k ≥ 1)	Concrete gaps	Worst-case time complexity	Author and year of publication
Floor(N/2^k)	N/2,N/4……….1	Theta(N^2)	Shell 1959
2*Floor(N/2^(k+1))+1	2(N/4)+1,…..3,1	Theta(N^(3/2))	Frank & Lazarus, 1960
2^k-1	1,3,7,15,31,63,……	Theta(N^(3/2))	Hibbard, 1963
2^k+1	1,3,5,9,17,33,65,….	Theta(N^(3/2))	Papernov & Stasevich, 1965
successive numbers of the form 3^p2^q	1,2,3,4,6,8,9,12…..	Theta(Nlog^2N)	Pratt