Shell Sort

As we have seen, insertion and selection sort behave differently. Selection sort moves the entries very efficiently but doesn’t make redundant comparisons. In its best case, insertion sort does the minimum number of comparisons but is inefficient in moving entries only one place at a time, as it compares only adjacent keys.

If we were to modify it, first comparing the keys far apart, then it could sort the entries. Afterwards the entries closer together would be sorted and finally the increment between the keys would be reduced to 1 to ensure that the list is completely in order. This is the concept implemented by Donald. L. Shell in the sorting method bearing his name. The method is also called diminishing increment sort.

Algorithm: The idea of Shellsort is is the following

Step1: Arrange the data sequences in a two-dimensional array.

Step2: Sort the columns of the array.

Example:

Let the array 3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2

be the data sequences to be sorted. First, it is arranged in an array with 7 columns (left), then the columns are sorted (right):

3 7 9 0 5 1 6 3 3 2 0 5 1 5

8 4 2 0 6 1 5  7 4 4 0 6 1 6

7 3 4 9 8 2 8 7 9 9 8 2

Data elements 8 and 9 have now come to the end of the sequence, but a small element (2) is also still there. In the next step, the sequence is arranged in 3 columns, which are again sorted.

3 3 2 0 0 1

0 5 1 1 2 2

5 7 4 3 3 4

4 0 6 4 5 6

1 6 8 5 6 8

7 9 9 7 7 9

8 2 8 9

Now the sequence is almost completely sorted. When arranging it in one column in the last step, it is only a 6 an 8 and a 9 that have to moved a little bit to their correct positions.

Listing: Following program is showing the implementation of Shell sort.

/* 
* C Program to Perform Shell Sort without using Recursion 
*/ 
#include  <stdio.h> 
#define size 7 

/* Function Prototype */ 
int shell_sort(int []); 

void main() 
{ 
    int arr[size], i; 
    printf("Enter the elements to be sorted:"); 
    for (i = 0;i < size;i++) 
    { 
        scanf("%d", &arr[i]); 
    } 
    shell_sort(arr); 
    printf("The array after sorting is:"); 
    for (i = 0;i < size;i++) 
    { 
        printf("\n%d", arr[i]); 
    } 
} 

/* Code to sort array using shell sort */ 
int shell_sort(int array[]) 
{ 
    int i = 0, j = 0, k = 0, mid = 0; 
    for (k = size / 2;k > 0;k /= 2) 
    { 
        for (j = k;j < size;j++) 
        { 
            for (i = j - k;i >= 0;i -= k) 
            { 
                if (array[i + k] >= array[i]) 
                { 
                    break; 
                } 
                else 
                { 
                    mid = array[i]; 
                    array[i] = array[i + k]; 
                    array[i + k] = mid; 
                } 
            } 
        } 
    } 
    return 0; 
} 

Output: 
    //Average case: 

    Enter the elements to be sorted:57 
    67 
    48 
    93 
    42 
    84 
    95 
    The array after sorting is: 
    42 
    48 
    57 
    67 
    84 
    93 
    95 
     
    //Best case: 

    Enter the elements of array:22 
    33 
    74 
    85 
    86 
    87 
    98 
    The array after sorting is:22 
    33 
    74 
    85 
    86 
    87 
    98 
     
    //Worst case: 

    Enter the elements of array:94 
    92 
    91 
    89 
    85 
    80 
    43 
    The array after sorting is:43 
    80 
    85 
    89 
    91 
    92 
    94