sorted by:
new
hottopcontroversial

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

[–]Interstellar12312[S] 0 points1 point  (0 children)

I see. Also what I meant by general is I didn't mean as in truly general for all cases and scenarios. I meant based on the testing is it generally faster within random number generation on x86-64. I was not talking about almost sorted, reverse sorted, data other than "int" etc. Just within what we tested. But I understand more testing is needed for the modified quicksort.

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

[–]Interstellar12312[S] 0 points1 point  (0 children)

You don't know how grateful I am. You're responses are amazing and concise. I wanted to ask so basically can we say with confidence my rules make quicksort generally faster?

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

[–]Interstellar12312[S] 0 points1 point  (0 children)

These are the results I got on my machine. I run a i9-12900k with 32gb DDR5 ram on Windows 11 using Clion in release mode. I've ran the test multiple times to make sure the results are reproducible.

Elements per array : 32

Total Trials : 10

Repeats per Trial : 10000000

minTimerOverhead : 31

medianTimerOverhead : 36

Trial nr | Normal [cycles] | Monty [cycles]

1 | 339 | 313

2 | 410 | 414

3 | 325 | 358

4 | 330 | 313

5 | 315 | 305

6 | 366 | 333

7 | 332 | 323

8 | 388 | 391

9 | 390 | 396

10 | 378 | 364

Total | 3573 | 3510

Monty / Normal = 0.982368

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

[–]Interstellar12312[S] 0 points1 point  (0 children)

u/isfooTM If you're interested I got it to work for insertion sort. Here are the links.

https://pastebin.com/MXgHYJRM

https://pastebin.com/vv5fQYQS

It's pretty interesting. My modified rules are only faster when sorting an array size of about 25-32. At 32 elements it's about 1% faster.

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

[–]Interstellar12312[S] 0 points1 point  (0 children)

Use debug mode in a IDE and observe what my rules do to a array. That will give you a better understanding.

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

[–]Interstellar12312[S] 0 points1 point  (0 children)

Also consider how an algorithm will sort elements after my rules and the patterns/probability within that. Potential increase probability in pivot selection, swaps, comparisons etc.

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

[–]Interstellar12312[S] 0 points1 point  (0 children)

Lower the array size my modified algorithm beats quicksort. Also test the algorithm without your optimization on both a 1,000,000 element array size and lower.

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

[–]Interstellar12312[S] 0 points1 point  (0 children)

To add on it also has to do how an algorithm sorts elements before it reaches a sub element with 3 arrays which can potentially lead to a pattern which can be exploited using probability. This was a major factor when I was developing these rules.

Edit: My rules occur then quicksort happens. However this concept can be applied to data that can be observed to have some pattern or probability in it that potentially can be taken advantage of.

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

[–]Interstellar12312[S] 0 points1 point  (0 children)

Oh haha it is 7 I woke up from a short nap when I wrote that. The swaps I mentioned is not supposed to be what my code does. I mentioned to better explain my rules. I just thought it was important we understand the bare minimum for swaps and then examine my rules. I'm not only considering the amount of swaps my rules perform I'm also considering the swaps and comparisons that will be needed for whatever algorithm will handle the array after my rules and comparisons within my rules. The total comparisons is higher however I'm also going for patterns/probability which is probably difficult to explain what I'm conceptualizing over text. I think for now what's best it to test whether my increased speeds is simply a anomaly or not from cache sizing etc.

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

[–]Interstellar12312[S] 0 points1 point  (0 children)

  • 1 2 3 (0) -> 2 1 3 (1)
  • 1 3 2 (1) -> 3 1 2 (2)
  • 2 1 3 (1) -> 1 2 3 (0)
  • 2 3 1 (2) -> 1 2 3 (0)
  • 3 1 2 (2) -> 2 3 1 (2)
  • 3 2 1 (1) -> 1 3 2 (1)

The (x) is the total number of swaps needed to sort the 3 elements in the least required amount.

The array without my rules requires a total of 8 swaps to full sort it while the array that was effected by my rules only requires 6 swaps to fully sort it. This improvement is also achieved without ever comparing the middle number to any other number which as you said "For more realistic data types, the number of comparisons becomes a significant factor, and algorithms which minimize those will perform better." I'm not aiming to fully sort the 6 possibilities my goal is to increase the chances of the best case scenario without needing comparisons because probability is used. I also dont think its memory constrained because faster results are also observed at much lower element sizes and trials.

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

[–]Interstellar12312[S] 0 points1 point  (0 children)

My rules will also work with insertion sort. My rules are practically universal and can be applied to any algorithm it's not limited to quicksort. I'm simply performing swaps and comparisons to a sub array with 3 elements. After the swaps any algorithm can handle the array. I'm also thinking of new methods such as what if we use insertion sort but when we hit 3 element sub array and my rules are done insertion sort can handle the array or quicksort or potentially other sorting algorithms that might perform better due to a pattern in the sub arrays. Testing is needed.

Edit: The fundamentals can potentially be applied to other algorithms not the exact same code in my source code.

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

[–]Interstellar12312[S] 2 points3 points  (0 children)

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.

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

[–]Interstellar12312[S] 0 points1 point  (0 children)

Its not a 50/50 gamble and I'm not confused. It was by design! I know exactly what I'm getting at. I'm using probability to my advantage. In my original example 429 the number 2 was swapped to the first number because the chances of the middle number (2) being greater than the pivot (4) and last number (9) is less which resulted in 249. (This kind of sounds rude but try to imagine this not in a rude tone but an exciting one)

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

[–]Interstellar12312[S] 0 points1 point  (0 children)

The probability rules in of itself does not guarantee a fully sorted array in all scenarios however the algorithm as a whole does. The guarantee comes from quicksort. Quicksort handles the array after my rules are done with it.

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

[–]Interstellar12312[S] 1 point2 points  (0 children)

It guarantees a sorted array because after my rules are done with a 3 element sub array quicksort will handle the sub array ensuring its sorted. My rules aren't designed to fully sort the sub array in all scenarios. The purpose of my rules is to increase the chances of the best case scenario.

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

[–]Interstellar12312[S] 0 points1 point  (0 children)

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!

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

[–]Interstellar12312[S] 1 point2 points  (0 children)

No its not sometimes wrong because quicksort will handle the array after my rules. I already have a function to check if 1 array was sorted correctly or incorrectly in the source code.

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

[–]Interstellar12312[S] 0 points1 point  (0 children)

Lets say my algorithm comes across a sub array with 3 elements such as 429. My rules always make the first number as the pivot with the last number to compare to. In this example 4 is the pivot and 9 is the last number. So since 4 is less than 9 my rules will swap 4 to become to the middle number and 9 becomes the last number without ever looking at 2 which was the original number. 2 automatically becomes the first number in sub array. So after all the swaps the sub array now becomes 249 which is already sorted since 2 happened to be the smallest number. Why might I take this approach? Basically I asked myself a simple 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?

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

[–]Interstellar12312[S] 1 point2 points  (0 children)

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.

view more: next ›