Programming Geek
Rated 4.7/5 based on 1446 reviews

C Program for Different Sorting Algorithm

Here goes a C program which implements the different sorting algorithms like bubble sort, selection sort, insertion sort, merge sort and quick sort.

//Implementation of different sorting algorithms like bubble sort, selection sort, insertion sort, mergesort, quicksort in C
/**
*
*@author VIKASH VIK VIKASHVVERMA
*
*/

#include<stdio.h>

//bubble sort
void bubblesort(int arr[],int n)
{
 int i,j,temp;
 for(i=0;i<n;i++)
 {
  for(j=1;j<n-i;j++)
  {
   if(arr[j-1]>arr[j])
   {
    temp=arr[j];
    arr[j]=arr[j-1];
    arr[j-1]=temp;
   }
  }
 }
}

//selection sort
void selectionsort(int arr[],int n)
{
 int temp,min,i,j;
 
 for(i=0;i<n;i++)
 { min=i;
  for(j=i+1;j<n;j++)
  {
   if(arr[j]<arr[i])
   {
    min=j;
   }
  }

  temp=arr[min];
  arr[min]=arr[i];
  arr[i]=temp;  
 }
}


//insertion sort
void insertionsort(int arr[],int n)
{
 int i,j,temp;
 
 for( i=0;i<n;i++)
 {
  temp=arr[i];
  for(j=i-1;j>=0;j--)
  {
   if(arr[j]>temp)
   {
    arr[j+1]=arr[j];
   }
   else
   break;
  }
  arr[j+1]=temp;
 }
}


//merge 
void merge(int arr[],int l,int m,int r)
{
 int len,i,j,k,*c;
 len=r-l+1;
 c=(int*)malloc(sizeof(int)*len);
 i=0;
 j=l;
 k=m+1;
 while(j<=m && k<=r)
 {
  if(arr[j]<arr[k])
  {
   c[i++]=arr[j++];
   
  }
  else
  {
   c[i++]=arr[k++];
   
  }
  
 }
 
 while(j<=m)
 {
  c[i++]=arr[j++];
 }
 
 while(k<=r)
 {
  c[i++]=arr[k++];
 }
 i=0;
 while(l<=r)
 {
  arr[l++]=c[i++];
 }
}


//mergesort
void mergesort(int arr[],int l,int r)
{
 int m=(l+r)/2;
 if(l<r)
 {
  mergesort(arr,l,m);
  mergesort(arr,m+1,r);
  merge(arr,l,m,r);
 }
}


//partition the list
int partition(int arr[],int l,int r)
{
 int j=l+1,k=r,temp;
 int num=arr[l];
 while(k>=j)
 {
  while(arr[j]<num)
  j++;
  while(arr[k]>num)
  k--;
  
  if(k>j)
  {
   temp=arr[j];
   arr[j]=arr[k];
   arr[k]=temp;
   
  }
 }
 temp=arr[k];
 arr[k]=arr[l];
 arr[l]=temp;
 return k;
}

//quicksort
void quicksort(int arr[],int l,int r)
{ int m;
 if(r>l)
 {
  m=partition(arr,l,r);
  quicksort(arr,l,m-1);
  quicksort(arr,m+1,r);
 }
}

//execution logic
void main()
{
 int i,n,*arr,choice;
 printf("Enter No. of elements:");
 scanf("%d",&n);
 printf("\nEnter %d elements:",n);
 arr=(int*)malloc(sizeof(int)*n);
 for(i=0;i<n;i++)
 scanf("%d",&arr[i]);
 printf("\n\tMenu\n---------------------------");
 printf("\n1 : to apply bubble sort!");
 printf("\n2 : to apply selection sort!");
 printf("\n3 : to apply insertion sort!");
 printf("\n4 : to apply mergesort");
 printf("\n5 : to apply quicksort!");
 printf("\n6 : to apply any sorting algorithm!");
 printf("\nAny other number to exit!");
 printf("\nEnter your choice:");
 scanf("%d",&choice);
 switch(choice)
 {
  case 1: bubblesort(arr,n);
    break;
  case 2: selectionsort(arr,n);
    break;
  case 3: insertionsort(arr,n);
    break;
  case 4: mergesort(arr,0,n-1);
    break;
  case 5: quicksort(arr,0,n-1);
    break;
  case 6: quicksort(arr,0,n-1);
    break;
  default: exit(0);
    
 }
 
 printf("\n\tSorted Numbers:\n-----------------------------\n");
 for(i=0;i<n;i++)
 printf("%d\t",arr[i]);
}//main

No comments :

Post a Comment