Data Structures ---- Sorting (Part - 2 Shell Sort)

Shell Sort

reference: PANIMALAR ENGINEERING COLLEGE NOTES
                 Shell sort was invented by Donald Shell. It improves upon bubble sort and insertion sort by moving out of order elements more than one position at a time.
                 In this sort the whole array is first fragment into K segments, where K is preferably a prime number. After first pass, the whole array is partially sorted. In the next pass, the value of K is reduced which increases the size of the segment and reduces the number of segments.
                 The next K value is chosen as relatively prime to its previous value. The process is repeated until k=1 at which the array is sorted. The insertion sort is applied to each segment, so each successive segment is partially sorted.The shell sort is also called as Diminishing Increment Sort, because the value of K decreases continuously.

Algorithm

void ShellSort (ElementType A[ ], int N)
{
int i,j,Increment;
ElementType temp;
for(Increment = N/2; Increment>0; Increment = Increment/2)
for(i=Increment;i{
temp=A[i];
for(j=i;j>=Increment;j=j-Increment)
if(tempA[j] = A[j- Increment];
else
break;
A[j] = temp;
}
}

Example

Consider an Unsorted array

81      94       11         96        12       35        17        95        28         58

Here N = 10, the first Pass as K = 5 (10/2)

After First Pass

35        17          11           28           12            81             94            95           96           58

In second pass, K is reduced to 3

After Second Pass

28        12         11           35           17                81               58            95             96            94

In third pass, K is reduced to 1

The final sorted array is

11           12          17          28          35            58            81           94            95           96

Analysis of Shell Sort

Worst Case Analysis                          - O(N²)
Best Case Analysis                             - O(N log N)
Average Case Analysis                       - O(N²)

Advantages of Shell Sort

It is one of the fastest algorithm for sorting small number of elements.

It requires relatively small amounts of memory.

(contd)