How to Implement Quicksort Algorithm in C++
-
Implement Quicksort for
std::vectorContainer - Investigate the Recursion Levels in Quicksort Implementation
This article will demonstrate multiple methods about how to implement quicksort algorithm in C++.
Implement Quicksort for std::vector Container
Quicksort is one of the fastest general-purpose sorting algorithms used in contemporary code bases. It utilizes the divide-and-conquer technique similar to the merge sort algorithm. Although, the former one depends on an operation commonly called partitioning. The original vector is split on the element known as pivot, which delimits smaller elements before it and larger ones after. Note that these comparisons are relative to the pivot value, which the user should choose. Choosing the pivot value happens to be the critical factor for the performance of this algorithm, which we will analyze later in the article. At this point, let’s assume that the pivot element is the first element in the original vector. Once we have the method for pivot selection, we can partition the vector into two smaller vectors that will be recursively sorted in place. Notice that, quicksort operation is similar to the merge sort in that it also partitions the vectors multiple times until their starting positions cross each other.
The following example code implements the algorithm with a recursive sort function that calls the partitionVec function each time it’s invoked. The partitioning process can be done in linear time by swapping elements in the same vector object. The latter operation is implemented using the partitionVec function, which also acts as the sorting function in a certain way.
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
T partitionVec(vector<T> &vec, size_t start, size_t end) {
T pivot = vec.at(start);
auto lh = start + 1;
auto rh = end;
while (true) {
while (lh < rh && vec.at(rh) >= pivot) rh--;
while (lh < rh && vec.at(lh) < pivot) lh++;
if (lh == rh) break;
T tmp = vec.at(lh);
vec.at(lh) = vec.at(rh);
vec.at(rh) = tmp;
}
if (vec.at(lh) >= pivot) return start;
vec.at(start) = vec.at(lh);
vec.at(lh) = pivot;
return lh;
}
template <typename T>
void sort(vector<T> &vec, size_t start, size_t end) {
if (start >= end) return;
auto boundary = partitionVec(vec, start, end);
sort(vec, start, boundary);
sort(vec, boundary + 1, end);
}
template <typename T>
void quickSort(vector<T> &vec) {
sort(vec, 0, vec.size() - 1);
}
int main() {
vector<int> vec1 = {43, 5, 123, 94, 359, -23, 2, -1};
printVector(vec1);
quickSort(vec1);
printVector(vec1);
return EXIT_SUCCESS;
}
Output:
43; 5; 123; 94; 359; -23; 2; -1;
-23; -1; 2; 5; 43; 94; 123; 359;
Investigate the Recursion Levels in Quicksort Implementation
Quicksort has the O(nlogn) average time complexity, which is on par with the merge sort algorithm. Note, though, quicksort algorithm highly depends on the pivot selection method. In this case, we chose the naive version for choosing the pivot value, which was the first element in the vector. This can yield quite bad running times with O(n2) in certain scenarios. In practice, choosing the random pivot has a high probability of yielding the O(nlogn) performance. Although, one should be aware of the pivot selection method based on input data if the maximum performance is required.
We can observe the recursive process in the previous code snippet using the additional function argument that counts each invocation of the sort function. The following example runs a similar test on two vectors of different sizes and prints the corresponding sums. Notice that the sum of recursive calls relates the vector size with the following function - 2n - 1, where n denotes the number of elements.
#include <algorithm>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
template <typename T>
void printVector(const vector<T> &vec) {
for (auto &i : vec) {
cout << i << "; ";
}
cout << endl;
}
template <typename T>
auto partitionVec(vector<T> &vec, size_t start, size_t end) {
T pivot = vec.at(start);
auto lh = start + 1;
auto rh = end;
while (true) {
while (lh < rh && vec.at(rh) >= pivot) rh--;
while (lh < rh && vec.at(lh) < pivot) lh++;
if (lh == rh) break;
T tmp = vec.at(lh);
vec.at(lh) = vec.at(rh);
vec.at(rh) = tmp;
}
if (vec.at(lh) >= pivot) return start;
vec.at(start) = vec.at(lh);
vec.at(lh) = pivot;
return lh;
}
template <typename T>
void sort(vector<T> &vec, size_t start, size_t end, int &level) {
if (start >= end) return;
auto boundary = partitionVec(vec, start, end);
sort(vec, start, boundary, ++level);
sort(vec, boundary + 1, end, ++level);
}
template <typename T>
void quickSort(vector<T> &vec, int &level) {
sort(vec, 0, vec.size() - 1, ++level);
}
int main() {
vector<int> vec3(100, 10);
vector<int> vec4(200, 10);
int recursion_level = 0;
quickSort(vec3, recursion_level);
cout << "level: " << recursion_level << endl;
recursion_level = 0;
quickSort(vec4, recursion_level);
cout << "level: " << recursion_level << endl;
return EXIT_SUCCESS;
}
Output:
level: 199
level: 399
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook