How to write a C Program Quick Sort Using C Programming Language ?
Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order.
Quicksort is a divide-and-conquer sorting algorithm in which division is dynamically carried out (as opposed to static division in Merge sort).
The three steps of Quicksort are as follows:
Divide: Rearrange the elements and split the array into two subarrays and an element in between such that so that each element in the left subarray is less than or equal the middle element and each element in the right subarray is greater than the middle element.
Conquer: Recursively sort the two subarrays.
Combine: None.
#include<stdio.h>
int n;
main()
{
int a[20],i,l,r;
void qsort();
clrscr();
printf("enter how many elements do u want to enter: ");
scanf("%d",&n);
printf("enter the array elements: ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
l=0;
r=n-1;
qsort(a,l,r);
printf("final sorted array is: ");
for(i=0;i<n;i++)
printf("%d ",a[i]);
}
void qsort(int b[],int left,int right)
{
int i,j,k,p,temp,finished;
if(right>left)
{
i=left;
j=right;
p=b[left];
printf("\n P,the partioning element is: %d\n",p);
finished=0;
while(!finished)
{
do
{
++i;
}while((b[i]<=p)&&(i<=right));
while((b[j]>=p)&&(j>left))
{
--j;
}
if(j<i)
finished=1;
else
{
printf("\nswapping %d and %d. \n",b[i],b[j]);
temp=b[i];
b[i]=b[j];
b[j]=temp;
for(k=0;k<n;k++)
printf("%5d",b[k]);
printf("\n");
}
}
printf("\n I is greater than J,");
printf("so b[left] and b[j] are swapped.");
printf("Swapping %d and %d.\n\n",b[left],b[j]);
temp=b[left];
b[left]=b[j];
b[j]=temp;
for(k=0;k<n;k++)
printf("%5d",b[k]);
printf("\n");
printf("\nsub file one is : elements %d to %d.\n",left,j-1);
qsort(b,left,j-1);
printf("\nsub file two is : elements %d to %d.\n",i,right);
qsort(b,i,right);
}
else
{
if(right!=left)
printf("Right (%d) is less than Left(%d).\n",right,left);
else
{
printf("Right (%d) is less than Left(%d).\n",right,left);
printf("subfile has only one element.\n");
}
}
return;
}
C Program's related to How to Quick Sort Using C Programming Language :
1. How to Write a c program for bubble sort algorithm.2. How to Write a c program for insertion sort algorithm.
3. How to Write a c program for selection sort algorithm.
4. How to Write a c program for quick sort algorithm.
5. How to Write a c program for heap sort algorithm.
6. How to Write a c program for merge sort algorithm.
7. How to Write a c program for shell sort algorithm.