Quicksort is an efficient, recursive sorting algorithm in C++ that divides an array into smaller sub-arrays based on a pivot element, sorting them independently.
#include <iostream>
#include <vector>
void quicksort(std::vector<int>& arr, int left, int right) {
int i = left, j = right;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
std::swap(arr[i], arr[j]);
i++;
j--;
}
}
if (left < j) quicksort(arr, left, j);
if (i < right) quicksort(arr, i, right);
}
int main() {
std::vector<int> arr = {3, 6, 8, 10, 1, 2, 1};
quicksort(arr, 0, arr.size() - 1);
for (int num : arr) std::cout << num << " ";
return 0;
}
What is Quicksort?
Definition of Quicksort
Quicksort is an efficient sorting algorithm that follows the divide-and-conquer principle. It was developed by Tony Hoare in 1960 and has since become one of the most popular sorting algorithms due to its average-case efficiency and simplicity. The algorithm sorts an array by selecting a pivot element and partitioning the other elements into two subarrays according to whether they are less than or greater than the pivot.
How Quicksort Works
The quicksort algorithm is built on a fundamental process of dividing an array into smaller segments, sorting those segments, and then combining them to produce a sorted array. This is achieved through a clear and efficient methodology:
-
Choosing a Pivot: The pivot can be any element from the array, and it can significantly affect performance. Common strategies for choosing a pivot include selecting the first element, the last element, a random element, or the median.
-
Partitioning the Array: After selecting a pivot, the array is rearranged so that all elements less than the pivot come before it and all elements greater come after it. This forms two subarrays around the pivot, which is now in its final position.
Quicksort Algorithm Steps
Step-by-Step Explanation
Choosing a Pivot
The selection of the pivot is crucial for the algorithm's efficiency. An optimal pivot choice ensures the resulting subarrays are as balanced as possible, leading to better performance.
Partitioning the Array
The partitioning process rearranges elements in the array and segregates them into groups. Below is a basic example of a partition function implemented in C++:
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
In this function, the last element is chosen as the pivot and is used to partition the array.
Recursive Quicksort Implementation
After partitioning, the algorithm calls itself recursively on the two subarrays. Here’s how this is implemented in the quicksort function:
void quickSort(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);
}
}
In this code block, if the start index (`low`) is less than the end index (`high`), the algorithm proceeds with partitioning and recursion.
Example of Quicksort in C++
Full Quicksort Program
Here’s a complete C++ program demonstrating the quicksort algorithm. It combines the partitioning and sorting functions and displays the sorted array:
#include <iostream>
using namespace std;
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
void quickSort(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);
}
}
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";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
In the main function, an unsorted array is defined, and the quicksort function is called. After sorting, the sorted array is printed.
Performance of Quicksort
Time Complexity
The time complexity of quicksort is influenced by the pivot selection:
- Best Case: O(n log n) — occurs when the pivot is chosen optimally, leading to evenly sized partitions.
- Average Case: O(n log n) — this is the expected time complexity for most inputs.
- Worst Case: O(n²) — happens when the pivot chosen is the smallest or largest element, resulting in unbalanced partitions, particularly in already sorted or nearly sorted arrays.
Space Complexity
Quicksort is considered an in-place sorting algorithm, meaning that it requires a small, constant amount of additional storage space. Its average space complexity is O(log n) due to the recursion stack.
Comparison with Other Sorting Algorithms
When comparing quicksort with other common sorting algorithms like mergesort and bubblesort, several advantages and disadvantages arise:
-
Pros of Quicksort:
- Generally faster than other O(n log n) algorithms due to better cache performance.
- In-place sorting reduces memory usage.
-
Cons of Quicksort:
- Poor performance on sorted or nearly sorted arrays without pivot optimization.
- Recursive implementation can lead to stack overflow for large datasets.
Optimizations for Quicksort
Tail Recursion Optimization
Optimizing the recursion can enhance performance and prevent stack overflow. By converting certain recursive calls into loop iterations (tail recursion), we reduce the maximum stack depth.
Choosing the Right Pivot
Choosing a good pivot can substantially improve performance. Some techniques include:
- Median-of-Three: Select the median of the first, middle, and last elements.
- Random Pivot: Randomly selecting a pivot can help avoid the worst-case scenario on sorted arrays.
Hybrid Approaches
Incorporating insertion sort for smaller arrays can yield even faster performance. Here's an example of a hybrid approach:
void insertionSort(int arr[], int low, int high) {
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
void quickSort(int arr[], int low, int high) {
if (high - low < 10) {
insertionSort(arr, low, high);
} else {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
}
This code uses insertion sort for segments of the array that are smaller than 10 elements.
Common Pitfalls and Mistakes
Lack of Base Case
A critical aspect of recursion is ensuring a proper base case to terminate function calls. Omitting this can lead to infinite recursion. For example, not stopping when `low` is not less than `high` results in an endless loop.
Choosing the Wrong Pivot
Improperly selecting a pivot can drastically affect the algorithm's efficiency. Consistently choosing the first or last element can lead to performance degradation in sorted datasets, causing the worst-case time complexity.
Conclusion
Quicksort in C++ is a powerful and efficient sorting algorithm that combines complexity with elegance. Its speed and versatility in handling various data sets make it a valuable tool for programmers and developers. By mastering quicksort, you'll not only enhance your coding skills but also deepen your understanding of sorting algorithms and their practical applications.
Try coding the quicksort algorithm yourself, using the practices discussed in this guide. For further learning, explore additional resources on C++ programming and advanced sorting algorithms, which will broaden your skill set and enhance your programming proficiency.
