Objective: C program to perform Quick sort using the divide and conquer method
Concept: Quick Sort divides the array according to the value of elements. It rearranges elements of a given array A[0..n-1] to achieve its partition, where the elements before position s are smaller than or equal to A[s] and all the elements after position s are greater than or equal to A[s].
Algorithm:
Step 1: Start
Step 2: Declare the variables.
Step 3: Enter the elements to be sorted using the get()function.
Step 4: Divide the array list into two halves the lower array list and upper array list using the merge sort function.
Step 5: Sort the two array list.
Step 6: Combine the two sorted arrays.
Step 7: Display the sorted elements.
Step 8: Stop
Time complexities: Quick sort has an average time of O(n log n) on n elements. Its worst case time is O(n²)
#include <stdio.h>
#include <conio.h>
void qsort();
int n;
void main()
{
int a[100],i,l,r;
clrscr();
printf("\nENTER THE SIZE OF THE ARRAY: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\nENTER NUMBER-%d: ",i+1);
scanf("%d",&a[i]);
}
printf("\nTHE ARRAY ELEMENTS BEFORE SORTING: \n");
for(i=0;i<n;i++)
{
printf("%5d",a[i]);
}
l=0;
r=n-1;
qsort(a,l,r);
printf("\nTHE ARRAY ELEMENTS AFTER SORTING: \n");
for(i=0;i<n;i++)
printf("%5d",a[i]);
getch();
}
void qsort(int b[],int left,int right)
{
int i,j,p,tmp,finished,k;
if(right>left)
{
i=left;
j=right;
p=b[left];
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
{
tmp=b[i];
b[i]=b[j];
b[j]=tmp;
}
}
tmp=b[left];
b[left]=b[j];
b[j]=tmp;
qsort(b,left,j-1);
qsort(b,i,right);
}
return;
}
