In this tutorial, we will write a C program to implement shell sort. Before that, you may go through the following topics in C.
Shell Sort Algorithm
Shell sort is an in-place comparison-based sorting algorithm and variation of Insertion sort. It is a better version of Insertion sort in comparison-based. It can compare the elements far apart whereas Insertion compares adjacent elements.
In shell sort, we make the array h-sorted for a large value of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists of every h’th element are sorted.
Implementation of Shell Sort Algorithm in C
Question: C program to implement Shell sort using function.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | // Shell Sort in C programming #include <stdio.h> //function prototype void shellSort(int array[], int n); int main() { int arr[30], n, i; printf("Enter the number of elements: "); scanf("%d", &n); printf("Enter %d Elements:\n", n); for (i = 0; i < n; i++) scanf("%d", &arr[i]); //calling sorting function shellSort(arr, n); //Display the result printf("\nArray after sorting: \n"); for (i = 0; i < n; i++) printf("%d ", arr[i]); return 0; } // Shell sort void shellSort(int arr[], 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) { int temp = arr[i]; int j; for (j = i; j >= interval && arr[j - interval] > temp; j -= interval) arr[j] = arr[j - interval]; arr[j] = temp; } } } |
Output:
Enter the number of elements: 6
Enter 6 Elements:
55
3
356
124
54
18
Array after sorting:
3 18 54 55 124 356
Time Complexity of Shell Sort:
- Best case:
0(nlogn) - Average case:
0(n(logn)^2) - Worst case:
0(n(logn)^2)