So we have this block of pseudocode:

Monsters = [M1,M2,M3,M4,M5,M6,M7,M8];

qsort() sorts the array via quicksort where we use the last element as pivot. To compare two elements it uses rand_compare, which, with equal probability (i.e., 1/2 either way), will return either "1. element is bigger" or "2. element is bigger" and never "both are equal". What is the probability that M8 appears in position 0, 1 or 2, respectively, after applying qsort ?

I'm really not sure how to tackle this question. Intuitively it should be 1/8 for every position. Does it depend on what implementation of quicksort you use?

  • $\begingroup$ Do you know how quicksort works? This is really instrumental to answering this question. $\endgroup$ – Yuval Filmus May 22 '19 at 9:10
  • $\begingroup$ Yes I do! altough it's my first cs lecture, so I'm still kind of "learning how to swim" $\endgroup$ – Christian Singer May 22 '19 at 9:12

In quick sort, after a partition, you have placed every element smaller than your pivot p below p and every element larger than p above it. Therefore after a partition you know the pivot is in the correct position and therefore it will not be moved again. Since you choose the last element (M8) as your pivot, this simplifies the process, since you only have to go through one iteration.

When you compare each element to M8, you will randomly be told that M8 is greater or the other element is "greater" each with 1/2 odds, and if the other element is "greater" it will be placed to the right of M8. Therefore, for M8 to end up in position 0, 1, or 2 it will have to have 2 or less elements that are determined to be "smaller" than M8. We can determine this probability through a geometric sequence:

0: (0.5^7)(0.5^0)(C(7,7)) = (0.5^7)(1) = .0078125

1: (0.5^6)(0.5^1)(C(7,6)) = (0.5^7)(7) = .0546875

2: (0.5^5)(0.5^2)(C(7,5)) = (0.5^7)(21) = .1640625


Let us first recall how quicksort works. We start by choosing a pivot — in your case $M_8$. We then partition the array into elements smaller than the pivot and larger than the pivot (breaking ties arbitrarily), and reorder the array in the following way:

elements smaller than the pivot; the pivot; elements larger than the pivot

We then recursively sort the elements smaller than the pivot, and the elements larger than the pivot.

The location of the pivot is the same as the number of elements smaller than the pivot. In your case, each of the elements $M_1,\ldots,M_7$ is smaller than the pivot $M_8$ with probability $1/2$.

You take it from here.


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.