If you're going to post articles from arxiv, please post the top-level description so I can read the abstract before being forced to download a PDF document.
A numerical analysis of Quicksort: How many cases are bad cases? [pdf]
11–13 of 13 posts
Re: A numerical analysis of Quicksort: How many cases are bad cases? [pdf]
#12I remember, at uni, in the second semester, we had an assignment to specifically craft a sequence of n numbers 1..n that would trigger the worst case (#permutations) in a quicksort algorithm that always takes the first number in the array as the pivot. It was a nightmare. I spent days on it, and I was barely able to scrape together a notation to specify such a series. Turns out the sample solutions were like "The app…
What do you mean by worst case #permutations?
Re: A numerical analysis of Quicksort: How many cases are bad cases? [pdf]
#13It strikes me that, if three way partitioning is useful only if you are dealing with a limited set of values in relation to n, you could hash or insertion sort into an array the values for the first pass of the algorithm over the whole array (stopping if the count of uniques got bigger then some value based on n), and then decide to threeway partition if you hadn't stopped.
I feel like the recursive median of medians throws away a great deal of information, given all the comparisons you make. At the very least, for the final step, you know where the high and low values go, and could easily place them in the appropriate sides of the array.