What is Quick Sort?
Quick Sort is a Divide and Conquer algorithm based on Recursion. It works around taking a pivot and placing it at the correct index.
How it works?
In this sorting algorithm we compare all the elements of the array to the pivot we choose and then we put all the elements smaller than pivot before the pivot and larger than the pivot after the pivot. When the pivot is at the correct index we recursively call the elements at the left and right of the pivot and follow the same till we receive a sorted array, unless the array is already sorted.
How to choose the pivot?
There are multiple ways to choose the pivot such as :
- Choose it randomly.
- Choose the first or the last element always.
- Choose the median always.
Important points :
- Not Stable.
- In - Place.
Dry Run
Complete Code
// This Code is written in Java
static void quickSort(int[] arr, int low, int high){
// Low and high are for figuring out which,
// part of array you are working
// base condition
if(low >= high){
return;
}
// These variables are for swapping
int start = low;
int end = high;
int mid = start + (end - start) / 2;
// We have to move pivot to the correct index
int pivot = arr[mid];
// Main Loop
while(start <= end){
while(arr[start] < pivot){
start++;
}
while(arr[end] > pivot){
end-- ;
}
// This will be true when the above conditions are violated
if(start <= end){
// Swap only happens if the array is not already sorted
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
// Now our pivot is at the correct index
// Dividing the array into 2 recursive calls
// This will only call when start > pivot
// And End < pivot
quickSort(arr, low, end);
quickSort(arr, start, high);
}
}
Time Complexity
Worst Case : O(N^2)
Best Case : O(N logN)
Why Quick Sort?
- Cache Friendly, good locality of reference when used for arrays.
- Takes less space and time.
- Quick Sort is also tail recursive, therefore tail call optimizations is done.