Data Structures and Algorithms
    About Lesson

    The shell sort algorithm is an extended version of an insertion sort. Shell sort improves the average time complexity of insertion sort

    This is a comparison-based and in-place sorting algorithm, similar to insertion sort. Shell sort is effective for medium-sized data sets.

    In insertion sort, at a time elements can only be moved forward by one position. It takes many movements to move an element to a far-away position, which increases the algorithm’s execution time.

    Shell sort overcomes this problem of insertion sort. It makes it possible to move and swap distant elements as well.

    The algorithm first sorts elements that are far from each other, and then it reduces their distance from each other. This distance is called an interval.

    Here is the Knuth’s formula for calculating intervals –

    h = h * 3 + 1
    where −
       h is an interval with an initial value of 1

     

    Time Complexity

    CaseTime Complexity
    Best CaseO(n log n)
    Average CaseO(n log (n)2)
    Worst CaseO(n2)

     

    Best Case O(n log n): It occurs when there is no sorting needed, i.e. the array is already sorted.

    Average Case O(n log (n)2): The array elements are in a jumbled order that is not properly ascending and descending.

    Worst Case O(n2): This occurs when the array elements need to be sorted in reverse order.

     

    Space Complexity

    Space ComplexityO(1)
    StableNo

     

    The space complexity of shell sort is O (1).

     

    Example

    C Program

    #include <stdio.h>    
    /* function to implement shellSort */  
    int shell_sort(int a[], int n) {  
        /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */
        for (int interval = n/2; interval > 0; interval /= 2) {  
            for (int i = interval; i < n; i += 1) {  
                /* store a[i] to the variable temp and make the ith position empty */  
                int temp = a[i];  
                int j;        
                for (j = i; j >= interval && a[j - interval] > temp; j -= interval)  
                    a[j] = a[j - interval];  
                  
                // put temp (the original a[i]) in its correct position 
                a[j] = temp;  
            }  
        }  
        return 0;  
    }  
    
    /* function to print the array elements */  
    void print(int a[], int n) {  
        for (int i = 0; i < n; i++)  
            printf("%d ", a[i]);  
    }    
    
    int main() {  
        int a[] = { 42, 12, 17, 25, 40, 8, 42, 33, 31 };  
        int n = sizeof(a) / sizeof(a[0]);  
        printf("Before sorting array elements are - n");  
        print(a, n);  
        shell_sort(a, n);  
        printf("nAfter applying shell sort, the array elements are - n");    
        print(a, n);  
        return 0;  
    }  

     

    Java Program

    class ShellSort {  
        /* function to implement shellSort */  
        static void shellSort(int a[], int n) {  
            /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */  
            for (int interval = n/2; interval > 0; interval /= 2) {  
                for (int i = interval; i < n; i += 1) {  
                    /* store a[i] to the variable temp and make the ith position empty */  
                    int temp = a[i];  
                    int j;        
                    for (j = i; j >= interval && a[j - interval] >   
        temp; j -= interval)  
                        a[j] = a[j - interval];  
                    /* put temp (the original a[i]) in its correct  
        position */  
                    a[j] = temp;  
                }  
            }  
        }  
        
        /* function to print the array elements */  
        static void print(int a[], int n) {  
            for (int i = 0; i < n; i++)  
                System.out.print(a[i] + " ");  
        }
        
        public static void main(String args[]) {  
            int a[] = { 42, 12, 17, 25, 40, 8, 42, 33, 31 };
            int n = a.length;  
            System.out.print("Before sorting array elements are - n");
            print(a, n);  
            
            shellSort(a, n);  
            System.out.print("nAfter applying shell sort, the array elements are - n");    
            print(a, n);  
        }      
    }