5 ms·

> 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 nitpi

by gms7777 13y ago

> 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.

lifebeyondfife 13y ago
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.
- gms7777 13y ago
  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.
  - lifebeyondfife 13y ago
    I see what you mean. Thanks for taking the time out to nitpick.
  - eru 13y ago
    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.
  - tubbzor 13y ago
    >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.
gphilip 13y ago
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_pivoting https://en.wikipedia.org/wiki/Quicksort#Selection-based_pivo...
- ggchappell 13y ago
  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 https://en.wikipedia.org/wiki/Introsort
  - eru 13y ago
    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'.
    - ggchappell 13y ago

by gms7777 13y ago

lifebeyondfife 13y ago

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.

gms7777 13y ago
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.
- lifebeyondfife 13y ago
  I see what you mean. Thanks for taking the time out to nitpick.
- eru 13y ago
  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.
- tubbzor 13y ago
  >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.

gphilip 13y ago

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_pivoting https://en.wikipedia.org/wiki/Quicksort#Selection-based_pivo...

ggchappell 13y ago
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 https://en.wikipedia.org/wiki/Introsort
- eru 13y ago
  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'.
  - ggchappell 13y ago