Introduction
Quick Sort is a highly efficient sorting algorithm developed by Tony Hoare in 1959. It employs a divide-and-conquer strategy to sort elements in an array or list. Quick Sort is renowned for its average-case time complexity of O(n log n), making it suitable for large datasets. Its in-place sorting capability (requiring only a small, constant amount of additional memory space) further enhances its practicality.
However, in the worst case, Quick Sort’s performance can degrade to O(n²), typically when the pivot selection is poor (e.g., when the array is already sorted). Various optimizations, such as choosing a better pivot, can mitigate this risk.
In this guide, we’ll explore how to implement Quick Sort in C++, understand its inner workings through pseudocode, and assess its performance through testing.
Understanding the Quick Sort Algorithm
Quick Sort operates based on the following steps:
- Choose a Pivot: Select an element from the array as the pivot. The choice of pivot can affect the algorithm’s performance.
- Partitioning: Rearrange the array so that all elements less than the pivot are on its left, and all elements greater than the pivot are on its right.
- Recursion: Recursively apply the above steps to the sub-arrays on the left and right of the pivot.
Key Concepts
- In-Place Sorting: Quick Sort sorts the array without additional storage, making it memory-efficient.
- Recursion: Quick Sort relies on recursive calls to sort sub-arrays, which simplifies the implementation but can lead to stack overflow for very large arrays.
- Pivot Selection: The choice of pivot is crucial. Common strategies include selecting the first element, the last element, the middle element, or the median of the first, middle, and last elements (median-of-three).
Pseudocode for Quick Sort
Understanding the pseudocode can provide clarity before diving into code implementation. Here’s a straightforward representation of the Quick Sort algorithm:
function quickSort(array, low, high)
if low < high then
pivotIndex = partition(array, low, high)
quickSort(array, low, pivotIndex - 1)
quickSort(array, pivotIndex + 1, high)
function partition(array, low, high)
pivot = array[high]
i = low - 1
for j from low to high - 1 do
if array[j] < pivot then
i = i + 1
swap array[i] with array[j]
swap array[i + 1] with array[high]
return i + 1
Explanation:
- quickSort Function: This function takes the array and the
lowandhighindices, which define the portion of the array that needs to be sorted. - Base Case: If
lowis not less thanhigh, it means the section of the array is either empty or has only one element, so it’s already sorted. - Partitioning: The partition function reorganizes the array by placing elements smaller than the pivot to the left and larger elements to the right, and then returns the final position of the pivot.
- Recursive Calls: After partitioning, Quick Sort is called recursively on the sub-arrays to the left and right of the pivot until the entire array is sorted.
Diagram Explanation of Quick Sort
To better visualize how Quick Sort works, let’s walk through the sorting process step by step with the array [12, 4, 5, 6, 7, 3, 1, 15].
Step 1:
Original array: [12, 4, 5, 6, 7, 3, 1, 15]
Pivot: 6 (chosen using the median-of-three strategy)
- Partitioning:
- Left:
[4, 5, 3, 1] - Pivot:
[6] - Right:
[12, 7, 15]
- Left:
Step 2:
Recursively sort the left sub-array: [4, 5, 3, 1]
Pivot: 3
Partitioning:
- Left:
[1] - Pivot:
[3] - Right:
[4, 5]
Recursively sort the right sub-array [4, 5]:
- Pivot:
5 - Partitioning:
- Left:
[4] - Pivot:
[5]
- Left:
Step 3:
Recursively sort the right sub-array: [12, 7, 15]
Pivot: 12
Partitioning:
- Left:
[7] - Pivot:
[12] - Right:
[15]
Step 4:
Merge everything:
- Sorted Left:
[1, 3, 4, 5] - Pivot:
[6] - Sorted Right:
[7, 12, 15]
Final sorted array: [1, 3, 4, 5, 6, 7, 12, 15]
Implementing Quick Sort in C++
Let’s translate the pseudocode into a practical C++ implementation. We’ll start with a basic version and then discuss an optimized variant.
Basic Quick Sort Implementation
Here’s a straightforward C++ implementation of Quick Sort based on the above pseudocode:
#include <iostream>
#include <vector>
// Function to swap two elements
void swapElements(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// Partition function
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[high]; // Choosing the last element as pivot
int i = low - 1; // Index of smaller element
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than pivot
if (arr[j] < pivot) {
i++; // Increment index of smaller element
swapElements(arr[i], arr[j]);
}
}
swapElements(arr[i + 1], arr[high]);
return (i + 1);
}
// Quick Sort function
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
// pi is partitioning index
int pi = partition(arr, low, high);
// Separately sort elements before and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print the array
void printArray(const std::vector<int>& arr) {
for (int num : arr)
std::cout << num << " ";
std::cout << "\n";
}
// Main function to demonstrate Quick Sort
int main() {
std::vector<int> arr = {12, 4, 5, 6, 7, 3, 1, 15};
int n = arr.size();
std::cout << "Original array: ";
printArray(arr);
quickSort(arr, 0, n - 1);
std::cout << "Sorted array: ";
printArray(arr);
return 0;
}
Output:
Original array: 12 4 5 6 7 3 1 15 Sorted array: 1 3 4 5 6 7 12 15
Optimized Quick Sort with Median-of-Three Partitioning
To enhance Quick Sort’s performance, especially in avoiding the worst-case scenario, we can implement the median-of-three method for pivot selection. This strategy selects the median of the first, middle, and last elements as the pivot, providing a better partition in many cases.
#include <iostream>
#include <vector>
// Function to swap two elements
void swapElements(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// Function to find the median of three elements
int medianOfThree(std::vector<int>& arr, int low, int high) {
int mid = low + (high - low) / 2;
if (arr[low] > arr[mid])
swapElements(arr[low], arr[mid]);
if (arr[low] > arr[high])
swapElements(arr[low], arr[high]);
if (arr[mid] > arr[high])
swapElements(arr[mid], arr[high]);
// After ordering, arr[mid] is the median
swapElements(arr[mid], arr[high]); // Move median to high for partitioning
return arr[high];
}
// Partition function with median-of-three
int partition(std::vector<int>& arr, int low, int high) {
int pivot = medianOfThree(arr, low, high);
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swapElements(arr[i], arr[j]);
}
}
swapElements(arr[i + 1], arr[high]);
return (i + 1);
}
// Quick Sort function
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print the array
void printArray(const std::vector<int>& arr) {
for (int num : arr)
std::cout << num << " ";
std::cout << "\n";
}
// Main function to demonstrate optimized Quick Sort
int main() {
std::vector<int> arr = {12, 4, 5, 6, 7, 3, 1, 15};
int n = arr.size();
std::cout << "Original array: ";
printArray(arr);
quickSort(arr, 0, n - 1);
std::cout << "Sorted array: ";
printArray(arr);
return 0;
}
Explanation:
- medianOfThree Function: Determines the median of the first, middle, and last elements and places it at the end of the array to be used as the pivot.
- partition Function: Uses the median-of-three pivot for partitioning, enhancing the likelihood of balanced partitions.
Output:
Original array: 10 7 8 9 1 5 3 4 2 6 Sorted array: 1 2 3 4 5 6 7 8 9 10
Performance Testing Quick Sort
To evaluate Quick Sort’s efficiency, we’ll perform performance testing by measuring its execution time on arrays of varying sizes and configurations. This will help us understand its behavior in different scenarios.
Setting Up the Test Environment
Before implementing the performance test, consider the following:
- Test Cases: Assess Quick Sort on different types of arrays:
- Randomly ordered arrays
- Already sorted arrays (best and worst case scenarios)
- Reverse-sorted arrays
- Arrays with duplicate elements
- Array Sizes: Test on small, medium, and large arrays to observe scalability.
- Measurement Tools: Use C++’s
<chrono>library for high-resolution timing.
Implementing the Performance Test in C++
Below is a C++ program that performs Quick Sort on various test cases and measures the execution time.
#include <iostream>
#include <vector>
#include <algorithm> // For std::shuffle
#include <chrono>
#include <random>
// Function to swap two elements
void swapElements(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// Function to find the median of three elements
int medianOfThree(std::vector<int>& arr, int low, int high) {
int mid = low + (high - low) / 2;
if (arr[low] > arr[mid])
swapElements(arr[low], arr[mid]);
if (arr[low] > arr[high])
swapElements(arr[low], arr[high]);
if (arr[mid] > arr[high])
swapElements(arr[mid], arr[high]);
swapElements(arr[mid], arr[high]); // Move median to high for partitioning
return arr[high];
}
// Partition function with median-of-three
int partition(std::vector<int>& arr, int low, int high) {
int pivot = medianOfThree(arr, low, high);
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swapElements(arr[i], arr[j]);
}
}
swapElements(arr[i + 1], arr[high]);
return (i + 1);
}
// Quick Sort function
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to generate a vector with specified size and type
std::vector<int> generateArray(int size, const std::string& type) {
std::vector<int> arr(size);
for (int i = 0; i < size; i++)
arr[i] = i + 1;
if (type == "random") {
// Shuffle the array
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(arr.begin(), arr.end(), g);
} else if (type == "reverse") {
// Reverse the array
std::reverse(arr.begin(), arr.end());
}
// For "sorted", do nothing
return arr;
}
// Function to perform and time Quick Sort
double testQuickSort(std::vector<int> arr) {
auto start = std::chrono::high_resolution_clock::now();
quickSort(arr, 0, arr.size() - 1);
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double, std::micro> duration = end - start;
return duration.count(); // Return time in microseconds
}
// Main function to perform performance testing
int main() {
std::vector<std::string> types = {"random", "sorted", "reverse"};
std::vector<int> sizes = {1000, 10000, 100000, 1000000};
std::cout << "Quick Sort Performance Testing:\n";
std::cout << "Array Size\tType\t\tTime (μs)\n";
for (int size : sizes) {
for (const auto& type : types) {
std::vector<int> arr = generateArray(size, type);
double time = testQuickSort(arr);
std::cout << size << "\t\t" << type << "\t\t" << time << "\n";
}
}
return 0;
}
Explanation:
- generateArray Function: Creates arrays based on the specified type:
"random": Shuffles the array to randomize element order."sorted": Leaves the array in ascending order."reverse": Reverses the array to descending order.
- testQuickSort Function: Measures the time taken by Quick Sort to sort the array using
<chrono>for high-resolution timing. - Main Function: Iterates over different array sizes and types, performing Quick Sort on each and recording the execution time.
Analysis of the Results
Quick Sort Performance Testing: Array Size Type Time (μs) 1000 random 125.929 1000 sorted 62.745 1000 reverse 109.02 10000 random 1615.2 10000 sorted 939.049 10000 reverse 1486.65 100000 random 20401 100000 sorted 10169.6 100000 reverse 21991.3 1000000 random 293116 1000000 sorted 135297 1000000 reverse 272778
From the results of the performance testing using the median of three quick sort in C++, we can deduce several points:
- Sorted Arrays Perform Best: For each array size, the performance of quick sort is significantly better when the array is already sorted. This is expected since the median-of-three pivot selection minimizes worst-case behavior for sorted inputs, ensuring fewer swaps and comparisons.
- Random Arrays Perform Well: The performance on random arrays is efficient and consistently better than reverse-sorted arrays. Median-of-three improves performance on random data by selecting a good pivot that avoids worst-case partitions.
- Reverse-Sorted Arrays Are Slower: Quick sort shows the worst performance on reverse-sorted data. Although median-of-three helps mitigate the extreme worst case of quick sort (which happens when the first or last element is selected as a pivot), reverse-sorted data still takes more time due to the suboptimal partitioning.
- Growth with Array Size: As the array size increases, the time taken by quick sort grows, but the algorithm scales well. The time complexity is roughly O(nlogn)O(n \log n)O(nlogn), and the results confirm that the algorithm handles larger arrays efficiently, especially when the data is already sorted or random.
Quick Sort vs Merge Sort
Overall Comparison
- Time Complexity: Merge Sort has a consistent O(n log n) time complexity in all cases (best, average, and worst).
- Comparison: Quick Sort is often faster in practice than Merge Sort due to its in-place nature (no need for additional memory for merging). However, in the worst case, Quick Sort can degrade to O(n²), while Merge Sort remains consistently O(n log n).
- Memory Usage: Merge Sort requires additional memory to store temporary sub-arrays while Quick Sort is in place (except for stack space used in recursion).
Performance
We’ll modify the previous performance testing code by adding the Merge Sort implementation. This will allow us to run Quick and Merge Sort on the same datasets and compare their performance.
#include <iostream>
#include <vector>
#include <algorithm> // For std::shuffle
#include <chrono>
#include <random>
// Function to swap two elements
void swapElements(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// Function to find the median of three elements
int medianOfThree(std::vector<int>& arr, int low, int high) {
int mid = low + (high - low) / 2;
if (arr[low] > arr[mid])
swapElements(arr[low], arr[mid]);
if (arr[low] > arr[high])
swapElements(arr[low], arr[high]);
if (arr[mid] > arr[high])
swapElements(arr[mid], arr[high]);
swapElements(arr[mid], arr[high]); // Move median to high for partitioning
return arr[high];
}
// Partition function with median-of-three
int partition(std::vector<int>& arr, int low, int high) {
int pivot = medianOfThree(arr, low, high);
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swapElements(arr[i], arr[j]);
}
}
swapElements(arr[i + 1], arr[high]);
return (i + 1);
}
// Quick Sort function
void quickSort(std::vector<int>& arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to merge two halves (Merge Sort)
void merge(std::vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
std::vector<int> L(n1), R(n2);
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int i = 0; i < n2; i++)
R[i] = arr[mid + 1 + i];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// Merge Sort function
void mergeSort(std::vector<int>& arr, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
// Function to generate a vector with specified size and type
std::vector<int> generateArray(int size, const std::string& type) {
std::vector<int> arr(size);
for (int i = 0; i < size; i++)
arr[i] = i + 1;
if (type == "random") {
// Shuffle the array
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(arr.begin(), arr.end(), g);
} else if (type == "reverse") {
// Reverse the array
std::reverse(arr.begin(), arr.end());
}
// For "sorted", do nothing
return arr;
}
// Function to perform and time Quick Sort
double testQuickSort(std::vector<int> arr) {
auto start = std::chrono::high_resolution_clock::now();
quickSort(arr, 0, arr.size() - 1);
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double, std::micro> duration = end - start;
return duration.count(); // Return time in microseconds
}
// Function to perform and time Merge Sort
double testMergeSort(std::vector<int> arr) {
auto start = std::chrono::high_resolution_clock::now();
mergeSort(arr, 0, arr.size() - 1);
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double, std::micro> duration = end - start;
return duration.count(); // Return time in microseconds
}
// Main function to perform performance testing
int main() {
std::vector<std::string> types = {"random", "sorted", "reverse"};
std::vector<int> sizes = {1000, 10000, 100000};
std::cout << "Performance Testing - Quick Sort vs Merge Sort:\n";
std::cout << "Array Size\tType\t\tQuick Sort (μs)\tMerge Sort (μs)\n";
for (int size : sizes) {
for (const auto& type : types) {
std::vector<int> arr = generateArray(size, type);
double quickSortTime = testQuickSort(arr);
double mergeSortTime = testMergeSort(arr);
std::cout << size << "\t\t" << type << "\t\t" << quickSortTime << "\t\t" << mergeSortTime << "\n";
}
}
return 0;
}
Output:
Performance Testing - Quick Sort vs Merge Sort: Array Size Type Quick Sort (μs) Merge Sort (μs) 1000 random 128.605 823.905 1000 sorted 62.934 777.267 1000 reverse 111.87 791.138 10000 random 1785.84 11835.9 10000 sorted 977.881 10407.6 10000 reverse 1802.92 10413.6 100000 random 26372.1 114149 100000 sorted 12498.9 115641 100000 reverse 22051.3 97096.2
Analysis of the Results:
These performance figures show that Quick Sort significantly outperforms Merge Sort in all cases, particularly with smaller array sizes.
- For Small Arrays (Size 1000):
- Quick Sort is consistently faster across all types of data (random, sorted, reverse).
- Merge Sort takes about 6 to 13 times longer than Quick Sort for the same datasets.
- For Medium Arrays (Size 10,000):
- Quick Sort remains faster, with a noticeable gap. Merge Sort takes 5 to 6 times longer on average.
- Quick Sort is twice as fast on sorted arrays compared to random ones, likely benefiting from faster partitioning.
- For Large Arrays (Size 100,000):
- The performance gap widens dramatically as Merge Sort struggles with memory overhead for larger datasets.
- Quick Sort is about 5 times faster on random data, and up to 10 times faster on sorted arrays.
Key Insights:
- Quick Sort is particularly efficient for smaller datasets and for arrays that are already partially sorted.
- Merge Sort exhibits higher execution times due to the additional memory overhead for merging, even though it has guaranteed O(n log n) time complexity.
- Quick Sort is much more cache-efficient, which explains its superior performance for large arrays.
Further Considerations
- Optimizing for Large Arrays: For very large arrays, consider implementing iterative Quick Sort or switching to a different sorting algorithm like Heap Sort to avoid stack overflow due to deep recursion.
- Hybrid Approaches: Combining Quick Sort with other algorithms, such as Insertion Sort for small sub-arrays, can enhance performance.
Conclusion
Quick Sort remains one of the most efficient and widely used sorting algorithms due to its average-case O(n log n) time complexity and in-place sorting capability. By understanding its underlying mechanics, implementing it thoughtfully in C++, and rigorously testing its performance across various scenarios, developers can harness Quick Sort’s full potential.
Optimizations like the median-of-three pivot selection can significantly improve Quick Sort’s robustness, reducing the likelihood of worst-case scenarios. However, be aware of Quick Sort’s limitations, such as its O(n²) worst-case time complexity, and consider alternative algorithms when necessary.
Congratulations on reading to the end of this tutorial!
For further reading on sorting algorithms in C++, go to the articles
- How To Do Selection Sort in C++
- How To Do Heap Sort in C++
- How To Do Quick Sort in C++
- How To Do Merge Sort in C++
- How To Do Comb Sort in C++
- How To Do Insertion Sort in C++
For performance comparisons with Merge Sort and TimSort, go to How To Do TimSort in C++
To implement Quick Sort in Python, go to the article How to do Quick Sort in Python (With Code Example and Diagram).
Have fun and happy researching!
Suf is a senior advisor in data science with deep expertise in Natural Language Processing, Complex Networks, and Anomaly Detection. Formerly a postdoctoral research fellow, he applied advanced physics techniques to tackle real-world, data-heavy industry challenges. Before that, he was a particle physicist at the ATLAS Experiment of the Large Hadron Collider. Now, he’s focused on bringing more fun and curiosity to the world of science and research online.