Sorting > C Program

Sorting

Quick Sort, Heap Sort, Insertion Sort, Radix Sort, Merge Sort > C Program

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


void inserts(int a[],int n)
{
int i,j;
int temp;
for(i=1;i<n;i++)
{
temp=a[i];
for(j=i-1;j>=0&&a[j]>temp;j--)
a[j+1]=a[j];
a[j+1]=temp;
}
}
void createmax(int heap[],int n)
{
int c,root,temp,i;
for(i=1;i<n;i++)
{
c=i;
do
{
root=(c-1)/2;
if(heap[root]<heap[c])
{
temp=heap[root];
heap[root]=heap[c];
heap[c]=temp;
}
c=root;
}while(c!=0);
}
}

void downadjust(int heap[],int n)
{
int j,temp,root,c;
for(j=n-1;j>=0;j--)
{
temp=heap[0];
heap[0]=heap[j];
heap[j]=temp;
root=0;

do
{
c=2*root+1;
if((heap[c]<heap[c+1])&&c<j)
c++;
if((heap[root]<heap[c])&&c<j)
{
temp=heap[root];
heap[root]=heap[c];
heap[c]=temp;
}
root=c;
}while(c<j);
}
}
int partition(int a[],int l,int u)
{
int i,j;
int temp,v;
v=a[l];
i=l;
j=u+1;
do
{
do
i++;
while(a[i]<v&&i<=u);
do
j--;
while(v<a[j]&&j>=l);
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}while(i<j);
a[l]=a[j];
a[j]=v;
return(j);
}
void quicksort(int a[],int l,int u)
{
int i,j;
if(l<u)
{
j=partition(a,l,u);
quicksort(a,l,j-1);
quicksort(a,j+1,u);
}
}
void radix_sort(int arr[], int n)
{
 int bucket[10][5],buck[10],b[10];
 int i,j,k,l,num,div,large,passes;

 div=1;
 num=0;
 large=arr[0];

 for(i=0 ; i<n ; i++)
 {
  if(arr[i] > large)
   {
    large = arr[i];
   }

  while(large > 0)
  {
   num++;
   large = large/10;
  }

  for(passes=0 ; passes<num ; passes++)
  {
   for(k=0 ; k<10 ; k++)
   {
    buck[k] = 0;
   }
   for(i=0 ; i<n  ;i++)
   {
    l = ((arr[i]/div)%10);
    bucket[l][buck[l]++] = arr[i];
   }

   i=0;
   for(k=0 ; k<10 ; k++)
   {
    for(j=0 ; j<buck[k] ; j++)
    {
     arr[i++] = bucket[k][j];
    }
   }
   div*=10;
  }
 }
}
void mergeSort(int arr[],int low,int mid,int high){

    int i,m,k,l,temp[MAX];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){

if(arr[l]<=arr[m]){
    temp[i]=arr[l];
    l++;
}
else{
    temp[i]=arr[m];
    m++;
}
i++;
    }

    if(l>mid){
for(k=m;k<=high;k++){
    temp[i]=arr[k];
    i++;
}
    }
    else{
for(k=l;k<=mid;k++){
    temp[i]=arr[k];
    i++;
}
    }

    for(k=low;k<=high;k++){
arr[k]=temp[k];
    }
}

void partitions(int arr[],int low,int high){

    int mid;

    if(low<high){
mid=(low+high)/2;
partitions(arr,low,mid);
partitions(arr,mid+1,high);
mergeSort(arr,low,mid,high);
    }
}



void main()
{
int i,j,k,n,a[10];
int temp;
clrscr();
printf("\nEnter the no of elements");
scanf("%d",&n);
printf("\nEnter the elements");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nThe sorted list through quicksort: ");
quicksort(a,0,n-1);
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\nThe sorted list through heapsort: ");
createmax(a,n);
downadjust(a,n);
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\nThe sorted list through insertion sort: ");
inserts(a,n);
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\nThe sorted list through radix sort: ");
radix_sort(a,n);
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\nThe sorted list through mergesort: ");
partitions(a,0,n-1);
for(i=0;i<n;i++)
printf("%d ",a[i]);
getch();
}