Google

Sorting – Shell sort

Written on:November 25, 2012
Comments are closed

Shell Sort: 

Shell sort is quite similar to that of insertion sort with the only difference that in shell sort, higher values of k are considered.  Whereas insertion sort assumes k to be 1.  If k=4, then every 4th element is compared, if it is 3 then every 3rd element is compared.  Thus k=m means every mth element gets compared with each other and is swapped.

The value of k is decremented after each scan.  The file is sorted, when k becomes 1 and swapping is performed for k = 1.  The difference in original and decremented value(i.e. difference in k) may be generated using a hash function, which returns the number of decrements in k. say k=4, then k=2 and finally k=1.  k=3 is skipped.  or (k=8, k=4, k=2, k=1) or (k=4, k=3, k=2, k=1).

If k is taken as 1 only, then it is no more shell sort, it becomes insertion sort.

Example:



/*Program to implement Shell Sort*/

#include <stdio.h>
#include <conio.h>

#define MAX 5

void shellsort(int x[],int n,int incrmnts[],int numinc)
{
int incr,j,k,span,y;
for(incr=0;incr<numinc;incr++)
{
span=incrmnts[incr];
for(j=span;j<n;j++)
{
y=x[j];
for(k=j-span;k>=0 && y<x[k]; k-=span)
x[k+span]=x[k];
x[k+span]=y;
}
}
}
/*
A hash function may be defined as follows:
Let n be the size of the array (total number of elements).
Then begin from (n-3) upto 1.
Example: Let there are 8 elements, then n=8
increments array will hold 5,3,1 for (n-3), (n-5), (n-7) respectively.
and ct=3, where ct is numinc.
*/

int hash(int arr[],int n)
{
int i,j=0,ct=0;
for(i=3;(n-i)>0;i+=2)
{
arr[j++]=n-i;
ct++;
}
if(arr[j-1]!=1)
{arr[j]=1;
ct++;
}
return ct;
}

void main()
{
int arr[MAX],i,incrmnts[MAX], total_incr;
for(i=0;i<MAX;i++)
{
incrmnts[i]=0;
printf(“Enter value?”);
scanf(“%d”,&arr[i]);
}
total_incr = hash(incrmnts,MAX);
shellsort(arr,MAX,incrmnts,total_incr);
printf(“Sorted array is: “);
for(i=0;i<MAX;i++)
{
printf(“%d\t”,arr[i]);
}
getch();
}

Sorry, the comment form is closed at this time.