jan
Coursework analysis of quicksort results in (very) unexpected behaviour
Desc:
Implemented simple recursive quicksort algorithm to test it on a 'A' shaped arrays of different sizes (eg. [1, 2, 3, 4, 5, 5, 4, 3, 2, 1]).
Expected behaviour: (BASED ON MY THOUGHTS)
- rightmost pivot: O(n^2) - at least for 'A' shaped arrays
- middle pivot: O(n^2) - at least for 'A' shaped arrays
- random pivot: from O(n log n) to O(n^2)
Actual results are on the diagram.
Problems:
- random pivot ends up being basically instant (0-2ms) even for arrays of size 72 000
- middle pivot ends up taking 2x the amount of rightmost pivot
I also tested it against random shuffled arrays using Random.Shuffle, and for some reason introducing random to all pivot strategies makes all the timings >2ms, so it looks like using random makes any pivot strategy instant. I got no idea why it happens, I've also made sure that all arrays are not sorted before sorting, and sorted after sorting.
Code: https://pastebin.com/3zF7SLbz
.NET 8
VS2022
Please help..
66 replies