Exploring the Worst Case Complexity of Quicksort (2015)
tyler-davis.com
Exploring the Worst Case Complexity of Quicksort (2015)
1–7 of 7 posts
Re: Exploring the Worst Case Complexity of Quicksort (2015)
#2This was just as ridiculously nerdy as it was when friends of mine from school and I did it in 1981 -- in basic on the trs80 though :D
Re: Exploring the Worst Case Complexity of Quicksort (2015)
#3I wonder if the author is aware of antiqsort
https://www.cs.dartmouth.edu/~doug/aqsort.c and https://github.com/matslina/qsort/blob/master/antiqsort.c ...
Re: Exploring the Worst Case Complexity of Quicksort (2015)
#4The textbook solution is to use this pivot selection algorithm:
https://en.wikipedia.org/wiki/Median_of_medians
In practice it is not really worth it.
Re: Exploring the Worst Case Complexity of Quicksort (2015)
#5The light grey text with the white background, seems to be a popular design choice. But I have trouble reading this page do to the lack of contrast.
Re: Exploring the Worst Case Complexity of Quicksort (2015)
#6This was just as ridiculously nerdy as it was when friends of mine from school and I did it in 1981 -- in basic on the trs80 though :D
Was that Level I or Level II BASIC? ;)
Re: Exploring the Worst Case Complexity of Quicksort (2015)
#7The textbook solution is to use this pivot selection algorithm: https://en.wikipedia.org/wiki/Median_of_medians In practice it is not really worth it.
No matter how clever you are with an algorithm, somebody wrote a paper on it in the 70s.