Shell Sort Algorithm Implementation in C: Knuth’s and Hibbard’s Intervals

Shell Sort Algorithm sorts elements in array at a specific interval. At first, it sorts the elements that are away from each other and successively reduces the interval between them. This is a simple but powerful version of another sorting algorithm insertion sort. The performance of the shell sort depends on the type of sequence used for a given list. It performs very well if array elements are near to each other, i.e. array is partially sorted.

Shell Sort is named after Donald Lewis Shell who initially wrote it in a research paper called A High-Speed Sorting Procedure, which was published in Communications of the ACM, July 1959.

Table of Contents

• How Shell Sort Works?
• Shell Sort Sequence Intervals
  • Donald Shell’s Actual Interval:
  • Hibbard, Papernov & Stasevich Interval:
    • Hibbard’s Interval:
    • Papernov & Stasevich’s Interval:
  • Pratt’s Interval:
  • Knuth’s Interval:
  • Sedgewick’s Intervals:
  • Tokuda’s Intervals:
  • Ciura’s Interval:
• Shell Sort Applications
• Shell Sort Complexity
• Shell Sort Implementation using Knuth’s Interval
• Shell Sort Implementation using Hibbard’s Sequence

How Shell Sort Works?

This sorting algorithm extensively uses Insertion sort to sort the smaller arrays as insertion sort is very efficient on small arrays. It is also very efficient on nearly sorted arrays.

1. Choose an initial increment interval based on the size of the list.
2. Choose a smaller interval size (based on sequence) and continue through the loop.
3. While in the loop, use insertion sort with an interval size 1 to complete the array sorting.
4. Array is fully sorted when the loop ends.

With each outer iteration of the algorithm, the elements in the array closer to their actual positions. This method is efficient due to the use of insertion sort. It utilize the order present in a partially sorted input array. It is important to choose a good sequence of intervals.

Here are some of the good intervals used in Shell Sort.

Shell Sort Sequence Intervals

Donald Shell’s Actual Interval:

Formula: [N/2k]

Sequence: [N/2], [N/4], [N/8], … 1

Hibbard, Papernov & Stasevich Interval:

Both of them introduced similar intervals with minor changes i.e.

Hibbard’s Interval:

Formula: 2^k-1

Sequence: 0, 1, 3, 7, 15, 31

Papernov & Stasevich’s Interval:

Formula: 2^k+1, starting with 1

Sequence: 1, 3, 5, 9, 17, 33, 65,

Pratt’s Interval:

These numbers were once called “harmonic numbers”.

Formula: 2^i*3^j with i, j >= 0

Sequence: 1, 2, 3, 4, 6, 8, 9, 12, 16,

Knuth’s Interval:

Formula: (3^n – 1)/2

Sequence: 0, 1, 4, 13, 40, 121, 364,

Sedgewick’s Intervals:

Formula 1: 4^(n+1) + 3*2^n + 1

Sequence: 1, 8, 23, 77, 281, 1073, 4193

Formula 2 – Good sequence of intervals for Shell sort. It is even best on arrays with more values.

For Arrays with Even Length:

9*2^n – 9*2^(n/2) + 1

For Arrays with Odd Length:

8*2^n – 6*2^((n+1)/2) + 1

Sequence 2:

1, 5, 19, 41, 109, 209, 505, 929, 2161

Tokuda’s Intervals:

Formula: ceiling( (9 * (9/4)^n – 4) / 5).

Sequence: 1, 4, 9, 20, 46, 103, 233,

Ciura’s Interval:

Best Increments for the Average Case of Shell sort.

Sequence: 1, 4, 10, 23, 57, 132, 301, 701, 1750

Shell Sort Applications

• Sorting arrays: The most common application of the Shell Sort Algorithm is to sort arrays of data. The algorithm is particularly useful when the array is large and needs to be sorted quickly.
• Linux Kernel: Shell sort is used in the Linux Kernel. Shell sort is used in Linux kernel library uClib, which is used in embedded systems.
• Compression algorithms: Shell Sort can be used as a subroutine in compression algorithms to sort data before compressing it. This can improve the compression ratio and reduce the size of the compressed file. It used in bzip2 compression library using Knuth’s increments.
• Cryptography: Shell Sort can be used in some encryption algorithms to scramble the order of data before encrypting it. This can help to make the encryption more secure and harder to crack. One example of such an encryption algorithm is the Rijndael cipher, which is used in the Advanced Encryption Standard (AES).
• Database indexing: Shell Sort can be used to sort data in a database index. For example, in SQLite, the B-tree data structure is used for indexing, and Shell Sort is used as a sorting algorithm for building and maintaining the B-tree.
• Data visualization: Shell Sort can be used in some data visualization tools to sort data before displaying it. This can help to make the data more readable and easier to interpret.
• Memory Efficient: It is relatively easy to implement and does not use any additional memory (other than input).

Shell Sort Complexity

Worst Case Complexity: <= O(n2)

Best Case Complexity: O(n*log n)

Average Case Complexity: O(n*log n)

Space Complexity is O(1)

Shell Sort Implementation using Knuth’s Interval

#include <stdio.h>

void shellsort(int a[], int n);
void print(int a[], int n);    

int main() {
    int array[] = {6, 4, 9, 3, 7, 1, 0, 10, 2, 8, 5};
    int size = sizeof(array) / sizeof(array[0]);
    shellsort(array, size);
    printf("Sorted Array Using Shell Sort: \n");
    print(array, size);
}

// Shell Sort Algorithm C Implementation
void shellsort(int a[], int n) {
    int i, j;
    int tmp, increment;
    for (increment = n / 2; increment > 0; increment /= 2) {
        for (i = increment; i < n; i++) {
            tmp = a[i];
            for (j = i; j >= increment; j -= increment) {
                if (tmp < a[j - increment]) {
                    a[j] = a[j - increment];
                } else {
                    break;
                }
            }
            a[j] = tmp;
        }
        
        printf(" Gap %d: ", increment);
        print(a, n);
    }
}

// Print an array
void print(int a[], int n) {
    for (int i = 0; i < n; ++i) {
        printf("%d  ", a[i]);
    }
    printf("\n");
}

Output Knuth’s Implementation:

 Gap 5: 1  0  9  2  7  5  4  10  3  8  6  
 Gap 2: 1  0  3  2  4  5  6  8  7  10  9  
 Gap 1: 0  1  2  3  4  5  6  7  8  9  10  
Sorted Array Using Shell Sort: 
0  1  2  3  4  5  6  7  8  9  10

Shell Sort Implementation using Hibbard’s Sequence

#include <stdio.h>
#include <math.h>

void shellsort(int a[], int n);
void print(int a[], int n);    

int main() {
    int array[] = {6, 4, 9, 3, 7, 1, 0, 10, 2, 8, 5};
    int size = sizeof(array) / sizeof(array[0]);
    shellsort(array, size);
    printf("Sorted Array Using Shell Sort: \n");
    print(array, size);
}

// Shell Sort Algorithm C Implementation
void shellsort(int a[], int n) {
    int i, j;
    int tmp, increment;
    //2^k-1 - Formula
    //2^INT[LOG(n)/LOG(2)]-1  
    //To implement we have to find the max number in the hibbard's sequence
    //to start from i.e. in our casse it should be < size of array.
    for (increment = pow(2, (int)( log(n)/log(2) ) )-1 ; increment > 0; increment /= 2) {
        for (i = increment; i < n; i++) {
            tmp = a[i];
            for (j = i; j >= increment; j -= increment) {
                if (tmp < a[j - increment]) {
                    a[j] = a[j - increment];
                } else {
                    break;
                }
            }
            a[j] = tmp;
        }
        
        printf(" Gap %d: ", increment);
        print(a, n);
    }
}

// Print an array
void print(int a[], int n) {
    for (int i = 0; i < n; ++i) {
        printf("%d  ", a[i]);
    }
    printf("\n");
}

This C program demonstrates the Shell Sort algorithm to efficiently sort an array of integers. It includes the math.h library for mathematical functions. The shellsort function uses Hibbard’s sequence to determine the increments in a descending order (2^k – 1) and applies the Shell Sort algorithm on the array. It repeatedly compares and swaps elements at a certain gap until the entire array is sorted.

Output of Shell Sort with Hibbard’s Sequence:

 Gap 7: 6  2  8  3  7  1  0  10  4  9  5  
 Gap 3: 0  2  1  3  5  4  6  7  8  9  10  
 Gap 1: 0  1  2  3  4  5  6  7  8  9  10  
Sorted Array Using Shell Sort: 
0  1  2  3  4  5  6  7  8  9  10

See also: Quick Sort, Bubble Sort, Insertion Sort, Selection Sort