Suppose n different values are stored in numeric array a from the location 0 to n-1.Consider a dummy value which is largest among all input values. Place this dummy value at the n+1 location i.e. logical position a[n].In short place this dummy value after the last input value.The dummy value is used for sorting as follows -
1. a[n]=dummy value
2. Consider two indices l(low) and h(high).Initialize l to 0 and h to n-1.
3. If the lower limit is less than the higher limit then do the following -
a. Consider temporary variable k.Copy the content of the position l i.e. a[l] into k.Here k acts as a reference value for creating two partitions.
b. Consider two indices i and j.Initialize i to lower limit l and j to higher limit h+1.
c. While i < j do the following
i. While value of a[i] is less than or equal to k and i is less than h,increment i.
ii. While value of a[j] is greater than or equal to k and j is greater than l ,decrement j.
iii. If i is less than j ,then swap the values of a[i] and a[j].
d. If j is not equal to l ,then swap the values of a[j] and a[l].
e. After swapping a[l] and a[j],two partitions are created.First partition is from l to j-1 and second partition is from j+1 to h.
4. Use the steps from 2 to 3 for each partition till no more partition is possible.
5. After creating all the partitions , the input values are sorted automatically.
#include < stdio.h >
#include < conio.h >
void main()
{
int a[50];
int n;
clrscr();
printf("\nEnter n: ");
scanf("%d",&n);
read_data(a,n);
a[n]=9999;
printf("\nBefore sort :");
print_data(a,n);
qsort(a,0,n-1,n);
printf("\nAfter sort :");
print_data(a,n);
}
int read_data(int a[],int max)
{
int i;
printf("\nEnter %d values \n",max);
for(i=0; i < max; i++)
{
scanf("%d",&a[i]);
}
return;
}
int print_data(int a[],int max)
{
int i;
for(i=0; i < max; i++)
{
printf("%4d",a[i]);
}
return;
}
int quick_sort(int a[],int l,int h,int n)
{
int i,j,k,t;
if(l < h)
{
k=a[l];
i=l;
j=h+1;
while( i < j)
{
while( i < h && a[i] <= k)
i++;
while( j > l && a[j] > =k)
j--;
if( i < j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
if( l != j)
{
t=a[l];
a[l]=a[j];
a[j]=t;
}
printf("\nOutput :");
print_data(a,n);
qsort(a,l,j-1,n);
qsort(a,j+1,h,n);
}
//print_data(a,n);
return;
}
No comments:
Post a Comment