Learn Quick Sort, quickly.
In this article, we shall laconically discuss quick sort, touching upon various aspects of it, such as its advantages, disadvantages, time complexity and how can we optimize its performance and its applications.
Just like Merge Sort, Quicksort is another efficient algorithm that uses the Divide and Conquer approach.
There are a variety of quickSort versions available, each of which selects pivot in a unique manner.
1.) As a rule of thumb, the first element should always be used as the pivot.
2.)Always choose the last element to be the pivot (implemented below)
3.)As the pivot, choose something at random.
4.)As a pivot, choose the median.
Partitioning is the most important process in quickSort (). Given an array and a pivot element x, the goal of partitions is to place x in the proper position in the sorted array, with all smaller elements (less than x) placed before x and all larger elements (greater than x) placed after x.
What is the Process of QuickSort?
> From the array, a pivot element is selected. As the pivot element, you can select any element from the array.
The pivot element, in this case, is the rightmost (i.e. last) element of the array.
> The elements that are smaller than the pivot element are placed on the left, while those that are larger are placed on the right.
> The steps below will help you reach the above arrangement.
At the pivot element, a pointer is fixed. Beginning with the first index, the pivot element is compared to the elements. A second pointer is set for the element higher than the pivot element if it is entered. The pivot element is now being compared to the other elements (a third pointer). If a smaller element than the pivot element is detected, the smaller element is replaced with the larger element discovered previously.
> The procedure continues until the second-to-last element has been attained. The pivot element is then replaced with the second pointer.
> Pivot elements are selected separately for the left and right sub-parts. The pivot elements are positioned correctly within these sub-parts. Step 2 is then repeated.
The sub-parts are further subdivided into smaller sub-parts until each sub-part is made up of only one element. The array is sorted at this point.
Pseudo Code for QuickSort :
/* low --> Starting index, high --> Ending index */
quickSort(arr[], low, high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is now
at right place */
pi = partition(arr, low, high);
quickSort(arr, low, pi - 1); // Before pi
quickSort(arr, pi + 1, high); // After pi
}
}
QuickSort Algorithm :
quickSort(array, leftmostIndex, rightmostIndex)
if (leftmostIndex < rightmostIndex)
pivotIndex <- partition(array,leftmostIndex, rightmostIndex)
quickSort(array, leftmostIndex, pivotIndex)
quickSort(array, pivotIndex + 1, rightmostIndex)
partition(array, leftmostIndex, rightmostIndex)
set rightmostIndex as pivotIndex
storeIndex <- leftmostIndex - 1
for i <- leftmostIndex + 1 to rightmostIndex
if element[i] < pivotElement
swap element[i] and element[storeIndex]
storeIndex++
swap pivotElement and element[storeIndex+1]
return storeIndex + 1Implementation of QuickSort :
/* C++ implementation of QuickSort */
#include <bits/stdc++.h>
using namespace std;
// A utility function to swap two elements
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element and indicates the right position of pivot found so far
for (int j = low; j <= high - 1; j++)
{
// If current element is smaller than the pivot
if (arr[j] < pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver Code
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
Output:
Sorted array:
1 5 7 8 9 10Iterative QuickSort:
// An iterative implementation of quick sort
#include <bits/stdc++.h>
using namespace std;
// A utility function to swap two elements
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
/* This function is same in both iterative and recursive*/
int partition(int arr[], int l, int h)
{
int x = arr[h];
int i = (l - 1);
for (int j = l; j <= h - 1; j++) {
if (arr[j] <= x) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[h]);
return (i + 1);
}
/* A[] --> Array to be sorted,
l --> Starting index,
h --> Ending index */
void quickSortIterative(int arr[], int l, int h)
{
// Create an auxiliary stack
int stack[h - l + 1];
// initialize top of stack
int top = -1;
// push initial values of l and h to stack
stack[++top] = l;
stack[++top] = h;
// Keep popping from stack while is not empty
while (top >= 0) {
// Pop h and l
h = stack[top--];
l = stack[top--];
// Set pivot element at its correct position
// in sorted array
int p = partition(arr, l, h);
// If there are elements on left side of pivot,
// then push left side to stack
if (p - 1 > l) {
stack[++top] = l;
stack[++top] = p - 1;
}
// If there are elements on right side of pivot,
// then push right side to stack
if (p + 1 < h) {
stack[++top] = p + 1;
stack[++top] = h;
}
}
}
// A utility function to print contents of arr
void printArr(int arr[], int n)
{
int i;
for (i = 0; i < n; ++i)
cout << arr[i] << " ";
}
// Driver code
int main()
{
int arr[] = { 4, 3, 5, 2, 1, 3, 2, 3 };
int n = sizeof(arr) / sizeof(*arr);
quickSortIterative(arr, 0, n - 1);
printArr(arr, n);
return 0;
}
Output:
1 2 2 3 3 3 4 5Analyzing Time-Complexities :
Worst Case Complexity : O(n^2)
Best Case Complexity : O(n*log n)
Average Case Complexity : O(n*log n)
Improved Pivot Selection :
Pick median value of three elements from data array:
> data[0], data[n/2], and data[n-1].
Use this median value as a pivot.
Applications of Quicksort[When to use?]:
We apply quicksort when :
> the programming language is good for recursion
> time complexity matters
> space complexity matters
References :
