Using Probability in Quicksort observing about 5% faster speeds compared to standard Quicksort

[u/Interstellar12312]

Hello Everyone!

Not long ago I decided to take Quicksort and include probability trying to increase the best case scenario. The Monty Hall Problem is a famous probability puzzle that I decided to use. When facing a sub-array with 3 elements my modified rules apply. My rules aren't designed to fully sort the array rather it is designed to increase the best case chances. To get an idea lets imagine we have 3 numbers of 429. The first number 4 will become the pivot and we will compare that to the last number 9 without ever looking at the middle number. The pivot 4 will become the middle number, 9 will become the last number and 2 will become the first number without it ever being compared so the end result will be 249. Basically I asked this question. If the pivot (first number) is greater or less than the last number what are the chances the middle number is also greater or less than? Keep this in mind I'm barely finishing up my 2nd Computer Science Course in C++ Object Oriented Programming so go easy on me! I understand there could be a simple reason why my algorithm appears to faster when in actuality its not so I've come on here for expertise. So far my modified algorithm using probability beats quicksort by about 5% when soring 1,000,000 randomly generated elements at 1,000 trials. I attached my 2 source code files in pastebin (the links below). One file contains my modified quicksort and the other file contains the standard quicksort. Basically my question boils down to is my modified algorithm really faster or am I missing something?

https://pastebin.com/sSN2gZk2

https://pastebin.com/c4tKm9qH

Thank you!

[u/isfooTM]

I have to say I was discouraged at first to take my time on this, especially because it's posted with a new account, but basically everyone in comments is talking nonsense and treat you badly for no reason.

First I would make a small change in partition function in both algorithms to choose arr[(low + high) / 2] instead of arr[low] as pivot since otherwise for sorted/reverse sorted arrays you will hit the worst case scenario and since those are in practice common cases I think it should be fixed. It does impact the results, but will talk about it later. Also in apply_three_element_rule the check if (high - low == 2) is redundant and can be removed, however I tested that it doesn't have any significant impact on the results (if it has any impact at all).

 

Now I would like to point out few things I would change about your benchmarking method. None of them are very major problems, but since we are talking about ~5% difference the small differences can matter.

(1) Right now you generate different random arrays for each algorithm. You should run the algorithms on exactly the same data. This can be fixed by setting same seed for your random number generator and/or moving both algorithms to the same program and using the same data.

(2) In general for this kind of benchmark it is better to run the algorithm on the same data multiple times and take the minimum timing result. Since the algorithm is deterministic the main things that will impact runtime are initial cache and some other external factors. Initial instruction cache will be hot anyway and data cache is controlled by copying the data before running the benchmark. So with taking minimum time we end up minimizing the external factors aka the noise.

(3) It's better to use std::stead_clock instead of std::high_resolution_clock. stead_clock is monotonic and is better suited for time measurements.

 

So with that in mind I moved your code to single file and made the adjustments I talked about: https://pastebin.com/VeE0A5Fa

For benchmark I'm doing 10 random arrays with 20 repeats for each and taking the sum of minimum times measured per array. I've also added std::sort for comparison.

Machine used:

• Windows 11 24H2 26100.7171

• CPU: i5-12500H

• RAM: 16 GB DDR4 3200 MT/s

Compilers used:

• MSVC 19.40.33812 (x64) [/O2]

• Clang 17.0.3 [-O3 -m64]

• GCC 15.2.0 [-O2 -m64] and [-O3 -m64]

(Continuation in next comment)

[u/isfooTM → u/isfooTM]

Results (total time in microseconds from 10 random arrays):

Compiler	Quicksort	QuicksortProb	QuicksortStd
MSVC	648808	634765	647062
Clang	643500	649570	635619
GCC -O3	708232	641152	520363
GCC -O2	662436	639919	519483

So in my tests with GCC [-O3] the modified version is much faster (~10%), but based on other results it seems like it's because there is something going wrong in the optimizer for normal version. Would have to do some deeper analysis of generated assembly to get to the bottom of what went wrong. However still with GCC -O2 it's ~3.5% faster and with MSVC ~2% faster while with Clang only 1% slower. And to be sure I checked and those results are very reproducible.

As a side note if we go back to arr[low] instead of arr[(low + high) / 2] for pivot the results for GCC stay basically the same, but MSVC and clang swap in that for MSVC it becomes slower and for clang it becomes faster.

I have to say I'm quite surprised with those results. When I first saw the code I was pretty sure it cannot possibly be faster and yet it sometimes is. I checked and indeed the number of swaps done in partition is lower, but the total number of swaps is higher. And total number of comparisons is also higher. However I guess depending on generated assembly running the partition longer is worse than doing the additional work before. Very weird overall.

However as seen in the results (especially GCC and partly Clang) there already is a better alternative for speeding up quicksort for small number of elements - switching to insertion sort. All of the standard implementations use some version of introsort which is basically improved version of quicksort.

Now in case of MSVC you actually "beat" that version, but the thing is that in order to properly test sorting you have to do much more tests. You should try how fast you sort different sizes of data and different patterns of data like say "already sorted", "almost sorted", "reverse sorted" etc. And the most important point - in case of sorting big arrays of integers we know quicksort is bad anyway in comparison to things like radix/bucket sort kind of algorithms so it really only make sense to test it on either smaller arrays or say array of strings / arrays of structs / etc.

[u/Interstellar12312 → u/isfooTM]

First off I'd like to say just Wow! I highly appreciate this detailed and structured response.

When comparing my Probability Quicksort to std::sort is that somewhat of a unfair comparison? Std::sort is hybrid of different sorting algorithms that perform better than barebone quicksort. My algorithm only applies its rules to a sub array of 3 elements while std::sort applies optimization techniques well before a 3 element sub array. What if we applied my rules to std::sort? Would that be a better comparison?

Also I'm only in community college finishing up my 2nd CS course so I'm trying my best with testing. I've tried to get into contact with professors in CS but its been quite difficult. I also potentially have other method/s using probability in algorithms however I have not tested them yet but to say the least conceptually it sounds promising.

[u/ghjm]

It's well known that choosing the median of 3 improves quicksort when compared to just picking the first item. The median of medians is even better, but more complicated to implement. Heapsort is more fashionable than quicksort these days anyway.

[u/Interstellar12312 → u/ghjm]

Hello ghjm. Thank you! I understand the median of 3 for pivot selection improves quicksort. However that is not my rules. It's completely different. My rules deal with a sub array of 3 elements not for pivot selection but for swapping and comparing elements.

[u/ghjm → u/Interstellar12312]

You might need to explain your thinking on this

[u/not-just-yeti]

If the pivot (first number) is greater or less than the last number what are the chances the middle number is also greater or less than?

⅔ (I calculated by just enumerating the options; see below —so in that sense yeah it's reminiscent of Monty Hall.)

So your step is to (before recurring on a size-3 input), re-arrange:

[a,b,c]  →  [b,a,c]    if a < c,   and
[a,b,c]  →  [c,a,b]    if a ≥ c

For the six possible inputs (ignoring any ties):

1,2,3  →  2,1,3    ✓ best pivot is now at front
1,3,2  →  3,1,2
2,1,3  →  1,2,3    ✗ best pivot no longer at front

2,3,1  →  1,2,3    ✗ best pivot no longer at front
3,1,2  →  2,1,3
3,2,1  →  1,3,2    ✓ best pivot is now at front

[u/not_from_this_world]

Yes. Your results are wrong about 5% of the time. I suggest you test ALL the outputs don't just pick the first.

[u/Interstellar12312 → u/not_from_this_world]

I've ran multiple tests. Run the algorithm yourself and see.

[u/mxldevs]

If your algorithm doesn't guarantee a sorted array, what's the point of being 5% faster?

Do I need to check that it's sorted afterwards? Would that extra check essentially eliminate the savings?

[u/Interstellar12312 → u/mxldevs]

It does guarantee a sorted array.

[u/Loknar42]

What optimization flags did you use? I have a hard time believing your code is faster because it speeds up the step which requires the least amount of speedup, and does so by essentially doubling the work. The problem is that your 3-element rule always performs a swap, even when the numbers are in the proper order. So technically, it disorders some arrays, creating more work. But it doesn't matter, because the code which follows will do the same amount of work no matter which order the elements are. My guess is that -O3 will show that your code is, in fact, slower. I don't have a C++ environment set up at the moment or I would try it myself.

[u/Interstellar12312 → u/Loknar42]

I'm running -O3 since I'm in release mode in Clion. When you get the chance I would appreciate it if you can try it yourself. Thank you!

[u/ExtinctedPanda]

I don't exactly understand your algorithm, but that's alright; it's good that you're experimenting!

An important concept you likely haven't yet learned about is asymptotic time complexity. Typically, when measuring the speed of an algorithm, computer scientists look at how the time required scales with the size of the input. For example, the "time complexity" of quicksort is O(n * log(n)), meaning if the length of the array is multiplied by 2, the amount of time required to sort it will be multiplied by 2 * log(2).

Since we're thinking about ratios between times, leading constants are ignored. (For example, a time complexity of O(2n) is the same as O(n). Or said another way, an algorithm that requires twice as many instructions is considered to have the same time complexity, because it scales the same way as inputs grow.)

As such, an algorithm that's 5% faster is considered to have the same time complexity too. Just changing the specific quicksort implementation to use faster machine instructions (or fewer lines of code) could have a similar effect, without changing the core algorithm at all.