QUICK SORT


SOURCE CODE:

“Quick.h” File:

#include<stdio.h>
#include<conio.h>
#define cutoff (3)
void swap(int *x,int *y)
{
   int temp;
   temp=*x;
   *x=*y;
   *y=temp;
}
void display(int A[],int n)
{
   int i;
   for(i=0;i<n;i++)
      printf("%d\t",A[i]);
}
void insertionsort(int A[],int n)
{
   int j,p,temp;
   for(p=1;p<n;p++)
   {
      temp=A[p];
      for(j=p;j>0&&A[j-1]>temp;j--)
      A[j]=A[j-1];
      A[j]=temp;
   }
}
int median(int A[],int left,int right)
{
   int center=(left+right)/2;
   if(A[left]>A[center])
      swap(&A[left],&A[center]);
   if(A[left]>A[right])
      swap(&A[left],&A[right]);
   if(A[center]>A[right])
      swap(&A[center],&A[right]);
   if(A[left]<=A[center]<=A[right])
      swap(&A[center],&A[right-1]);
   return A[right-1];
}
void quicksort(int A[],int left,int right)
{
   int i,j,pivot;
   if(left+cutoff<=right)
   {
      pivot=median(A,left,right);
      i=left;
      j=right-1;
      for(;;)
      {
     while(A[++i]<pivot)
     {}
     while(A[--j]>pivot)
     {}
     if(i<j)
        swap(&A[i],&A[j]);
     else
        break;
      }
      swap(&A[i],&A[right-1]);
      quicksort(A,left,i-1);
      quicksort(A,i+1,right);
   }
   else
      insertionsort(A+left,right-left+1);
}

“Quick.c” file

#include"quick.h"
void main()
{
int A[20],n,i;
clrscr();
printf("\n how many numbers do u want to sort:\t");
scanf("%d",&n);
printf("\n\n Enter the values");
for(i=0;i<n;i++)
{
   printf("\n A[%d]\t",i);
   scanf("%d",&A[i]);
}
quicksort(A,0,n-1);
display(A,n);
getch();
}

OUTPUT:

How many numbers do u want to sort:    5

 Enter the values
 A[0]   25

 A[1]   10

 A[2]   89

 A[3]   65

 A[4]   15
       

10              15              25              65              89
Previous
Next Post »

Still not found what you are looking for? Try again here.