Sunday, May 9, 2021

Shell Sort using C

 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.

Shell Sort using C


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