2
$\begingroup$

Assume we want to use quicksort on some array $s$ with length $n$ consisting of only $n$ distinct elements. Let $S_{(1)},S_{(2)},\dots,S_{(n)}$ be the sorted order of the elements in $S$. Furthermore, let $d(i)$ be the number of elements that $S_{(i)}$ is compared to. Finally, the pivot element is chosen uniformly at random.

How do I then compute the probability that $d(i) < k$ for some $k \in \mathbb{N}$?

$\endgroup$
1
  • 1
    $\begingroup$ The question in the title is different from the question in the body. Are you interested in counting how may comparisons involve $S_{(i)}$? How many pivots are compared to $S_{(i)}$? How many elements is $S_{(i)}$ compared to as a pivot? $\endgroup$ May 16 at 18:56
1
$\begingroup$

This is not the answer to your question, but maybe you can use some elements of it.

For $i<j$, let us denote $X_{ij}$ the random variable: $$X_{ij} = \left\{\begin{array}{rl}1 & \text{if }S_{(i)}\text{ and }S_{(j)}\text{ are compared}\\0&\text{otherwise}\end{array}\right.$$ and $A_{ij} = \{S_{(i)}, S_{(i+1)}, …, S_{(j)}\}$.

Since a comparison between two elements only occurs if one of them is a pivot, and since a pivot is never compared to other elements after the end of the partition occurring when it was chosen, we can conclude that:

$$\mathbb{P}(X_{ij} = 1) = \mathbb{P}(S_{(i)} \text{ first pivot in }A_{ij}) + \mathbb{P}(S_{(j)} \text{ first pivot in }A_{ij})$$ This is also due to the fact that if another element of $A_{ij}$ is chosen as first pivot, $S_{(i)}$ and $S_{(j)}$ will be put in two different parts of the partition.

Since the choice of the pivot is uniform, we get $\mathbb{P}(S_{(i)} \text{ first pivot in }A_{ij}) = \frac{1}{|A_{ij}|}$ and finaly $\mathbb{P}(X_{ij} = 1) = \frac{2}{j - i +1}$.

Now, the expected number of comparisons where $S_{(i)}$ is involved is:

$$\begin{array}{rcl} \displaystyle\mathbb{E}\left(\sum\limits_{j=1,j\neq i}^nX_{ij}\right) & = & \displaystyle\sum\limits_{j=1,j\neq i}^n\mathbb{E}(X_{ij})\\ & = & \displaystyle\sum\limits_{j=1,j\neq i}^n\mathbb{P}(X_{ij} = 1)\\ & = & \displaystyle\sum\limits_{j=1,j\neq i}^n\frac{2}{|j-i| + 1}\\ & = & \displaystyle\sum\limits_{j=1}^{i-1}\frac{2}{i - j +1} + \sum\limits_{j=i+1}^{n}\frac{2}{j - i +1}\\ & = & \displaystyle\sum\limits_{k=1}^{i-1}\frac{2}{k +1} + \sum\limits_{k=1}^{n-i}\frac{2}{k +1}\\ \end{array}$$

This analysis is generally sufficient for the analysis of the average time complexity of quicksort, because this value is $O(\log n)$. However, I am not sure as to how use part of it to find the value you want, which is: $$\displaystyle\mathbb{P}\left(\sum\limits_{j = 1, j\neq i}^n X_{ij} = k\right)$$

Also it is not so clear that for $j\neq j'$, $X_{ij}$ and $X_{ij'}$ are independant (since for example $X_{ij}$, $X_{ij'}$ and $X_{jj'}$ are not independant because at most two of the three could be $1$).

$\endgroup$
1
$\begingroup$

We can describe quicksort with a random pivot as follows. Assume for simplicity that $S_{(i)} = i$. First, choose a permutation of $\{1,\ldots,n\}$. Then, whenever processing some subarray, choose the element that appears first in the permutation as the pivot.

Suppose we are interested in the number of elements compared to $i$. Suppose that $i$ is found at location $j$. Suppose that when $i$ is chosen as a pivot, it is compared to $k_-$ elements smaller than itself and $k_+$ elements larger than itself. These elements must be $i-k_-,\ldots,i-k_+$, and the elements $i-k_--1,i+k_++1$, if they are in range, must appear before $i$. Let $b_-,b_+$ be the indicators of these elements being in range (i.e., $b_- = 1$ if $k_- < i-1$, and $b_+ = 1$ if $k_+ < n-i$).

Suppose that $j_-$ of the elements preceding $i$ are smaller than $i$, forming a set $S_-$, and so $j_+ = j - 1 - j_-$ of the elements preceding $i$ are larger than $i$, forming a set $S_+$. There are $\binom{i-1-k_--b_-}{j_--b_-}$ choices for $S_-$ and $\binom{n-i-k_+-b_+}{j_+-b_+}$ choices for $S_+$. There are $\binom{j_++j_-}{j_+}$ ways of putting them together, and $(n-j)!$ ways to choose the order of the remaining elements.

The number of permutations of $S_-$ with $\ell_-$ left-to-right maxima is the Stirling number of the first kind $\genfrac{\lbrack}{\rbrack}01{j_-}{\ell_-}$. Similarly, the number of permutations of $S_+$ with $\ell_+$ left-to-right minima is $\genfrac{\lbrack}{\rbrack}01{j_+}{\ell_+}$.

We obtain the following formula for the probability that $i$ is compared to exactly $s$ elements: $$ \frac{1}{n!} \sum_{j_++j_- \leq n-1} \sum_{\substack{k_++k_-+\ell_++\ell_-=s \\ k_- \leq i-1 \\ k_+ \leq n-i}} \\ \binom{j_++j_-}{j_+} \binom{i-1-k_--b_-}{j_--b_-} \binom{n-i-k_+-b_+}{j_+-b_+} \\ (n-j_+-j_--1)! \genfrac{\lbrack}{\rbrack}00{j_-}{\ell_-} \genfrac{\lbrack}{\rbrack}00{j_+}{\ell_+}. $$

$\endgroup$

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.