C Program To Perform Shell Sort

Shell sort works by comparing distant elements before processing neighboring elements.  And the distance used for comparison keeps decreases for each pass.

Example:
83   97   14  101   15   39   23   98   31   63

Pass 1: (Distance: 5)
Apply insertion sort to sub-array (a0, a5), (a1, a6), (a2, a7), (a3, a8), (a4, a9)
39  97  14 101  15  83  23  98  31  63  -   (a0, a5)
39  23  14 101  15  83  97  98  31  63  -   (a1, a6)
39  23  14 101  15  83  97  98  31  63  -   (a2, a7)
39  23  14  31  15  83  97  98 101  63  -   (a3, a8)
39  23  14  31  15  83  97  98 101  63  -   (a4, a9)

Pass 2: (Distance: 2)
Apply insertion sort on sub-arrays (a0, a2), (a1, a3), (a0, a2, a4), (a1, a3, a5), (a0, a2, a4, a6), (a1, a3, a5, a7), (a0, a2, a3, a6, a8), (a1, a3, a5, a7, a9)

14  23  39  31  15  83  97  98 101  63   -  (a0, a2)
14  23  39  31  15  83  97  98 101  63   -  (a1, a3)
14  23  15  31  39  83  97  98 101  63   -  (a0, a2, a4)
14  23  15  31  39  83  97  98 101  63   -  (a1, a3, a5)
14  23  15  31  39  83  97  98 101  63   -  (a0, a2, a4, a6)
14  23  15  31  39  83  97  98 101  63   -  (a1, a3, a5, a7)
14  23  15  31  39  83  97  98 101  63  -  (a0, a2, a3, a6, a8)
14  23  15  31  39  63  97  83 101  98  -  (a1, a3, a5, a7, a9)

Pass 3: (Distance: 1)
Apply insertion sort on a0..a9
14  23  15  31  39  63  97  83 101  98  - inserted 23 at the right place
14  15  23  31  39  63  97  83 101  98  - inserted 15 at the right place
14  15  23  31  39  63  97  83 101  98  - inserted 31 at the right place
14  15  23  31  39  63  97  83 101  98  - inserted 39 at the right place
14  15  23  31  39  63  97  83 101  98  - inserted 63 at the right place
14  15  23  31  39  63  97  83 101  98  - inserted 97 at the right place
14  15  23  31  39  63  83  97 101  98  - inserted 83 at the right place
14  15  23  31  39  63  83  97 101  98  - inserted 101 at the right place
14  15  23  31  39  63  83  97  98 101  - inserted 98 at the right place

See Also:

C Program To Perform Insertion Sort

C Program To Perform Shell Sort

C Program To Perform Bubble Sort

C Program To Perform Quick Sort

C Program To Perform Radix Sort

C Program To Perform Selection Sort

C Program To Perform Heap Sort

C Program To Perform Merge Sort

C Program To Perform External Sorting

C Program To Perform Sorting Using Binary Search Tree

Example Program For Shell Sort:

---

  #include <stdio.h>
  #include <stdlib.h>
  void shell_sort(int *data, int n) {
        int i, j, k, l, tmp;
        for (i = n/2; i > 0; i = i/2) {
                for (j = i; j < n; j++) {
                        tmp = data[j];
                        for (k = j; k >= i && data[k-i] > tmp; k = k-i) {
                                data[k] = data[k-i];
                        }
                        data[k] = tmp;
                }
        }
        printf("Sorted data:\n");
        for (l = 0; l < n; l++)
                printf("%3d ", data[l]);
        printf("\n");

  }

  int main() {
        int n, i, *data;
        printf("Enter the no of data:");
        scanf("%d", &n);
        data = (int *)malloc(sizeof (int) * n);
        for (i = 0; i < n; i++)
                scanf("%d", &data[i]);
        shell_sort(data, n);
        return 0;
  }

  Output: (C Program To Implement Shell Sort)

  jp@jp-VirtualBox:s$ ./a.out
  Enter the no of data:10
  83  97  14  101  15  39  23  98  31  63
  Sorted data:
  14  15  23  31  39  63  83  97  98 101