New answers tagged


You have misunderstood the analysis of randomized quicksort. The idea is that we can view pivot selection in randomized quicksort in the following way. We first select a permutation $\pi$ on the elements on the array. When choosing a pivot among some subarray $B$, we choose the element of $B$ which appears first in $\pi$. Suppose that $i < j$. We are ...


Yes. This is exactly what a selection algorithm does. It can be done in linear time.


The conceptually simplest way is to simply use the same algorithm recursively to sort the sub arrays; hence why it's labeled as recursion. As long as the base cases for very small arrays are correctly defined, this will yield a correct result. As an example, let's Quicksort some alphabet, using first symbol as pivot: sort(FHDEBACG) -> sort(DEBAC) F sort(...


Splitting the list entails comparing every element in the current list with the pivot. That is, if the list is of size $n$, you would have $n-1$ comparisons. Then, the list is split into sizes $|B|$ and $|S|$ and continues recursively. On the $B$ part you will choose a pivot and make $|B|-1$ comparisons to split them into two (sub)lists. Same with $S$. This ...

Top 50 recent answers are included