C Program for Sorting an Array using Shell Sort using Knuth increments

By | 17.09.2017

Shell Sort using Knuth increments


Write a C Program for Sorting an Array using Shell Sort using Knuth increments.  Here’s simple C Program for Sorting an Array using Shell Sort using Knuth increments in C Programming Language.


Shell Sort


Shell Sort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved.

The idea of Shell Sort is to allow exchange of far items. 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 sub lists of every h’th element is sorted.

Time Complexity: Time complexity of Shell Sort is O(n2).


Also Read : : C Program for Sorting an Array using Insertion Sort

Below is the source code for C Program for Sorting an Array using Shell Sort using Knuth increments which is successfully compiled and run on Windows System to produce desired output as shown below :


SOURCE CODE : :


/* C Program for Sorting an Array using Shell Sort using Knuth increments */

#include<stdio.h>
#define MAX 100
int main()
{
        int arr[MAX],i,j,k,n,incr;

        printf("\nEnter the number of elements : ");
        scanf("%d",&n);

        for(i=0;i<n;i++)
        {
                printf("\nEnter element %d : ",i+1);
                scanf("%d",&arr[i]);
        }

        incr=1;
        while(incr<=(n-1)/9)
                incr=3*incr+1;

        while(incr>=1)
        {
                for(i=incr; i<n; i++)
                {
                        k=arr[i];
                        for(j=i-incr; j>=0 && k<arr[j]; j=j-incr)
                                arr[j+incr]=arr[j];
                        arr[j+incr]=k;
                }
                incr=incr/3;
        }

        printf("\nSorted list is :\n");
        for(i=0; i<n; i++)
                printf("%d ", arr[i]);
        printf("\n");

        return 0;
}

OUTPUT  : :


/* C Program for Sorting an Array using Shell Sort using Knuth increments */


Enter the number of elements : 6

Enter element 1 : 1

Enter element 2 : 77

Enter element 3 : 33

Enter element 4 : 9

Enter element 5 : 0

Enter element 6 : 24

Sorted list is :
0 1 9 24 33 77

Process returned 0

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.


Thanks for reading the post…


Recommended Posts : :

3.7 7 votes
Article Rating
Subscribe
Notify of
guest

1 Comment
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Anmol Sonthalia

Can you recommend which compiler do you use ?