I will show here an example on shell sort (invented by Donald Shell) using C programming language. This method makes repeated use of straight insertion or shuttle sort. The method starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared.
An array with n elements, in each pass, an increment is chosen. The increment must be less than n and the increment progressively should be smaller and the last increment must be equal to 1.
Time Complexity
Worst-case performance: O(n2)
Best-case performance: O(n log n)
Worst-case space complexity: О(n) total, O(1) auxiliary
Source Code
The complete source code for shell sort algorithm using C program is given below:
/* * File: ShellSort.c */ #include <stdio.h> #include <stdlib.h> void shellSort(int a[], int n) { int i, j, m; int temp; for (m = n / 2; m > 0; m /= 2) { for (j = m; j < n; j++) { for (i = j - m; i >= 0; i -= m) { if (a[i + m] >= a[i]) { break; } else { temp = a[i]; a[i] = a[i + m]; a[i + m] = temp; } } } } printf("\n"); printf("\nThe sorted array elements are given below\n"); for (i = 0; i < n; i++) { printf("a[%d]=%d ", i, a[i]); } } int main() { int i, n = 6; int a[] = {15, 8, 17, 12, 38, 19}; printf("\n:: Shell Sort ::\n"); printf("\nInput array elements\n"); for (i = 0; i < n; i++) { printf("a[%d]=%d ", i, a[i]); } shellSort(a, n); }
Testing the Program
By executing the above C program you will get the below output:
:: Shell Sort :: Input array elements a[0]=15 a[1]=8 a[2]=17 a[3]=12 a[4]=38 a[5]=19 The sorted array elements are given below a[0]=8 a[1]=12 a[2]=15 a[3]=17 a[4]=19 a[5]=38
No comments:
Post a Comment