News for hackers. Stuff that matters.
Re:Helping a stranger, and why you should understand NP-comp... by gms7777 on Monday November 04, 2013 @10:01AM (#6668858)
> They can tell you that the most efficient algorithm for ordering (randomised) data is Quicksort, which has a Big-O notation of O(nlogn)

I know this is nitpicky, but quicksort is, worst-case, O(n^2), meaning a large number of comparison based sorting algorithms are faster than it. Its in the average case that Quicksort wins.

Re:Helping a stranger, and why you should understand NP-comp... by lifebeyondfife on Monday November 04, 2013 @10:14AM (#6668942)
That's why I said "(randomised)". The worst case occurs when the list to be sorted is already ordered and you select the head of the list as the pivot point.

Even though other algorithms such as Mergesort also have O(nlogn), Quicksort is normally the preferred implementation because it's relatively easy to do in-place and generally is the most efficient[1] of all the sorting algorithms.

[1]Not my field of expertise though, happy to be told I'm wrong.

Re:Helping a stranger, and why you should understand NP-comp... by gms7777 on Monday November 04, 2013 @10:28AM (#6669050)
You're definitely not wrong, its generally the fastest. Efficient is a bit of a loaded worded in these contexts, and I feel as though when discussiing algorithms, unless otherwise specified, the assumption is you're discussing worst-case efficiency (because while worst case isn't always the most useful metric, is usually the most easily defined and derived one). And randomizing data doesn't necessarily guarantee that you won't still land on a worst-case starting order (as is the nature of randomness). As I said though, that is an entirely nitpicky point.
Re:Helping a stranger, and why you should understand NP-comp... by tubbzor on Monday November 04, 2013 @03:40PM (#6671022)
>And randomizing data doesn't necessarily guarantee that you won't still land on a worst-case starting order (as is the nature of randomness).

This is the beauty of randomized analysis in the worst-cases. The worst-case occurs if and only if the random generator spits out a sorted list. If all permutations are equally likely, a list of n elements has probability 1/n! of coming out sorted = O(n^2).

Even in practice, this is very pessimisstic as it only occurs with a probability of 1/n! and is therefore extremely rare.

Re:Helping a stranger, and why you should understand NP-comp... by eru on Monday November 04, 2013 @02:05PM (#6670447)
Randomized QuickSort has an expected worst case runtime of O(n log n).

To pick that part, first you write your (randomized) QuickSort, then your antagonists picks the worst case, and last you let your algorithm run and pick its random numbers. No matter how the antagonist chooses the input (but not the random numbers), you get O (n log n) expected runtime.

This is different from an average (over all inputs) run time.

Re:Helping a stranger, and why you should understand NP-comp... by lifebeyondfife on Monday November 04, 2013 @10:33AM (#6669090)
I see what you mean. Thanks for taking the time out to nitpick.
Re:Helping a stranger, and why you should understand NP-comp... by gphilip on Monday November 04, 2013 @11:21AM (#6669399)
This is even more nitpicky, but the worst-case running time can be improved to O(n log n) by choosing the median of the input numbers to be the pivot each time, in O(n) time. This works irrespective of whether the list is sorted or not. This is /not/ useful in practice because of the overhead of choosing the pivot this way, but hey, theory is theory!

"... given a worst-case O(n) selection algorithm, one can use it to find the ideal pivot (the median) at every step of quicksort, producing a variant with worst-case O(n log n) running time. In practical implementations this variant is considerably slower on average, but it is of theoretical interest, showing how an optimal selection algorithm can yield an optimal sorting algorithm."

https://en.wikipedia.org/wiki/Quicksort#Selection-based_pivo...

Re:Helping a stranger, and why you should understand NP-comp... by ggchappell on Monday November 04, 2013 @12:03PM (#6669671)
A better way to improve the worst case to O(n log n) time is to use the "Introsort" optimization.[1] Keep track of the recursion depth (with optimized-out tail-recursive calls counted). If the depth exceeds k * log_2(n) [maybe k = 2?], then switch to Heap Sort for the current sublist.

This optimization is useful in practice. The result is a sort that is as fast as Quicksort on average, but unlike Quicksort runs in O(n log n) time. So, for example, the C++ Standard Library function std::sort will use Introsort in any good implementation.

Despite its wonderfulness, Introsort is strangely little known. Algorithms texts rarely mention it, for some reason.

[1] https://en.wikipedia.org/wiki/Introsort

Re:Helping a stranger, and why you should understand NP-comp... by eru on Monday November 04, 2013 @02:08PM (#6670464)
Introsort is good in practice, but it's not a quicksort.

If you are interested in theory, the pivot in linear time algorithm (like QuickSelect) is truly marvelous. It also provides a good study of how simple a randomized algorithm can be, and how to de-randomize it into something much more complicated but deterministic. But in some sense that complications help you understand, because otherwise, randomize algorithms are often `magic'.

Re:Helping a stranger, and why you should understand NP-comp... by ggchappell on Monday November 04, 2013 @05:02PM (#6671498)
I'm familiar with the median-of-medians linear-time selection algorithm (a.k.a. BFPRT). But I don't recall ever seeing a construction of a pivot-finding algorithm using de-randomization. Do you have a reference for this?
Re:Helping a stranger, and why you should understand NP-comp... by eru on Tuesday November 05, 2013 @12:15AM (#6673353)
Sorry, that was from memory. (Can't you interpret the BFPRT as a de-randomization?)

Anyway, slightly modified my point still stands: BFPRT is way more complicated (and harder to come up with) than randomized QuickSelect.