Partial Quicksort and weighted branching processes

Ragab, Mahmoud

In this dissertation we look at dierent two models of sorting algorithms based on divideand-conquer algorithms. Quicksort algorithm, sort an unsorted array of n distinct elements. Partial Quicksort sorts the l smallest elements in a list of length n. Both stochastic divide-and-conquer algorithms are widely studied. Our algorithm Quicksort on the y provides online the rst smallest, then second smallest and so on. If we stop at the l-th smallest, we obtain Partial Quicksort. We analyze the running time performance Yn of Quicksort on the y using the parameter l as time index. We show that, the process Yn converges not only in distribution, but also uniformly almost everywhere in D to a random variable Y . The distribution of y is characterized as a solution of a stochastic xed point equation with values in the space D of cadlag functions on the unit interval. This result includes the performance of Quicksort via l = n, respectively Y (1) in the limit.


Citation style:

Ragab, Mahmoud: Partial Quicksort and weighted branching processes. 2011.


Use and reproduction:
No CC License (german copyright law applies)