Quick Sort
Quick Sort is a highly efficient, comparison-based sorting algorithm that uses the divide-and-conquer approach. It works by selecting a "pivot" element, partitioning the array into two subarrays—elements smaller than the pivot and elements larger than or equal to it—and then recursively sorting these subarrays.
Let us understand quick steps of this algorithm
Step 1: Choose a Pivot
The pivot is a reference element used to divide the array into two parts. Choosing the right pivot impacts the efficiency of the algorithm. Common methods for selecting the pivot include:
- Last element (simple but prone to worst-case performance on sorted/reverse-sorted arrays).
- First element (similar issues as the last element).
- Random element (reduces the likelihood of worst-case performance).
- Median-of-three (median of the first, middle, and last elements for better partitioning).
Step 2: Partition the Array
Partitioning involves rearranging the array so that:
- Elements smaller than the pivot are on its left.
- Elements greater than or equal to the pivot are on its right.
The pivot is then placed in its correct sorted position. This ensures that the pivot is fixed, and the rest of the elements are divided into smaller subproblems.
Partitioning Algorithm (Lomuto's Scheme):
- Initialize pointers:
- i starts at low - 1 (before the start of the array).
- j traverses the array from low to high - 1.
- Traverse the array:
- For each element arr[j]:
- If arr[j] is less than the pivot, increment i and swap arr[i] with arr[j].
- Place the pivot:
- After the traversal, swap the pivot element (arr[high]) with arr[i + 1] to position it correctly.
- Return the pivot index:
- This index separates the left and right subarrays.
Step 3: Recursively Apply Quick Sort
Once partitioning is complete:
- Apply Quick Sort to the left subarray (elements smaller than the pivot).
- Apply Quick Sort to the right subarray (elements larger than or equal to the pivot).
Step 4: Base Case
The recursion stops when:
- The subarray has only one element or no elements (already sorted).
- This ensures that the algorithm eventually terminates.
Let us understand a step-by-step working of Quick Sort with an example :
Suppose we have the following array of integers [10, 7, 8, 9, 1, 5] that we want to sort in ascending order:
Step By Step Working with an Example
Initial Array: [10, 7, 8, 9, 1, 5]
Step 1: Choose Pivot
We choose the last element as the pivot.
- Pivot = 5.
Step 2: Partitioning
We partition the array such that:
- All elements smaller than 5 go to its left.
- All elements larger than or equal to 5 go to its right.
Initial State of Variables
- i = -1 (points to the position where the last smaller-than-pivot element will go).
- j = 0 (used to traverse the array).
Traversing the Array
We traverse each element and compare it with the pivot (5):
- Compare arr[0] = 10 with pivot 5:
- 10 > 5, so no action.
- i = -1, the array remains unchanged.
- Compare arr[1] = 7 with pivot 5:
- 7 > 5, so no action.
- i = -1, the array remains unchanged.
- Compare arr[2] = 8 with pivot 5:
- 8 > 5, so no action.
- i = -1, the array remains unchanged.
- Compare arr[3] = 9 with pivot 5:
- 9 > 5, so no action.
- i = -1, the array remains unchanged.
- Compare arr[4] = 1 with pivot 5:
- 1 < 5, so:
- Increment i to 0.
- Swap arr[i] and arr[j]: Swap 10 with 1.
- Array becomes [1, 7, 8, 9, 10, 5]
Place the Pivot
After the traversal:
- Swap the pivot (5) with the element at i + 1 (arr[1]): Swap 5 and 7.
- Array becomes [1, 5, 8, 9, 10, 7].
Result of Partition
- Pivot 5 is at the index 1.
- Left subarray: [1] (elements smaller than 5).
- Right subarray: [8,9,10,7] (elements larger than or equal to 5).
Step 3: Recursively Sort the Subarrays
Left Subarray: 1
- It contains only one element, so it’s already sorted.
Right Subarray: [8,9,10,7]
- Choose Pivot: Pivot = 7.
- Partition: Traverse and Compare:
- Initial i = -1, j = 0.
- Compare 8 > 7: No action.
- Compare 9 > 7: No action.
- Compare 10 > 7: No action.
- Place pivot: Swap 7 and 8.
Array becomes [7,9,10,8].
- Result of Partition:
- Pivot 7 is at index 0.
- Left subarray: [] (empty).
- Right subarray: [9,10,8].
Sort Right Subarray: [9,10,8]
- Choose Pivot: Pivot = 8.
- Partition: Traverse and Compare:
- Initial i = -1, j = 0.
- Compare 9 > 8: No action.
- Compare 10 > 8: No action.
- Place pivot: Swap 8 and 9.
Array becomes [8,10,9].
- Result of Partition:
- Pivot 8 is at the index 0.
- Left subarray: [] (empty).
- Right subarray: [10, 9].
Sort Right Subarray: [10, 9]
- Choose Pivot: Pivot = 9.
- Partition: Traverse and Compare:
- Initial i = -1, j = 0.
- Compare 10 > 9: No action.
- Place pivot: Swap 9 and 10.
Array becomes [9, 10].
- Result of Partition:
- Pivot 9 is at the index 0.
- Left subarray: [] (empty).
- Right subarray: [10].
Final Sorted Array
Combining all the sorted subarrays step-by-step: [1, 5, 7, 8, 9, 10].
Since we have learned about the step-by-step process with an example let us understand each one of the two functions in detail.
1. Quick Sort Function
The Quick Sort function is the recursive part of the algorithm that divides the array and sorts the partitions.
Detailed Explanation of the Quick Sort Function
- Base Case:
- If the subarray has one or no elements (start >= end), it is already sorted, so the function returns and does not do anything.
- Recursive Case:
- If the subarray has more than one element, the function proceeds as follows:
- Partition the array: The array is divided around a pivot element, and the partition() function is called to rearrange the elements.
- Recursively Sort the Left Partition: Once the array is partitioned, Quick Sort is called recursively on the left partition (i.e., elements less than the pivot).
- Recursively Sort the Right Partition: Similarly, Quick Sort is called recursively on the right partition (i.e., elements greater than or equal to the pivot).
- If the subarray has more than one element, the function proceeds as follows:
Pseudocode for Quick Sort
FUNCTION quickSort(arr, start, end):
IF start >= end: // Base case: Subarray with 1 or 0 elements is already sorted
RETURN
// Partition the array and find the pivot index
pivotIndex = partition(arr, start, end)
// Recursively sort the left partition
quickSort(arr, start, pivotIndex - 1)
// Recursively sort the right partition
quickSort(arr, pivotIndex + 1, end)
Explanation of the Pseudocode:
- quickSort(arr, start, end):
- This function takes three parameters: the array arr, and two indices start and end that define the range of the current subarray to sort.
- The function first checks if the subarray has one or no elements (base case). If so, it returns because the subarray is already sorted.
- Otherwise, the array is partitioned by calling the partition() function. The function then recursively calls quickSort() for the left and right partitions.
2. Partition Function
The Partition function is responsible for rearranging the elements in the array around a pivot element, ensuring that all elements smaller than the pivot are placed to its left, and all elements greater than the pivot are placed to its right.
Detailed Explanation of the Partition Function
- Choose a Pivot:
- The pivot is typically chosen as the last element of the array or subarray (though other pivot selection methods are possible).
- Rearrange the Array:
- We maintain two pointers:
- i: Tracks the position of the last element smaller than the pivot.
- j: Traverses the array to compare each element with the pivot.
- For each element arr[j]:
- If arr[j] is smaller than the pivot, we increment i and swap the with arr[j] to ensure that smaller elements are moved to the left side.
- We maintain two pointers:
- Place the Pivot in the Correct Position:
- After traversing the array, the pivot element is placed in its correct sorted position by swapping it with arr[i + 1].
- Return Pivot Index:
- The pivot is now placed in its correct position, and its index is returned. This index divides the array into two parts that will be recursively sorted.
Pseudocode for Partition
FUNCTION partition(arr, start, end):
pivot = arr[end] // Choose the last element as the pivot
i = start - 1 // Pointer for smaller-than-pivot region
FOR j FROM start TO end - 1: // Traverse the array
IF arr[j] < pivot: // If current element is smaller than pivot
i = i + 1 // Increment i
SWAP arr[i] WITH arr[j] // Move smaller element to the left partition
// Place the pivot in the correct position
SWAP arr[i + 1] WITH arr[end] // Place pivot in its correct position
RETURN i + 1 // Return the pivot index
Explanation of the Pseudocode:
- partition(arr, start, end):
- This function takes the array arr, and the indices start and end, representing the range of the subarray being partitioned.
- The pivot is selected as the last element (arr[end]).
- i is initialized as start - 1, and j iterates over the elements from start to end - 1.
- If an element arr[j] is smaller than the pivot, i is incremented and arr[i] is swapped with arr[j] to move the smaller element to the left.
- After the loop, the pivot is swapped with arr[i + 1] to place it in the correct sorted position.
- Finally, the function returns i + 1, which is the new index of the pivot.
Code Implementation
C++
// Function to partition the array using the middle element as the pivot
int partition(vector<int>& arr, int start, int end) {
int pivot = arr[end]; // Use the middle element as pivot
int i = start - 1; // Pointer for smaller element
// Rearrange elements around the pivot
for (int j = start; j < end; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]);
}
}
// Place pivot in its correct position
swap(arr[i + 1], arr[end]);
return i + 1; // Return pivot index
}
// Recursive Quick Sort function
void quickSort(vector<int>& arr, int start, int end) {
if (start < end) {
int pivotIndex = partition(arr, start, end); // Partition the array
quickSort(arr, start, pivotIndex - 1); // Sort the left part
quickSort(arr, pivotIndex + 1, end); // Sort the right part
}
}Java
public class QuickSort {
// Function to partition the array using the middle element as the pivot
public static int partition(int[] arr, int start, int end) {
// Use the end element as pivot
int pivot = arr[end];
// Pointer for smaller element
int i = start - 1;
// Move pivot to the end
swap(arr, mid, end);
// Rearrange elements around the pivot
for (int j = start; j < end; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
// Place pivot in its correct position
swap(arr, i + 1, end);
// Return pivot index
return i + 1;
}
// Swap utility function
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Recursive Quick Sort function
public static void quickSort(int[] arr, int start, int end) {
if (start < end) {
// Partition the array
int pivotIndex = partition(arr, start, end);
// Sort the left part
quickSort(arr, start, pivotIndex - 1);
// Sort the right part
quickSort(arr, pivotIndex + 1, end);
}
}
}Python
Python# Function to partition the array using the end element as pivot
def partition(arr, start, end):
# Use the middle element as pivot
pivot = arr[mid]
# Pointer for smaller elements
i = start - 1
# Rearrange elements around the pivot
for j in range(start, end):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
# Place pivot in its correct position
arr[i + 1], arr[end] = arr[end], arr[i + 1]
# Return pivot index
return i + 1
# Recursive Quick Sort function
def quick_sort(arr, start, end):
if start < end:
# Partition the array
pivot_index = partition(arr, start, end)
# Sort the left part
quick_sort(arr, start, pivot_index - 1)
# Sort the right part
quick_sort(arr, pivot_index + 1, end) Javascript
// Function to partition the array using the end element as pivot
function partition(arr, start, end) {
// Use the end element as pivot
const pivot = arr[end];
// Pointer for smaller elements
let i = start - 1;
// Rearrange elements around the pivot
for (let j = start; j < end; j++) {
if (arr[j] <= pivot) {
i++;
// Swap elements
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
// Place pivot in its correct position
[arr[i + 1], arr[end]] = [arr[end], arr[i + 1]];
// Return pivot index
return i + 1;
}
// Recursive Quick Sort function
function quickSort(arr, start, end) {
if (start < end) {
// Partition the array
const pivotIndex = partition(arr, start, end);
// Sort the left part
quickSort(arr, start, pivotIndex - 1);
// Sort the right part
quickSort(arr, pivotIndex + 1, end);
}
}Time Complexity
We will analyze Quick Sort's time complexity in three different cases:
1. Best Case Time Complexity: O(nlogn)
In the best case, Quick Sort performs well when the pivot divides the array into almost equal halves at each step.
- Pivot Choice: The pivot divides the array into two parts that are roughly of equal size, leading to the most balanced recursion tree.
- Partitioning: In each partition step, we compare every element of the array with the pivot. This requires O(n) time to partition the array at each level.
- Recursion Tree Depth: The recursion depth is proportional to logn, as the array is divided into halves in each step.
Thus, the time complexity is:
- Partition step: O(n) for each recursion.
- Recursion depth: O(logn), as the array is halved in each step.
Therefore, the overall time complexity for the best case is: O(nlogn)
- Average Case Time Complexity: O(nlogn)
The average case of Quick Sort occurs when the pivot divides the array into reasonably balanced partitions, but not necessarily exactly in half. This happens when the pivot is not too small or too large, but somewhere in the middle.
- Pivot Choice: In practice, the pivot often divides the array into reasonably balanced subarrays, even though it may not be exactly in the middle.
- Partitioning: Each partition still requires O(n) time to compare and arrange elements around the pivot.
- Recursion Tree Depth: The recursion depth is still roughly O(logn) in the average case, though it may not be as perfectly balanced as in the best case.
Thus, the overall time complexity for the average case is: O(nlogn)
This is because, on average, the pivot divides the array into reasonably balanced parts, and Quick Sort recursively sorts each part.
3. Worst Case Time Complexity: O(n²)
The worst-case time complexity of Quick Sort occurs when the pivot always divides the array in the most unbalanced way possible, i.e., the pivot is the smallest or largest element in the array. This can happen if:
- The array is already sorted or reverse sorted.
- The pivot is consistently chosen as the first or last element (e.g., if the pivot is selected using a deterministic method like always picking the first or last element in the array).
- Pivot Choice: If the pivot is the smallest or largest element, one of the subarrays is empty, and the other contains almost all the elements of the array.
- Partitioning: For each partitioning step, the partitioning requires O(n) time.
- Recursion Tree Depth: In the worst case, the recursion depth becomes O(n), as the array is divided into subarrays of size n−1 and 1 at each step.
Thus, the overall time complexity for the worst case is: O(n²)
This occurs because:
- In each partition step, we are processing O(n) elements.
- The recursion depth is O(n), resulting in a total time complexity of O(n×n)=O(n²).
Optimizing the Worst Case:
To avoid the worst-case performance, various optimizations can be made:
- Randomized Pivot Selection: Randomly choosing the pivot helps ensure that the pivot is likely to divide the array into reasonably balanced partitions, even if the array is already sorted or nearly sorted. This brings the worst-case complexity closer to O(nlogn) on average.
- Median-of-Three: Choosing the pivot as the median of the first, middle, and last elements can reduce the likelihood of selecting a poor pivot in the case of sorted or nearly sorted data.
Space Complexity
The space complexity of an algorithm refers to the amount of memory required to run the algorithm. In the case of Quick Sort, the space complexity is influenced primarily by the recursion stack and the input size. Let’s break it down in detail:
1. In-Place Sorting:
Quick Sort is an in-place sorting algorithm, meaning it doesn’t require extra space to store a separate array for the sorted data. Instead, it modifies the original array directly during the sorting process. Therefore, the space complexity from the perspective of the array itself is O(1), as no additional memory is used to store a copy of the array.
However, the space complexity primarily arises from the recursion stack used during the sorting process. Let's understand this better.
2. Recursion Stack:
Quick Sort works by recursively dividing the array into smaller subarrays. At each step, Quick Sort calls itself on the left and right subarrays, creating new recursive function calls.
Each recursive call adds a new stack frame to the recursion stack, which contains:
- Local variables (e.g., start, end, pivot index).
- The state of the algorithm (e.g., the current subarray being processed).
The depth of the recursion stack depends on how balanced the partitions are. Let’s discuss the space complexity based on different scenarios:
3. Best and Average Case Recursion Depth:
In the best-case and average-case scenarios, where the pivot divides the array into roughly equal-sized subarrays, the recursion depth is O(logn). Here’s why:
- At each level of recursion, the array is divided into two roughly equal subarrays.
- This results in a recursion tree with a height of O(logn), because the array size is halved at each level.
Thus, in the best and average cases, the space required for the recursion stack is O(logn), since the maximum depth of recursive calls is O(logn).
4. Worst Case Recursion Depth:
In the worst-case scenario, Quick Sort has unbalanced partitions, and the recursion depth can become as deep as O(n). This happens, for example, when the pivot is always the smallest or largest element in the array (like in the case of a sorted or reverse-sorted array), causing one subarray to have almost all the elements and the other to be empty.
- In this case, Quick Sort recurses on subarrays of size n−1, n−2, ..., down to 1. This creates a recursion depth of n.
Thus, in the worst case, the space complexity of the recursion stack is O(n), because the recursion depth becomes linear.
5. Auxiliary Space:
Quick Sort is an in-place sorting algorithm, meaning no extra array or list is used to store intermediate results. All the sorting happens directly on the input array. The only extra space needed is for the recursion stack, which is required to store the state of recursive calls.
Since Quick Sort does not use any other data structures (like auxiliary arrays) apart from the recursion stack, its auxiliary space complexity is the same as the recursion stack space.
- Auxiliary Space: O(logn) on average and O(n) in the worst case.
Stability of Algorithm
By default, it is not a stable algorithm.
How Quick Sort Works (and why it’s not stable)
In Quick Sort, elements are divided into two groups based on a pivot element. The key operation that causes instability is the partitioning step, where the array is rearranged such that:
- Elements less than or equal to the pivot come before it.
- Elements greater than or equal to the pivot come after it.
During this partitioning step, equal elements (i.e., elements that have the same value as the pivot) might end up being swapped around, which can cause a change in their original relative order.
Can we make Quick Sort Stable?
To make Quick Sort stable, you would need to modify the partitioning step to ensure that equal elements are not swapped, or use a more stable partitioning strategy. A common method to do this involves a slight modification to how the elements are grouped during partitioning. Instead of just placing elements less than the pivot in one subarray and elements greater than the pivot in another, we could ensure that elements equal to the pivot are placed in the middle subarray or at a consistent position.
However, making Quick Sort stable comes at the cost of slightly increasing its time complexity, which is typically avoided unless stability is a key requirement for the problem at hand.
Application of Quick Sort
- Database Management Systems (DBMS):
- Used for sorting records, query processing, and indexing in databases.
- Handles large datasets efficiently in an in-place manner.
- Multi-Level Sorting:
- Quick Sort is used in applications that require sorting multiple attributes or levels of data (e.g., sorting by name, then by age).
- File Systems:
- Used in sorting files or directories by size, date, or other attributes for organizing and searching file systems.
- Distributed Systems:
- In parallel computing, Quick Sort is adapted for distributed sorting tasks, where each node sorts a portion of data, and the results are combined.
- Computer Graphics:
- Used for sorting data such as pixel values, colors, and geometric objects in graphics algorithms.