Quick Sort:
Quicksort is a recursive sorting technique used to sort elements in decreasing or non-decreasing order. It is based on the concept of Divide-and-Conquer(also used in Merge-sort).
In this sorting technique we start by choosing a Pivot element which could be any element and at the end of each iteration the pivot element reaches its correct position in the set of elements. This way the quick sort makes it to completion in O(nlog n) complexity which makes it efficient over most other sorting algorithms which have time complexity O(n^2).
Here's the code for quick sort:
#include<stdio.h>
#define MAX 10
int partition(int[],int,int);
void quick(int[],int,int);
void main()
{
int A[MAX]={12,44,10,1,94,5,78,23,56,3};int b=0;int e=9;int i;
printf("Original array is: ");
for(i=0;i<10;i++)
{
printf("%d ",A[i]);
}
quick(A,b,e);
printf("\n\nQuick sorted array is: ");
for(i=0;i<10;i++)
{
printf("%d ",A[i]);
}
}
void quick(int A[],int b,int e)
{
int q;
if(b>=e)
return;
else
{
q=partition(A,b,e);
quick(A,b,q-1);
quick(A,q+1,e);
}
}
int partition(int A[],int b,int e)
{
int temp;
int left=b;int right=e;int loc=b;
while(1)
{
while(A[loc]<=A[right]&&loc!=right)
right--;
if(loc==right)
return loc;
if(A[loc]>A[right])
{
temp=A[right];
A[right]=A[loc];
A[loc]=temp;
loc=right;
right--;
}
while(A[loc]>=A[left] && loc!=left)
left++;
if(loc==left)
return loc;
if(A[loc]<A[left])
{
temp=A[left];
A[left]=A[loc];
A[loc]=temp;
loc=left;
left++;
}
}
}
Below is the output:
Note: The code is written in DEVC++ and it might not run in TurboC++ or other IDEs because DEVC++ allows us to omit some code(which is useful). So if you are facing any problem regarding compilation please let me know in the comment box and i will try to resolve your query as ASAP!!!.
