Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

GreedyAlgorithm comments on Worse Than Random - Less Wrong

25 Post author: Eliezer_Yudkowsky 11 November 2008 07:01PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (99)

Sort By: Old

You are viewing a single comment's thread.

Comment author: GreedyAlgorithm 11 November 2008 11:26:35PM 5 points [-]

Brian, the reason we do that is to avoid the quicksort algorithm being stupid and choosing the worst-case pivot every time. The naive deterministic choices of pivot (like "pick the first element") do poorly on many of the permutations of the input which are far more probable than 1/n! because of the types of inputs people give to sorting algorithm, namely, already or nearly-already sorted input. Picking the middle element does better because inputs sorted inside to outside are rarer, but they're still far more likely than 1/n! apiece. Picking a random element is a very easy way to say "hey, any simple algorithm I think up will do things that correlate with algorithms other people think up, so will hit worst-case running times more often than I'd like, so I'll avoid correlation with other people".

There are variants of quicksort that completely avoid worst-case complexity by choosing the true median of the list each time. They incur an extra cost that makes average case worse, though, and they're usually not the best choice because we're almost always not trying to avoid the worst-case for a single run, we're actually trying to make the average case faster.