4 ms·

Note that properly implemented quicksort has expected O(n log n) time independent of the data (dependent only on the random choices of pivots), whereas interpol

Note that properly implemented quicksort has expected O(n log n) time independent of the data (dependent only on the random choices of pivots), whereas interpolation sort's performance is data dependent. That's a pretty important distinction.

pbiggar 16y ago
Interestingly, that's not quite true: see http://www.scss.tcd.ie/~pbiggar/jea-2008.pdf http://www.scss.tcd.ie/~pbiggar/jea-2008.pdf, section 8.3. I'll point out too that no quicksort implementation uses a truly random choice of pivot. Typically they use the median of three pivots to be pseudo-random.
- lliiffee 16y ago
  Your second point may be valid, though not literally. I've implemented quicksort, and I used (pseudo) random pivots, damnit! :) The article you point to doesn't seem to address the complexity of quicksort with random pivots. However, that is proven to be expected O(n log n) time for any data in Motwani's Randomized Algorithms book, and I don't think the correctness of that has ever been questioned.
  - pbiggar 16y ago
    > The article you point to doesn't seem to address the complexity of quicksort with random pivots. That paper is about experimental algorithmics, and avoids discussions of things which aren't practical (such as using truly random pivots). > However, that is proven to be expected O(n log n) time for any data in Motwani's Randomized Algorithms book, and I don't think the correctness of that has ever been questioned. Right, but since there are no truly random quicksorts, its hardly a concern.
    - lliiffee 16y ago
      Please clarify: Why are random pivots not practical? And why do you say there are no truly random quicksorts? Because pseudorandom numbers aren't really random, or for some other reason?
      - pbiggar 16y ago
        > Why are random pivots not practical? The cost of true randomness is really high (in execution time) > And why do you say there are no truly random quicksorts? Because pseudo-random numbers aren't really random. The only reason this is important is that the pseudo-randomness means that its possible the construct an adversarial input, which could drive the quicksort to take N^2 time.

pbiggar 16y ago

Interestingly, that's not quite true: see http://www.scss.tcd.ie/~pbiggar/jea-2008.pdf http://www.scss.tcd.ie/~pbiggar/jea-2008.pdf, section 8.3. I'll point out too that no quicksort implementation uses a truly random choice of pivot. Typically they use the median of three pivots to be pseudo-random.

lliiffee 16y ago
Your second point may be valid, though not literally. I've implemented quicksort, and I used (pseudo) random pivots, damnit! :) The article you point to doesn't seem to address the complexity of quicksort with random pivots. However, that is proven to be expected O(n log n) time for any data in Motwani's Randomized Algorithms book, and I don't think the correctness of that has ever been questioned.
- pbiggar 16y ago
  > The article you point to doesn't seem to address the complexity of quicksort with random pivots. That paper is about experimental algorithmics, and avoids discussions of things which aren't practical (such as using truly random pivots). > However, that is proven to be expected O(n log n) time for any data in Motwani's Randomized Algorithms book, and I don't think the correctness of that has ever been questioned. Right, but since there are no truly random quicksorts, its hardly a concern.
  - lliiffee 16y ago
    Please clarify: Why are random pivots not practical? And why do you say there are no truly random quicksorts? Because pseudorandom numbers aren't really random, or for some other reason?
    - pbiggar 16y ago
      > Why are random pivots not practical? The cost of true randomness is really high (in execution time) > And why do you say there are no truly random quicksorts? Because pseudo-random numbers aren't really random. The only reason this is important is that the pseudo-randomness means that its possible the construct an adversarial input, which could drive the quicksort to take N^2 time.