4
$\begingroup$

Cormen talks briefly about the advantages of picking a random pivot in quicksort. However as pointed out here(4th to the last paragraph):

Using a random number generator to choose the positions is relatively expensive

So how is picking a random pivot actually implemented in practice, and how random is it? It can't be too expensive, since from what I understand one of quicksort's main advantages over other $\cal{O}(n \lg n)$ sorts is the small constant factors, and spending allot of cycles picking pivots would undermine that advantage.

EDIT

As an example, the C code from "Three Beautiful Quicksorts" actually calls the C library rand function:

int randint(int l, int u) {
    return rand()%(u-l+1)+l;
}

void quicksort(int l, int u) {
    int i, m;
    if (l >= u) return;
    swap(l, randint(l, u));
    m = l;
    for (i = l+1; i <= u; i++)
        if (x[i] < x[l])
            swap(++m, i);
    swap(l, m);
    quicksort(l, m-1);
    quicksort(m+1, u);
}

While the pivot picking code here is clearly $\cal{O}(1)$, it would seem that the hidden $c$ here is relatively high.

$\endgroup$
  • $\begingroup$ It's not expensive. It is certainly $O(1)$. And you don't need any fancy kind of randomness. The regular multiply, add, divide is fine. Though apparently the authors of that text thought it's too expensive. It's not something you need to worry much about, though. $\endgroup$ – Karolis Juodelė Apr 18 '13 at 18:22
  • 1
    $\begingroup$ @KarolisJuodelė Actually, if you want to map the random element over all indices the of input list, you must calculate at least $O(\log n)$ time to simply read the index. And you need $n$ of those pivots, so that's $O(n \log n)$ just generating the necessary bits. But, of course, RAM model et cetera, et cetera, et cetera ... $\endgroup$ – Pål GD Apr 18 '13 at 18:27
4
$\begingroup$

Take a look at McIllroy and Douglas' "A Killer Adversary for Quicksort" (Software -- Practice and Experience 29(4): 341-344 (1999)) or Crosby and Wallach's "Denial of Service via Algorithmic Complexity Attacks" for the reason behind randomizing. Quicksort behaves very badly if you pick (nearly) the largest/smallest as pivot each time. For randomization to make sense, it has to be random (if I know how you pick pivots deterministically, I can cook up an array that forces you to go into $O(n^2)$ behaviour, see the paper mentioned for details). But a fancy RNG is costlier than, say, taking 3 or another smallish odd number of elements, and pick the median of those as pivot, which is another way to counteract bad behaviour. So if you choose randomization, use a fast RNG seeded appropiately (probably a linear congruential scheme will be enough).

Algorithms can (and should) be compared by $O(\cdot)$, but if you are talking about different implementations of the same algorithm one must switch to more detailed analysis. In fact, Sedgewick and Flajolet in "An introduction to the analysis of algorithms" argue that one shouldn't use $T(n) = O(f(n))$ at all, but should strive to get $T(n) \sim f(n)$ type asymptotics.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So the real main reason for "randomizing" the pivot choice is more a security reason than a asymptotics reason? $\endgroup$ – Robert S. Barnes Apr 19 '13 at 5:25
  • $\begingroup$ @RobertS.Barnes No, the main reason is the expected running time. $\endgroup$ – Pål GD Apr 19 '13 at 7:11
  • $\begingroup$ A linear congruential generator will not be enough. paper. $\endgroup$ – adrianN Apr 19 '13 at 8:10
  • 1
    $\begingroup$ this theory is based on an "adversary" that attempts to cause an algorithmic slowdown via internal knowledge of the algorithm. so its applicable more in cryptography and not so much general algorithmic complexity where "pathological" cases of sort orders appearing at random are basically negligible. $\endgroup$ – vzn Apr 20 '13 at 18:45
  • $\begingroup$ @PålGD What do you make of Bentley's results which show a deterministic choice of pivot significantly outperforming a randomized one? $\endgroup$ – Robert S. Barnes Apr 22 '13 at 9:30
1
$\begingroup$

So after taking the time to sit down and actually watch Bentley's google lecture, Three Beautiful Quicksorts, it turns out that randomized pivot's are not faster than other methods. Specifically, according to Bently - who with McIlroy - rewrote the standard C library qsort function, we have the following from their paper, Engineering a Sort Function:

  • $1.386\;\cdot n \lg n$ average comparisons using first, middle or a randomized pivot
  • $1.188\;\cdot n \lg n$ average comparisons using a median of 3 pivot
  • $1.094\;\cdot n \lg n$ average comparisons using a median of 3 medians pivot

According to the above paper:

Our final code therefore chooses the middle element of smaller arrays, the median of the first, middle and last elements of a mid-sized array, and the pseudo-median of nine evenly spaced elements of a large array.

I read the following in Data Structures Using C, by Tenenbaum, Langsam and Augenstein:

It is possible to speed up quicksort for sorted files by choosing a random element of each subfile as the pivot value. If a file is known to be nearly sorted, this might be a good strategy ( although, in that case choosing the middle element as a pivot would be even better ). However, if nothing is known about the file, such a strategy does not improve the worst case behaviour, since it is possible (although improbably) that the random element chosen each time might consistently be the smallest element of each subfile. As a practical matter, sorted files are more common than a good random number generator happening to choose the smallest element repeatedly.

In their book they use the Hoare partition scheme. Further down they say:

It can be shown, however, that on the average (over all files of size $n$), the quicksort makes approximately $1.386 n \lg n$ comparisons even in its unmodified version.

He's referring here to picking the first element as the pivot.

EDIT

I think I just stumbled on the answer to how a deterministic selection of pivot outperforms a randomized one.

Question 9.3-3 in Cormen is, "Show how quicksort can be made to run in $O(n \lg n)$ time in the worst case."

The answer is to use deterministic selection to select the median element each time. Since deterministic selection runs in $O(n)$ time worst case, you get the worst case recursion $$T(n)=2T(n/2)+Θ(n)=Θ(n \lg n)$$ for this deterministic quicksort, admittedly with a large hidden constant factor in there.

I think that what Bentely is doing is an extension of this idea using a pseudo median. Bentely's paper references another paper which quantifies the quality of these pseudo medians.

The cost of computing the pseudo median is $\Theta(1)$ whereas finding the real median is $O(n)$. This is probably a big part of where his very small constant factor comes from. I assume that the paper Bentely references proves somehow that the pseudo median is "good enough" to guarantee a high enough percentage of good splits by the partition function to give the above run times.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But this is average complexity and not worst time complexity, right? $\endgroup$ – Pål GD Apr 22 '13 at 11:30
  • 1
    $\begingroup$ @PålGD Yes, but we're always talking about average case when it comes to quicksort. And as I suspected, and Tenenbaum confirms, picking a random pivot doesn't eliminate quicksort's worstcase behaviour and in fact the randomized quicksort performs no better on average than the one which picks the first element as it's pivot. That's also what Bentley said above. $\endgroup$ – Robert S. Barnes Apr 23 '13 at 6:28
  • 2
    $\begingroup$ No, we are not always talking about average case complexity with quicksort. Expected running time is over the randomness of the algorithm, but is worst case over inputs. Average case complexity assumes inputs come from a distribution. This is a big assumption: often your arrays will have structure, which means they're nothing like random. On the other hand there are no bad inputs for randomized quick sort - just bad randomness, but that is much more unlikely than a bad file if you have a reasonable PRG $\endgroup$ – Sasho Nikolov Apr 23 '13 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.