4 ms·

Strictly speaking, it is not true that shuffling first avoids the worst case. Given a deterministic shuffling function, some permutation of input needs to shuff

by ruggeri 12y ago

Strictly speaking, it is not true that shuffling first avoids the worst case. Given a deterministic shuffling function, some permutation of input needs to shuffle to sorted order, which will again trigger the worst case. Of course, shuffling is still potentially helpful because ascending/descending order is often common in many applications.

mtdewcmu 12y ago
You're right that shuffling doesn't avoid the worst case, but your explanation isn't quite correct. See my other comment for my explanation. I'm not sure what you mean by deterministic shuffling. Shuffling is supposed to be random, and therefore non-deterministic. In practice, you'd probably use a pseudorandom function to implement shuffling, but the goal of pseudorandom functions is to be indistinguishable from random functions, so that detail shouldn't matter.
brudgers 12y ago
Randomization of the pivots produces O(n log n) average running time with a very low probability of any other running time for any value of n where the worst case running time matters.
- ruggeri 12y ago
  Even without randomization of pivots expected run time is O(n log n). If the order of the input data is random, I don't believe randomizing pivots changes the distribution of running times. What changes is that one very common permutation of data (ascending data) does not have O(n * 2) performance.
  - brudgers 12y ago
    There's little justification for expecting data to behave randomly unless our algorithm introduces it.
    - mtdewcmu 12y ago
      Correct. In general, real data will seldom, if ever, look like random data.
shanusmagnus 12y ago
Shuffling with a too-small seed size will render the shuffle susceptible to brute force attacks; but in no way invalidates its use as a dodge for pathological (pre-sorted) arrays submitted to Quicksort in the course of normal usage. There's a better chance of getting eaten by a dinosaur than finding O(N^2) QS performance on shuffled data that comes from anything other than an attacking adversary.

by ruggeri 12y ago

mtdewcmu 12y ago

You're right that shuffling doesn't avoid the worst case, but your explanation isn't quite correct. See my other comment for my explanation. I'm not sure what you mean by deterministic shuffling. Shuffling is supposed to be random, and therefore non-deterministic. In practice, you'd probably use a pseudorandom function to implement shuffling, but the goal of pseudorandom functions is to be indistinguishable from random functions, so that detail shouldn't matter.

brudgers 12y ago

Randomization of the pivots produces O(n log n) average running time with a very low probability of any other running time for any value of n where the worst case running time matters.

ruggeri 12y ago
Even without randomization of pivots expected run time is O(n log n). If the order of the input data is random, I don't believe randomizing pivots changes the distribution of running times. What changes is that one very common permutation of data (ascending data) does not have O(n * 2) performance.
- brudgers 12y ago
  There's little justification for expecting data to behave randomly unless our algorithm introduces it.
  - mtdewcmu 12y ago
    Correct. In general, real data will seldom, if ever, look like random data.

shanusmagnus 12y ago

Shuffling with a too-small seed size will render the shuffle susceptible to brute force attacks; but in no way invalidates its use as a dodge for pathological (pre-sorted) arrays submitted to Quicksort in the course of normal usage. There's a better chance of getting eaten by a dinosaur than finding O(N^2) QS performance on shuffled data that comes from anything other than an attacking adversary.