C++ Quicksort implementation

Question

I wrote this quicksort implementation in C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
void myquicksort(std::vector<int>& A, const int left, const int right)
{
 int i = left;
 int j = right;
 int pivot = A[left + ((right - left) / 2)];
 while(i < j)
 {
 while(A[i] < pivot) ++i;
 while(A[j] > pivot) --j;
 if(i <= j)
 {
 std::swap(A[i], A[j]); 
 ++i;
 --j;
 }
 }
 if(left < j) myquicksort(A, left, j);
 if(i < right) myquicksort(A, i, right);
}
void quick_sort(std::vector<int>& A)
{
 myquicksort(A, 0, A.size() - 1);
}
int main()
{
 std::vector<int> v{8, 37, 4, 12, 1, 19, 13, 6, 23, 42, 3};
 auto v2 = v;
 quick_sort(v);
 std::sort(v2.begin(), v2.end());
 assert(v2 == v);
}

Can you share your opinions?

One remark: I am curious about times where i == j on some occasions in those lines:

 if(left < j) myquicksort(A, left, j);
 if(i < right) myquicksort(A, i, right);

therefore calling myquicksort with overlapping ranges. Is that an issue?

• greybeard: I am curious about times where i == j: me, too. Apart from the idea to std::swap(A[i], A[i]) (instead of just handling (left, i-1) & (i+1, right)), are there more possibilities for i == j than 1) pivot occurs at pivotIndex === left + ((right - left) / 2), only, or 2) at that index and the ones below and above, too?

Answer 1

void myquicksort(std::vector<int>& A, const int left, const int right)
{
 // .......
}

Is myquicksort() supposed to be callable by those that use your sort? If not, hide those internal implementation details by using a namespace to signify that.

std::vector::operator[] parameter takes a pos of type size_type. Consider using a similar type (std::vector<int>::size_type, std::size_t).

---

int pivot = A[left + ((right - left) / 2)];

Certain inputs can make your partitioning algorithm behave poorly, degrading from \$O(n\ log\ n)\$ to \$O(n^2)\$. In your implementation, your pivot choice of picking the median is vulnerable to organ-pipe input sequences (\1,ドル 2, ..., n/2, ..., 2, 1\$). If you want to use the median, consider using a stronger pivoting rule, such as the median-of-\$k\$ (median-of-3, median-of-9, etc).

Certain inputs also just break your code. Your implementation produces a segmentation fault when trying to sort an empty sequence.

---

One remark: I am curious about times where i == j on some occasions in those lines:

if(left < j) myquicksort(A, left, j);
if(i < right) myquicksort(A, i, right);

therefore calling myquicksort with overlapping ranges. Is that an issue?

You won't be able to parallelize it using task parallelism while doing more comparisons and utilizing more space. Just have your two calls work over the ranges [left, j] and [j + 1, right].

---

Keep functions short and simple. They become easier to understand, test, and reuse. Ideally, your myquicksort would refactor the median calculation and partitioning into their own functions. Example:

void myquicksort(std::vector<int>& A, const std::size_t left, const std::size_t right) {
 if (right - left <= 1) {
 return;
 }
 const auto pivot_value = range_median(A, left, right);
 const auto partition_point = hoare_partition(A, left, right, pivot_value);
 myquicksort(A, left, partition_point);
 myquicksort(A, partition_point + 1, right);
}

Now if you decide that you want to use a different pivoting or partitioning strategy, you are affording yourself the opportunity to reuse code.