2 ms·
Sigh. I give up. I'll just suggest you open up a copy of clrs and read the section on randomized quick sort. There is a section dealing with this killer adversa
by jchonphoenix 16y ago
Sigh. I give up. I'll just suggest you open up a copy of clrs and read the section on randomized quick sort. There is a section dealing with this killer adversary exactly and why this adversary does not kill randomized quick sort.
Your logic is failing because your thinking of this from a programmers perspective when, in reality this is an algorithm analysis problem which is theory.
- sesqu 16y agoI don't have that book, so you'll have to explain the reasoning if you want to convince me. I did find the MIT OCW lecture transcript on randomized quicksort, based on the book, and it described how randomization probably defeats an adversary supplying a worst-case initial permutation when the pivoting algorithm is known. That's a different adversary to the one we are discussing, even if relaxed; it has to supply an input that is consistent and fixed. They also motivated the scenario in terms of competition, which I find less reasonable than actual malevolence, but that bears little relevance now. When theory and practise diverge, there is strong reason to hold the practise as more defensible than the theory. How would you say the practice should be amended to not suffer from this problem that is apparently not extant in theory? I hold that it cannot, for this adversary is more capable than the other.