introduce
quickSort is a divide and rule algorithm. It selects an element as a pivot and partitions a given array around the selected pivot. There are many different versions of quickSort that select pivots in different ways.
1.Always select the first element as the pivot 2.Always select the last element as the pivot (implemented below) 3.Select a random element as the pivot 4.Select the median as the pivot
The key process in quickSort (ascending order) is partition(). The goal of partitioning is to give an array and the element X of an array as the pivot, put X in the correct position in the sorted array, put all smaller elements (less than x) before x, and put all larger elements (more than x) after X. All of this should be done in linear time.
Partition algorithm
There are many ways to partition. The following pseudo code uses the method given in the CLRS book. The logic is very simple. We start with the leftmost element and track the index of smaller or equal pivot elements as I. During traversal, if we find a smaller element, we exchange the current element with arr[i]. Otherwise, we ignore the current element.
Pseudo code of recursive quick sort function
/* 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
}
}
Pseudo code of partition()
/* 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 */
partition (arr[], low, high)
{
// pivot (Element to be placed at right position)
pivot = arr[high];
i = (low – 1) // Index of smaller element and indicates the
// right position of pivot found so far
for (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] and arr[j]
}
}
swap arr[i + 1] and arr[high])
return (i + 1)
}
Description of partition():
Consider: arr[] = {10, 80, 30, 90, 40, 50, 70}
Indexes: 0 1 2 3 4 5 6
low = 0, high = 6, pivot = arr[h] = 70
Initialize index of smaller element, i = -1
Traverse elements from j = low to high-1
j = 0: Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 0
arr[] = {10, 80, 30, 90, 40, 50, 70} // No change as i and j are same
j = 1: Since arr[j] > pivot, do nothing
j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 1
arr[] = {10, 30, 80, 90, 40, 50, 70} // We swap 80 and 30
j = 3 : Since arr[j] > pivot, do nothing // No change in i and arr[]
j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 2
arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 and 40 Swapped
j = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j]
i = 3
arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 and 50 Swapped
We come out of loop because j is now equal to high-1.
Finally we place pivot at correct position by swapping arr[i+1] and arr[high] (or pivot)
arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 and 70 Swapped
Now 70 is at its correct place. All elements smaller than 70 are before it and all elements greater than 70 are after it.
Since quick sort is a recursive function, we call the partition function again at left and right partitions
Again call function at right part and swap 80 and 90
code implementation
Implementation of quick sort using the last element as a pivot:
/* 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;
}
// This code is contributed by rathbhupendra
Implementation of quick sort using the first element as a pivot:
#include <iostream>
#include <algorithm>
using namespace std;
int partition(int arr[], int low, int high)
{
int i = low;
int j = high;
int pivot = arr[low];
while (i < j)
{
while (pivot >= arr[i])
i++;
while (pivot < arr[j])
j--;
if (i < j)
swap(arr[i], arr[j]);
}
swap(arr[low], arr[j]);
return j;
}
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
void printArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
int main()
{
int arr[] = {4, 2, 8, 3, 1, 5, 7,11,6};
int size = sizeof(arr) / sizeof(int);
cout<<"Before Sorting"<<endl;
printArray(arr, size);
quickSort(arr, 0, size - 1);
cout<<"After Sorting"<<endl;
printArray(arr, size);
return 0;
}
Time complexity analysis
The time taken for quick sorting can usually be written as follows:
T ( n ) = T ( k ) + T ( n − k − 1 ) + θ ( n ) T(n) = T(k) + T(n-k-1) + \theta(n) T(n)=T(k)+T(n−k−1)+θ(n)
The first two items are used for two recursive calls, and the last one is used for the partitioning process. k is the number of elements smaller than the pivot. The time taken by QuickSort depends on the input array and partition policy. The following are three cases:
Worst case:
The worst case occurs when the partitioning process always selects the largest or smallest element as the pivot. If we consider the above partitioning strategy, the last element is always selected as the pivot, and the worst case will occur when the array has been sorted in ascending or descending order. Here is the worst case scenario.
T ( n ) = T ( 0 ) + T ( n − 1 ) + θ ( n ) w h i c h i s e q u i v a l e n t t o T ( n ) = T ( n − 1 ) + θ ( n ) T(n) = T(0) + T(n-1) + \theta(n) \ which \ is \ equivalent \ to\ T(n) = T(n-1) + \theta(n) T(n)=T(0)+T(n−1)+θ(n) which is equivalent to T(n)=T(n−1)+θ(n)
The above recursive solution is: θ ( n 2 ) \theta(n^2) θ(n2)
Best case:
The best case occurs when the partitioning process always selects the middle element as the pivot. The following is a reproduction of the best case.
T ( n ) = 2 T ( n / 2 ) + θ ( n ) T(n) = 2T(n/2) + \theta(n) T(n)=2T(n/2)+θ(n)
The above recursive solution is: θ ( n L o g n ) \theta(nLogn) θ(nLogn)
Average:
To analyze the average situation, we need to consider all possible permutations of the array and calculate the time taken for each permutation, which does not seem easy. We can understand the average situation by considering the case where partitions put O(n/9) elements in one set and O(9n/10) elements in another set. The following is a reproduction of this case.
T ( n ) = T ( n / 9 ) + T ( 9 n / 10 ) + θ ( n ) T(n) = T(n/9) + T(9n/10) + \theta(n) T(n)=T(n/9)+T(9n/10)+θ(n)
The above recursive solution is: θ ( n L o g n ) \theta(nLogn) θ(nLogn)