Shell Sort C Code And Algorithm

Socialize It →

Tweet

Shell sort is an in-place comparison sort. Donald Shell published the first version of this sort in 1959. It generalizes an exchanging sort, such as insertion or bubble sort, by starting the comparison and exchange of elements with elements that are far apart before finishing with neighboring elements. Starting with far apart elements can move some out-of-place elements into position faster than a simple nearest neighbor exchange.
Shellsort is a multi-pass algorithm. Each pass is an insertion sort of the sequences consisting of every h-th element for a fixed gap h (also known as the increment). This is referred to as h-sorting. Shell sort is unstable,that is, it may change the relative order of elements with equal values.
It has "natural" behavior, in that it executes faster when the input is partially sorted.

Shell Sort In Action

Algorithm/Pseudo-Code:

Using Marcin Ciura's gap sequence, with an inner insertion sort.

/* Double-Click To Select Code */
# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]
 
foreach (gap in gaps)
{
    # Do an insertion sort for each gap size.
    for (i = gap; i < n; i += 1)
    {
        temp = a[i]
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        a[j] = temp
    } 
}

Here is the C Code for Shell Sort:

/* Double-Click To Select Code */

#include <stdio.h>
#include <conio.h>
#define MAX 20

void main()
{
 int arr[MAX],i,j,k,n,increment;
 clrscr();
 printf("Enter the number of elements: ");
 scanf("%d",&n);
 printf("\nEnter %d elements : \n",n);
 for(i=0 ; i<n ; i++)
 scanf("%d",&arr[i]);

 printf("\nUnsorted list is:\n");
 for (i = 0; i < n; i++)
 {
  printf("%4d",arr[i]);
 }
 increment=5;

 /*ACTUAL LOGIC STARTS*/

 while(increment>=1)
 {
  for(j=increment ; j<n ; j++)
  {
   k=arr[j];
   for(i = j-increment ; i >= 0 && k<arr[i] ; i = i-increment)
   arr[i+increment]=arr[i];
   arr[i+increment]=k;
  }
  increment=increment-2;  /*Decrease the incrementement*/
 }
 printf("\n\nSorted list is:\n");
 for (i = 0 ; i<n ; i++)
 {
  printf("%4d",arr[i]);
 }
 printf("\n\n *WWW.CODINGBOT.NET*");
 getch();
}

Output of Program:

Please Comment If You Liked This Post !! 

This article uses material from the Wikipedia article Shell Sort which is released under the Creative Commons Attribution-Share-Alike License 3.0

Do you like this post? Please link back to this article by copying one of the codes below.

URL: http://www.codingbot.net/2013/05/shell-sort-c-code-and-algorithm.html HTML link code: <a href="http://www.codingbot.net/2013/05/shell-sort-c-code-and-algorithm.html">Shell Sort C Code And Algorithm</a> Forum link code: [url=http://www.codingbot.net/2013/05/shell-sort-c-code-and-algorithm.html]Shell Sort C Code And Algorithm[/url]