Quick sort
Introduction:
This is a comparison based sort where we select a pivot element from the array and put it in the correct place in the array such that all the elements to the left are less than or equal to pivot and all the elements to the right are greater than or equal to pivot
similary we do the same with the left and right parts recursively.
Problem Statement:
Sort an array of n integers
Algorithm
1. we have an array of n numbers.
2. select a pivot and partition the array into two parts such that all the elements in the left partition are less than pivot and all the elements in right partition are greater than or equal to pivot
3. repeat step to for left and right partitions till partition size is 1
4. In this algorithm we select the pivot as the last element.
Pseudo code :
quick_partition(a[], start, end):
pivot = end
i = start
j = i
while j < end:
if a[j] <= a[pivot]:
swap(a[i], a[j])
i++
j++
swap(a[i], a[pivot])
pivot = i
return pivot
quick_sort(a, start, end):
if end <= start:
return
pivot = quick_partition(a, start, end)
quick_sort(a, start, pivot-1)
quick_sort(a, pivot+1, end)
Code :
#include <bits/stdc++.h>
using namespace std;
int quick_partition(int a[], int start, int end)
{
int pivot = end;
int i = start;
int j = i;
/* for every element a[j] if a[j] <= a[pivot]
then swap it with position a[i] and increse both i and j by 1
else increase j by 1*/
while (j < end)
{
if (a[j] <= a[pivot])
{
swap(a[i], a[j]);
i++;
}
j++;
}
/* finally i will be the first position where a[i]>a[pivot]
so we swap these and pivot will be ith position*/
swap(a[i], a[pivot]);
pivot = i;
return pivot;
}
void quick_sort(int a[], int start, int end) // quick_sort(a,0,n-1)
{
if (end <= start)
{
return;
}
int pivot = quick_partition(a, start, end); // partition
quick_sort(a, start, pivot - 1); // quick sort left part
quick_sort(a, pivot + 1, end); // quick sort right part
}
int main()
{
int n;
cout << "Enter n: ";
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
quick_sort(a, 0, n - 1);
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
printf("\n");
}
Complexity Analysis :
Complexity lies between \(O(nlogn)\) to \(O(n^2)\)
worst case : \(O(n^2)\) when array is already sorted