Can QuickSort be implemented in O(nLogn) worst case time complexity?
The worst-case time complexity of a typical implementation of QuickSort is O(n2). The worst case occurs when the picked pivot is always an extreme (smallest or largest) element. This happens when the input array is sorted or reverses sorted and either the first or last element is picked as a pivot.
Although randomized QuickSort works well even when the array is sorted, there is still possible that the randomly picked element is always extreme. Can the worst case be reduced to O(nLogn)?
The answer is yes, we can achieve O(nLogn) worst case. The idea is based on the fact that the median element of an unsorted array can be found in linear time. So we find the median first, then partition the array around the median element.
Following is a C++ implementation based on the above idea. Most of the functions in below program are copied from K’th Smallest/Largest Element in Unsorted Array | Set 3 (Worst Case Linear Time)
C++
/* A worst case O(nLogn) implementation of quicksort */ #include <algorithm> #include <climits> #include <cstring> #include <iostream> using namespace std; // Following functions are taken from http://goo.gl/ih05BF int partition( int arr[], int l, int r, int k); int kthSmallest( int arr[], int l, int r, int k); /* A O(nLogn) time complexity function for sorting arr[l..h] */ void quickSort( int arr[], int l, int h) { if (l < h) { // Find size of current subarray int n = h - l + 1; // Find median of arr[]. int med = kthSmallest(arr, l, h, n / 2); // Partition the array around median int p = partition(arr, l, h, med); // Recur for left and right of partition quickSort(arr, l, p - 1); quickSort(arr, p + 1, h); } } // A simple function to find median of arr[]. This is // called only for an array of size 5 in this program. int findMedian( int arr[], int n) { sort(arr, arr + n); // Sort the array return arr[n / 2]; // Return middle element } // Returns k'th smallest element in arr[l..r] in worst case // linear time. ASSUMPTION: ALL ELEMENTS IN ARR[] ARE // DISTINCT int kthSmallest( int arr[], int l, int r, int k) { // If k is smaller than number of elements in array if (k > 0 && k <= r - l + 1) { int n = r - l + 1; // Number of elements in arr[l..r] // Divide arr[] in groups of size 5, calculate // median of every group and store it in median[] // array. int i, median[(n + 4) / 5]; // There will be // floor((n+4)/5) groups; for (i = 0; i < n / 5; i++) median[i] = findMedian(arr + l + i * 5, 5); if (i * 5 < n) // For last group with less than 5 elements { median[i] = findMedian(arr + l + i * 5, n % 5); i++; } // Find median of all medians using recursive call. // If median[] has only one element, then no need // of recursive call int medOfMed = (i == 1) ? median[i - 1] : kthSmallest(median, 0, i - 1, i / 2); // Partition the array around a random element and // get position of pivot element in sorted array int pos = partition(arr, l, r, medOfMed); // If position is same as k if (pos - l == k - 1) return arr[pos]; if (pos - l > k - 1) // If position is more, recur for left return kthSmallest(arr, l, pos - 1, k); // Else recur for right subarray return kthSmallest(arr, pos + 1, r, k - pos + l - 1); } // If k is more than number of elements in array return INT_MAX; } void swap( int * a, int * b) { int temp = *a; *a = *b; *b = temp; } // It searches for x in arr[l..r], and partitions the array // around x. int partition( int arr[], int l, int r, int x) { // Search for x in arr[l..r] and move it to end int i; for (i = l; i < r; i++) if (arr[i] == x) break ; swap(&arr[i], &arr[r]); // Standard partition algorithm i = l; for ( int j = l; j <= r - 1; j++) { if (arr[j] <= x) { swap(&arr[i], &arr[j]); i++; } } swap(&arr[i], &arr[r]); return i; } /* 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 program to test above functions int main() { int arr[] = { 1000, 10, 7, 8, 9, 30, 900, 1, 5, 6, 20 }; int n = sizeof (arr) / sizeof (arr[0]); quickSort(arr, 0, n - 1); cout << "Sorted array is\n" ; printArray(arr, n); return 0; } |
Java
import java.util.Arrays; class QuickSort { // Function to find the median of five elements static int findMedian( int arr[], int i, int n) { Arrays.sort(arr, i, i + n); return arr[i + n / 2 ]; } // Function to partition the array around the median of // medians static int partition( int arr[], int l, int r, int x) { for ( int i = l; i < r; i++) if (arr[i] == x) swap(arr, i, r); int i = l; for ( int j = l; j <= r - 1 ; j++) { if (arr[j] <= x) { swap(arr, i, j); i++; } } swap(arr, i, r); return i; } // Function to swap two elements in the array static void swap( int arr[], int a, int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } // Function to find the kth smallest element using // median of medians static int kthSmallest( int arr[], int l, int r, int k) { if (k > 0 && k <= r - l + 1 ) { int n = r - l + 1 ; int i, median[] = new int [(n + 4 ) / 5 ]; for (i = 0 ; i < n / 5 ; i++) median[i] = findMedian(arr, l + i * 5 , 5 ); if (i * 5 < n) { median[i] = findMedian(arr, l + i * 5 , n % 5 ); i++; } int medOfMed = (i == 1 ) ? median[i - 1 ] : kthSmallest(median, 0 , i - 1 , i / 2 ); int pos = partition(arr, l, r, medOfMed); if (pos - l == k - 1 ) return arr[pos]; if (pos - l > k - 1 ) return kthSmallest(arr, l, pos - 1 , k); return kthSmallest(arr, pos + 1 , r, k - pos + l - 1 ); } return Integer.MAX_VALUE; } // Function to perform quicksort on the array static void quickSort( int arr[], int l, int h) { if (l < h) { int n = h - l + 1 ; int med = kthSmallest(arr, l, h, n / 2 ); int p = partition(arr, l, h, med); quickSort(arr, l, p - 1 ); quickSort(arr, p + 1 , h); } } // Function to print an array static void printArray( int arr[]) { for ( int i : arr) System.out.print(i + " " ); System.out.println(); } // Driver program to test above functions public static void main(String args[]) { int arr[] = { 1000 , 10 , 7 , 8 , 9 , 30 , 900 , 1 , 5 , 6 , 20 }; int n = arr.length; quickSort(arr, 0 , n - 1 ); System.out.println( "Sorted array is" ); printArray(arr); } } |
Python
def partition(arr, l, r, x): # Search for x in arr[l..r] and move it to end i = l for i in range (l, r): if arr[i] = = x: break arr[i], arr[r] = arr[r], arr[i] # Standard partition algorithm i = l for j in range (l, r): if arr[j] < = x: arr[i], arr[j] = arr[j], arr[i] i + = 1 arr[i], arr[r] = arr[r], arr[i] return i def findMedian(arr, n): arr.sort() # Sort the array return arr[n / / 2 ] # Return middle element def kthSmallest(arr, l, r, k): if 0 < k < = r - l + 1 : n = r - l + 1 # Number of elements in arr[l..r] # Divide arr[] in groups of size 5, calculate # median of every group and store it in median[] median = [ 0 ] * ((n + 4 ) / / 5 ) i = 0 for i in range (n / / 5 ): median[i] = findMedian(arr[l + i * 5 :l + i * 5 + 5 ], 5 ) if i * 5 < n: median[i] = findMedian(arr[l + i * 5 :l + i * 5 + n % 5 ], n % 5 ) i + = 1 # Find median of all medians using recursive call. # If median[] has only one element, then no need # of recursive call medOfMed = median[i - 1 ] if i = = 1 else kthSmallest(median, 0 , i - 1 , i / / 2 ) # Partition the array around a random element and # get the position of the pivot element in the sorted array pos = partition(arr, l, r, medOfMed) # If the position is the same as k if pos - l = = k - 1 : return arr[pos] if pos - l > k - 1 : # If the position is more, recur for the left return kthSmallest(arr, l, pos - 1 , k) # Else, recur for the right subarray return kthSmallest(arr, pos + 1 , r, k - pos + l - 1 ) # If k is more than the number of elements in the array return float ( 'inf' ) def quickSort(arr, l, h): if l < h: # Find the size of the current subarray n = h - l + 1 # Find the median of arr[] med = kthSmallest(arr, l, h, n / / 2 ) # Partition the array around the median p = partition(arr, l, h, med) # Recur for the left and right of the partition quickSort(arr, l, p - 1 ) quickSort(arr, p + 1 , h) def printArray(arr): for i in arr: print (i), # Driver program to test above functions arr = [ 1000 , 10 , 7 , 8 , 9 , 30 , 900 , 1 , 5 , 6 , 20 ] n = len (arr) quickSort(arr, 0 , n - 1 ) print ( "Sorted array is" ) printArray(arr) |
C#
using System; class Program { // Function to calculate sum of absolute differences static int CalculateSum( int [] arr, int n, int x) { int sum = 0; // Traverse to find sum of absolute differences for ( int i = 0; i < n; i++) { sum += Math.Abs(arr[i] - x); } return sum; } // A O(nLogn) time complexity function for sorting // arr[l..h] static void QuickSort( int [] arr, int l, int h) { if (l < h) { // Find size of current subarray int n = h - l + 1; // Find median of arr[]. int med = KthSmallest(arr, l, h, n / 2); // Partition the array around median int p = Partition(arr, l, h, med); // Recur for left and right of partition QuickSort(arr, l, p - 1); QuickSort(arr, p + 1, h); } } // A simple function to find median of arr[]. This is // called only for an array of size 5 in this program. static int FindMedian( int [] arr, int n) { Array.Sort(arr); // Sort the array return arr[n / 2]; // Return middle element } // Returns k'th smallest element in arr[l..r] in worst // case linear time. ASSUMPTION: ALL ELEMENTS IN ARR[] // ARE DISTINCT static int KthSmallest( int [] arr, int l, int r, int k) { // If k is smaller than the number of elements in // the array if (k > 0 && k <= r - l + 1) { int n = r - l + 1; // Number of elements in arr[l..r] // Divide arr[] into groups of size 5, calculate // the median of every group and store it in // median[] int i, count = 0; int [] median = new int [(n + 4) / 5]; // There will be // floor((n+4)/5) groups for (i = 0; i < n / 5; i++) { median[i] = FindMedian(arr, 5); count++; } if (i * 5 < n) // For the last group with less // than 5 elements { median[i] = FindMedian(arr, n % 5); count++; i++; } // Find the median of all medians using a // recursive call. If median[] has only one // element, then no need for a recursive call int medOfMed = (count == 1) ? median[0] : KthSmallest(median, 0, count - 1, count / 2); // Partition the array around a random element // and get the position of the pivot element in // the sorted array int pos = Partition(arr, l, r, medOfMed); // If the position is the same as k if (pos - l == k - 1) return arr[pos]; if (pos - l > k - 1) // If the position is more, recur // for the left subarray return KthSmallest(arr, l, pos - 1, k); // Else, recur for the right subarray return KthSmallest(arr, pos + 1, r, k - pos + l - 1); } // If k is more than the number of elements in the // array return int .MaxValue; } static void Swap( ref int a, ref int b) { int temp = a; a = b; b = temp; } // It searches for x in arr[l..r] and partitions the // array around x. static int Partition( int [] arr, int l, int r, int x) { // Search for x in arr[l..r] and move it to the end int i; for (i = l; i < r; i++) { if (arr[i] == x) break ; } Swap( ref arr[i], ref arr[r]); // Standard partition algorithm i = l; for ( int j = l; j <= r - 1; j++) { if (arr[j] <= x) { Swap( ref arr[i], ref arr[j]); i++; } } Swap( ref arr[i], ref arr[r]); return i; } // Function to print an array static void PrintArray( int [] arr, int size) { for ( int i = 0; i < size; i++) Console.Write(arr[i] + " " ); Console.WriteLine(); } // Driver program to test the above functions static void Main() { int [] arr = { 1000, 10, 7, 8, 9, 30, 900, 1, 5, 6, 20 }; int n = arr.Length; QuickSort(arr, 0, n - 1); Console.WriteLine( "Sorted array is" ); PrintArray(arr, n); } } |
Javascript
// JavaScript Program for the above approach /* A worst case O(nLogn) implementation of quicksort */ // It searches for x in arr[l..r], and partitions the array // around x. function partition(arr, l, r, k) { // Search for x in arr[l..r] and move it to end let i; for (i = l; i < r; i++) { if (arr[i] === k) { break ; } } swap(arr, i, r); // Standard partition algorithm i = l; for (let j = l; j <= r - 1; j++) { if (arr[j] <= k) { swap(arr, i, j); i++; } } swap(arr, i, r); return i; } // Returns k'th smallest element in arr[l..r] in worst case // linear time. ASSUMPTION: ALL ELEMENTS IN ARR[] ARE // DISTINCT function kthSmallest(arr, l, r, k) { // If k is smaller than number of elements in array if (k > 0 && k <= r - l + 1) { let n = r - l + 1; // Divide arr[] in groups of size 5, calculate // median of every group and store it in median[] // array. let i = 0; // There will be floor((n+4)/5) groups; let median = new Array(Math.floor((n + 4) / 5)); for (i = 0; i < Math.floor(n / 5); i++) { median[i] = findMedian(arr, l + i * 5, 5); } if (i * 5 < n) { median[i] = findMedian(arr, l + i * 5, n % 5); i++; } // Find median of all medians using recursive call. // If median[] has only one element, then no need // of recursive call let medOfMed = (i === 1) ? median[i - 1] : kthSmallest(median, 0, i - 1, Math.floor(i / 2)); // Partition the array around a random element and // get position of pivot element in sorted array let pos = partition(arr, l, r, medOfMed); // If position is same as k if (pos - l === k - 1) { return arr[pos]; } if (pos - l > k - 1) { return kthSmallest(arr, l, pos - 1, k); } // Else recur for right subarray return kthSmallest(arr, pos + 1, r, k - pos + l - 1); } // If k is more than number of elements in array return Infinity; } // A simple function to find median of arr[]. This is // called only for an array of size 5 in this program. function findMedian(arr, start, size) { let tempArr = new Array(size); for (let i = 0; i < size; i++) { tempArr[i] = arr[start + i]; } tempArr.sort((a, b) => a - b); let flr = Math.floor(size / 2); return tempArr[flr]; } function quickSort(arr, l, h) { if (l < h) { // Find size of current subarray let n = h - l + 1; // Find median of arr[]. let med = kthSmallest(arr, l, h, Math.floor(n / 2)); // Partition the array around median let p = partition(arr, l, h, med); // Recur for left and right of partition quickSort(arr, l, p - 1); quickSort(arr, p + 1, h); } } function swap(arr, i, j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Function to print an array function printArray(arr) { console.log(arr.join(' ')); } // Driver Code let arr = [1000, 10, 7, 8, 9, 30, 900, 1, 5, 6, 20]; quickSort(arr, 0, arr.length - 1); console.log(' Sorted array is:'); printArray(arr); // This code is contributed by codebraxnzt |
Sorted array is 1 5 6 7 8 9 10 20 30 900 1000
C++
// C++ code for the above approach #include <iostream> using namespace std; void quickSort( int array[], int left, int right); int partition( int array[], int left, int right); void swap( int array[], int i, int j); void quickSort( int array[], int left, int right) { if (left < right) { int pivotIndex = partition(array, left, right); quickSort(array, left, pivotIndex - 1); quickSort(array, pivotIndex + 1, right); } } // It searches for x in array[left..right], and partitions the array around x. int partition( int array[], int left, int right) { int pivot = array[right]; int i = left - 1; for ( int j = left; j < right; j++) { if (array[j] <= pivot) { i++; swap(array, i, j); } } swap(array, i + 1, right); return i + 1; } void swap( int array[], int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } // Driver code to check the above written functions int main() { int array[] = {5, 2, 9, 1, 5, 6}; int n = sizeof (array)/ sizeof (array[0]); quickSort(array, 0, n-1); for ( int i = 0; i < n; i++) { cout << array[i] << " " ; } return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { public static void quickSort( int [] array, int left, int right) { if (left < right) { int pivotIndex = partition(array, left, right); quickSort(array, left, pivotIndex - 1 ); quickSort(array, pivotIndex + 1 , right); } } // It searches for x in array[left..right], and partitions the array around x. private static int partition( int [] array, int left, int right) { int pivot = array[right]; int i = left - 1 ; for ( int j = left; j < right; j++) { if (array[j] <= pivot) { i++; swap(array, i, j); } } swap(array, i + 1 , right); return i + 1 ; } private static void swap( int [] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } // Driver code to check the above written functions public static void main(String[] args) { int [] array = { 5 , 2 , 9 , 1 , 5 , 6 }; quickSort(array, 0 , array.length - 1 ); for ( int i : array) { System.out.print(i + " " ); } } } |
Python3
def quickSort(array, left, right): # Recursive function to sort the array using quicksort algorithm if left < right: # Partition the array and get the pivot index pivotIndex = partition(array, left, right) # Sort elements to the left of pivot index quickSort(array, left, pivotIndex - 1 ) # Sort elements to the right of pivot index quickSort(array, pivotIndex + 1 , right) # It searches for x in array[left..right], and partitions the array around x. def partition(array, left, right): # Select the rightmost element as pivot pivot = array[right] # Initialize i as left-1 i = left - 1 # Traverse the array from left to right for j in range (left, right): if array[j] < = pivot: # Increment i and swap the current element with i i + = 1 array[i], array[j] = array[j], array[i] # Swap the pivot with the element at i+1 array[i + 1 ], array[right] = array[right], array[i + 1 ] # Return the pivot index return i + 1 # Driver code to check the above written functions if __name__ = = '__main__' : # Initialize an array to be sorted array = [ 5 , 2 , 9 , 1 , 5 , 6 ] # Sort the array using quicksort algorithm quickSort(array, 0 , len (array) - 1 ) # Print the sorted array for i in array: print (i, end = ' ' ) |
C#
// C# program for the above approach using System; class GFG { public static void QuickSort( int [] array, int left, int right) { if (left < right) { int pivotIndex = Partition(array, left, right); QuickSort(array, left, pivotIndex - 1); QuickSort(array, pivotIndex + 1, right); } } // It searches for x in array[left..right], and partitions the array around x. private static int Partition( int [] array, int left, int right) { int pivot = array[right]; int i = left - 1; for ( int j = left; j < right; j++) { if (array[j] <= pivot) { i++; Swap(array, i, j); } } Swap(array, i + 1, right); return i + 1; } private static void Swap( int [] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } // Driver code to check the above written functions static void Main( string [] args) { int [] array = { 5, 2, 9, 1, 5, 6 }; QuickSort(array, 0, array.Length - 1); foreach ( int i in array) { Console.Write(i + " " ); } } } // This code is contributed by rishabmalhdijo |
Javascript
// Javascript code for the above approach function quickSort(array, left, right) { // Recursive function to sort the array using quicksort algorithm if (left < right) { // Partition the array and get the pivot index let pivotIndex = partition(array, left, right); // Sort elements to the left of pivot index quickSort(array, left, pivotIndex - 1); // Sort elements to the right of pivot index quickSort(array, pivotIndex + 1, right); } } // It searches for x in array[left..right], and partitions the array around x. function partition(array, left, right) { // Select the rightmost element as pivot let pivot = array[right]; // Initialize i as left-1 let i = left - 1; // Traverse the array from left to right for (let j = left; j < right; j++) { if (array[j] <= pivot) { // Increment i and swap the current element with i i++; [array[i], array[j]] = [array[j], array[i]]; } } // Swap the pivot with the element at i+1 [array[i + 1], array[right]] = [array[right], array[i + 1]]; // Return the pivot index return i + 1; } // Driver code to check the above written functions let array = [5, 2, 9, 1, 5, 6]; // Sort the array using quicksort algorithm quickSort(array, 0, array.length - 1); // Print the sorted array console.log(array.join( ' ' )); // This code is contributed by adityashatmfh |
Output
1 2 5 5 6 9
Auxiliary Space: O(n*logn) where n is size of array.
How is QuickSort implemented in practice – is above approach used?
Although worst case time complexity of the above approach is O(nLogn), it is never used in practical implementations. The hidden constants in this approach are high compared to normal Quicksort. Following are some techniques used in practical implementations of QuickSort.
1) Randomly picking up to make worst case less likely to occur (Randomized QuickSort)
2) Calling insertion sort for small sized arrays to reduce recursive calls.
3) QuickSort is tail recursive, so tail call optimizations is done.
So the approach discussed above is more of a theoretical approach with O(nLogn) worst case time complexity.
This article is compiled by Shivam.