Quick sort in C C++
The popular one
Also known as Selection-exchange sort, and Partition-exchange sort
Explanation
Take first element as pivot and assign it to x.
Take two pointers. i and j. i at first element and j at last element. Increment i till a greater element than pivot is obtained and decrement j until smaller element than pivot is obtained.
Element at i is greater than pivot and element at j is smaller than pivot.
Now swap these two elements and continue incrementing i and decrementing j till j is not smaller than i.
Again found the elements. Now swap them.
Again obtained required elements at i and j. Swap them now and further increment i and decrement j.
Stop now as j < i.
Swap the pivot element and element at j.
We can observe that 50 is positioned at its sorted position, that is the position at which it will be present in the sorted list.
Now the list is divided into two sections.
Now call the QuickSort function recursively on the left and right sublist.
The final outcome of the recursive will be a sorted array.
As the list is dividing or splitting into 2 sublists, time complexity of average case is O(nlogn) and not O(n^2).
Important points
- Quick sort is a self sorting technique
- Each element sorts itself to a position such that all elements preceding this element is smaller than it and all the elements succeeding is greater than it.
- Therefore each element finds a perform spot for itself and hence the list gets sorted.
- Time complexity is O(nlogn) for best and average case and O(n^2) for the worst case.
- Best case scenario is when partitioning takes place around the middle of the list.
- Worst case scenario is when partitioning takes place at either of the two ends.
- Not adaptive
- Not stable
Program for Quick sort in C language
#include<stdio.h>
#include<stdlib.h>
void swap(int *p, int *q)
{
int temp;
temp = *p;
*p = *q;
*q = temp;
}
int partition(int A[],int l,int h)
{
int pivot=A[l];
int i=l,j=h;
do
{
do{i++;}while(A[i]<=pivot);
do{j--;}while(A[j]>pivot);
if(i<j)swap(&A[i],&A[j]);
}while(i<j);
swap(&A[l],&A[j]);
return j;
}
void QuickSort(int A[],int l, int h)
{
int j;
if(l<h)
{
j=partition(A,l,h);
QuickSort(A,l,j);
QuickSort(A,j+1,h);
}
}
int main()
{
int A[11] = {1,5,2,1,6,3,6,2,5,10};
int i;
A[10] = INT32_MAX;
QuickSort(A,0,10);
for(i=0;i<10;i++)
{
printf("%d ",A[i]);
}
return 0;
}
