For fun, I decided to implement the quickest Quicksort I could. This is what I came up with. How can I make it better?
I know that it's slower for sorted and already reversed lists (through testing), but I'm not certain why. What I do know is that this algorithm reverses the list past the pivot, if the list was sorted/reversed to begin with, but I'm not sure why that would slow it down as much as it does.
#pragma once
#include "InsertionSort.h" // assume this has a good implementation of Insertion Sort
namespace QuickSort
{
template<typename iterator>
iterator medianOfThree(iterator low, iterator high) {
iterator mid = low + (high - low) / 2; // get an iterator to the middle index
if (*low <= *mid and *mid <= *high) return mid;
if (*high <= *mid and *mid <= *low) return mid;
if (*mid <= *low and *low <= *high) return low;
if (*high <= *low and *low <= *mid) return low;
return high;
}
/*
* Sorts the list given by the two iterators (begin and end) by virtue of
* Quicksort.
*/
template<typename iterator>
void sort(iterator begin, iterator end) {
// the loop handles one of the partitions, guaranteeing "tail-call" optimization for the larger
// partition. The smaller partition goes into the recursive step
while (end - begin > 1) {
if (end - begin < 20) { // this is supposed to make it faster for small lists
InsertionSort::sort(begin, end);
return;
}
auto value = *medianOfThree(begin, end - 1);
iterator i = begin; // i marks the top of the "smaller" partition
iterator j = begin; // j marks the bottom of the "larger" partition
iterator n = end - 1; // n allows us to swap the larger values to the end
// This partitioning algorithm allows us to partition into 3 groups:
// smaller, equal, larger.
// This makes it so that with large amounts of repeated values, we are faster.
while (j <= n) {
if (*j < value) {
std::iter_swap(i, j);
++i;
++j;
} else if (value < *j) {
std::iter_swap(j, n);
--n;
} else {
++j;
}
}
// at this point, i marks the end of the "smaller" partition
// and j marks the beginning of the "larger" partition.
// Note that between them resides values equal to the pivot.
int size1 = i - begin; // this is the size of the "smaller" partition
int size2 = end - j; // this is the size of the "larger" partition
if (size1 < size2) {
QuickSort::sort(begin, i); // recurse on the smaller partition
begin = j; // this partition is handled by the next iteration of the loop
} else {
QuickSort::sort(j, end);
end = i;
}
}
}
}
When I tested this code, this is what I got:
Sorting a sorted vector of size 1000000 Seconds: 1.159602842 Sorting a sorted vector of size 1500000 Seconds: 1.160466839 Sorting a sorted vector of size 2000000 Seconds: 2.269401411 Sorting a reversed vector of size 1000000 Seconds: 0.551178608 Sorting a reversed vector of size 1500000 Seconds: 0.828606600 Sorting a reversed vector of size 2000000 Seconds: 1.263003406 Sorting a random vector of size 1000000 Seconds: 0.099294498 Sorting a random vector of size 1500000 Seconds: 0.151264950 Sorting a random vector of size 2000000 Seconds: 0.210116894 Sorting a binary random vector of size 1000000 Seconds: 0.006512821 Sorting a binary random vector of size 1500000 Seconds: 0.009594559 Sorting a binary random vector of size 2000000 Seconds: 0.013067604 Sorting a small random vector of size 1000000 Seconds: 0.090787581 Sorting a small random vector of size 1500000 Seconds: 0.137927258 Sorting a small random vector of size 2000000 Seconds: 0.405081084
Where sorted means consecutive integers from 0 to size - 1, reversed is the reverse of that, random means calls to rand() (I did not seed it), binary random means rand() % 2, and small random means rand() % (size / 10).
%is. \$\endgroup\$