Sorting Techniques - Shell Sort and Merge Sort


Arranging a list of elements in an order (ascending or descending) is called sorting. There are different types of sorting techniques in which one technique is better than its predecessor. In this article, I am going to discuss the two sorting techniques shell sort and merge sort with their C programs.

Shell Sort


It is a sorting technique which comes under the category of sorting by exchange. The procedure of shell sort is as follows. First, take a value as increment. Generally, increment value is taken as half of the length of the array used to store the list of elements. Sort the list in increments i.e. sort elements in position 1, 1+increment … and then sort elements in position 2, 2+increment … and so on until all the elments i the list are considered. Now, reduce the increment value and repeat the above procedure. Keep on doing this until the increment value reaches 1. Therefore, shell sort is also called diminishing increment sort. To understand this clearly, let us perform shell sort on the list 78, 46, 76, 12, 34, 90, 45, 59, 13, 77 (n=10).

A[1]=78 A[2]=46 A[3]=76 A[4]=12 A[5]=34 A[6]=90 A[7]=45 A[8]=59 A[9]=13 A[n]=77

Increment=5
A[1]=78 A[6]=90 becomes A[1]=78 A[6]=90
A[2]=46 A[7]=45 becomes A[2]=45 A[7]=46
A[3]=76 A[8]=59 becomes A[3]=59 A[8]=76
A[4]=12 A[9]=13 becomes A[4]=12 A[9]=13
A[5]=34 A[n]=77 becomes A[5]=34 A[n]=77

A[1]=78 A[2]=45 A[3]=59 A[4]=12 A[5]=34 A[6]=90 A[7]=46 A[8]=76 A[9]=13 A[n]=77

Increment=3
A[1]=78 A[4]=12 A[7]=46 A[n]=77 becomes A[1]=12 A[4]=46 A[7]=77 A[n]=78
A[2]=45 A[5]=34 A[8]=76 becomes A[2]=34 A[5]=45 A[8]=76
A[3]=59 A[6]=90 A[9]=13 becomes A[3]=13 A[6]=59 A[9]=90

A[1]=12 A[2]=34 A[3]=13 A[4]=46 A[5]=45 A[6]=59 A[7]=77 A[8]=76 A[9]=90 A[n]=78

Increment=1
A[1]=12 A[2]=34 A[3]=13 A[4]=46 A[5]=45 A[6]=59 A[7]=77 A[8]=76 A[9]=90 A[n]=78
becomes (Insertion Sort)
A[1]=12 A[2]=13 A[3]=34 A[4]=45 A[5]=46 A[6]=59 A[7]=76 A[8]=77 A[9]=78 A[n]=90

A[1]=12 A[2]=13 A[3]=34 A[4]=45 A[5]=46 A[6]=59 A[7]=76 A[8]=77 A[9]=78 A[n]=90

C Program for Shell Sort


Program
#include<stdio.h>
#include<conio.h>
void main(void)
{
int list[25];
int i,d,n;
int temp;
clrscr();
printf("\n Enter the number of elements in the list : ");
scanf("%d",&n);
printf("\n Enter the elements in the list : ");
for(i=0;i<n;i++)
scanf("%d",&list[i]);
d=n;
do
{
d=(d+1)/2;
for(i=0;i<n-d;i++)
{
if(list[i]>list[i+d])
{
temp=list[i+d];
list[i+d]=list[i];
list[i]=temp;
}
}
}
while(d>1);
printf("\n The list after sorting is : ");
for(i=0;i<n;i++)
printf("%d ",list[i]);
getch();
}

Output
Enter the number of elements in the list : 10
Enter the elements in the list : 78 46 76 12 34 90 45 59 13 77
The list after sorting is : 12 13 34 45 46 59 76 77 78 90

The time complexity of shell sort is O(nlogn) in best case and O(nlog22n) in worst case. Average case time complexity depends on the value of increment. And space complexity of shell sort in O(n) in worst case.

Merge Sort


It is a sorting technique which comes under the category of sorting by merging. The procedure of merge sort is as follows. Divide the list into 2 almost equal sized sub lists and apply merge sort on each of them i.e. divide these sub lists further and apply merge sort on each of them. Do this until every sub list contains only 1 element. Then, merge the sub lists in sorted order. To understand this clearly, let us perform merge sort on the list 78, 46, 76, 12, 34, 90, 45, 59, 13, 77. Imagine the example in tree form for more clarity.

Divide 78 46 76 12 34 90 45 59 13 77 into two sub lists 78 46 76 12 34 and 90 45 59 13 77.

Divide 78 46 76 12 34 into two sub lists 78 46 76 and 12 34
Divide 78 46 76 into two sub lists 78 46 and 76
Divide 78 46 into two sub lists 78 and 46
Divide 12 34 into two sub lists 12 and 34
Merge 12 and 34 into 12 34
Merge 78 and 46 into 46 78
Merge 46 78 and 76 into 46 76 78
Merge 46 76 78 and 12 34 into 12 34 46 76 78

Divide 90 45 59 13 77 into two sub lists 90 45 59 and 13 77
Divide 90 45 59 into two sub lists 90 45 and 59
Divide 90 45 into two sub lists 90 and 45
Divide 13 77 into two sub lists 13 and 77
Merge 13 and 77 into 13 77
Merge 90 and 45 into 45 90
Merge 45 90 and 59 into 45 59 90
Merge 45 59 90 and 13 77 into 13 45 59 77 90

Merge 12 34 46 76 78 and 13 45 59 77 90 into 12 13 34 45 46 59 76 77 78 90

C Program for Merge Sort


Program
#include<stdio.h>
#include<conio.h>
void mergesort(int a[],int low,int mid,int high);
void partition(int a[],int low,int high);
void main(void)
{
int i,n,a[25];
clrscr();
printf("Enter number of elements : ");
scanf("%d",&n);
printf("Enter the list before sorting : ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
partition(a,0,n-1);
printf("The list after sorting is :");
for(i=0;i<n;i++)
printf("%d ",a[i]);
getch();
}
void partition(int a[],int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
partition(a,low,mid);
partition(a,mid+1,high);
mergesort(a,low,mid,high);
}
}
void mergesort(int a[],int low,int mid,int high)
{
int i,k,l,m,temp[25];
l=low;
i=low;
m=mid+1;
while((l<=mid)&&(m<=high))
{
if(a[l]<=a[m])
{
temp[i]=a[l];
l++;
}
else
{
temp[i]=a[m];
m++;
}
i++;
}
if(l>mid)
{
for(k=m;k<=high;k++)
{
temp[i]=a[k];
i++;
}
}
else
{
for(k=l;k<=mid;k++)
{
temp[i]=a[k];
i++;
}
}
for(k=low;k<=high;k++)
{
a[k]=temp[k];
}
}

Output
Enter number of elements : 10
Enter the list before sorting : 78 46 76 12 34 90 45 59 13 77
The list after sorting is : 12 13 34 45 46 59 76 77 78 90

The time complexity of merge sort mentioned above is O(n) in the best case and O(nlogn) in the worst case and the average case. And space complexity of merge sort mentioned above is O(n) in the worst case.


Comments

No responses found. Be the first to comment...


  • Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
  • No HTML formatting and links to other web sites are allowed.
  • This is a strictly moderated site. Absolutely no spam allowed.
  • Name:
    Email: