Shell sort algorithm

Shell Sort Algorithm:-

Shell sort algorithm is an improved version of Insertion sort algorithm. In an average case when list is already partially sorted insertion sort is not an efficient way to solve the problem. Thus, we use shell sort algorithm.

        In shell sort algorithm, we divide the list in no. of lists according to the length of the list and then apply insertion sort on each sub-list. And then merge all the sub-lists to form one.

Example:-

       0   1   2   3  4   5   6    7     8   9  10

     70 30 40 10 80 20 90 110 75 60 45

We can divide it into 3 parts with 2 having 4 elements and one having 3 elements.

       0       3      6     9                 1       4     7        10                 2     5     8

    70 10 90 60         30 80 110 45          40 20 75

Apply insertion sort on each sub-list.

     0       3      6      9                1     4        7     10                  2      5     8

    10 60 70 90         30 45 80 110          20 40 75 

Merge them.

     0   1   2   3  4   5   6    7     8   9  10

    10 30 20 60 45 40 70 80 75 90 110

Divide it into two parts.

     0   2   4    6   8   10                1  3   5   7   9  

    10 20 45 70 75 110              30 60 40 80 90

Sort them using insertion sort.

      0   2    4   6   8   10                 1   3  5    7   9

     10 20 45 70 75 110               30 40 60 80 90

Merge them.

      0    1   2    3  4  5   6   7   8  9     10

     10 30 20 40 45 60 70 80 75 90 110 

Apply insertion sort to the list.

        10 20 30 40 45 60 70 75 80 90 110                

The list is sorted now.

Insertion Sort Algorithm

Insertion Sort:-

Insertion sort algorithm has two case scenarios -

• Best case
• Worst case

1. In worst case the given array elements are arranged in reverse /decreasing order. Thus, we have to do 1 comparison in first pass, 2 in second and n-1 comparisons in (n-1)th  pass.Thus, the total no. of comparisons made will be equal to (n^2)/2 and the complexity will be O(n^2).
2. Best case is occurred when given list is already sorted. In this case we have to make only one comparison in each pass. So, the complexity will be O(n).

In both cases no. of  passes are (n-1).

where n is the no. of elements in given array.

Algorithm:-

int i,j,temp,x[n];

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

{

            temp = x[i];

            j = i - 1;

            while( temp < x[j] && j >= 0)

            {

                       x[j + 1] = x[j];

                       j = j - 1;

            }

            x[j + 1] = temp;

}  

Example:-

              70 80 30 10 20

1. Split the array in two parts. One sorted list and second unsorted       list.

              70            80 30 10 20

          sorted              unsorted

2. Start placing elements in first list from second list at their correct     position.

              70  80           30  10  20

              

              30  70  80        10  20

              10  30  70  80      20

              10  20  30  70  80

The list is sorted now.