Probabilistic analysis of optimal multi-pivot QuickSort
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913074083004416 |
|---|---|
| author | Holmgren, Cecilia Ischebeck, Jasper Krenn, Daniel Lesny, Florian Neininger, Ralph |
| author_facet | Holmgren, Cecilia Ischebeck, Jasper Krenn, Daniel Lesny, Florian Neininger, Ralph |
| contents | We consider a multi-pivot QuickSort algorithm using $K\in\mathbb{N}$ pivot elements to partition a nonsorted list into $K+1$ sublists in order to proceed recursively on these sublists. For the partitioning stage, various strategies are in use. We focus on the strategy that minimizes the expected number of key comparisons in the standard random model, where the list is given as a uniformly permuted list of distinct elements. We derive asymptotic expansions for the expectation and variance of the number of key comparisons as well as a limit law for all $K\in\mathbb{N}$, where the convergence holds for all (exponential) moments. For $K\le 4$ we also bound the rate of convergence within the Wasserstein and Kolmogorov--Smirnov distance. Our analysis of the expectation is based on classical results for random $m$-ary search trees. For the remaining results, combinatorial considerations are used to make the contraction method applicable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_22334 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Probabilistic analysis of optimal multi-pivot QuickSort Holmgren, Cecilia Ischebeck, Jasper Krenn, Daniel Lesny, Florian Neininger, Ralph Probability We consider a multi-pivot QuickSort algorithm using $K\in\mathbb{N}$ pivot elements to partition a nonsorted list into $K+1$ sublists in order to proceed recursively on these sublists. For the partitioning stage, various strategies are in use. We focus on the strategy that minimizes the expected number of key comparisons in the standard random model, where the list is given as a uniformly permuted list of distinct elements. We derive asymptotic expansions for the expectation and variance of the number of key comparisons as well as a limit law for all $K\in\mathbb{N}$, where the convergence holds for all (exponential) moments. For $K\le 4$ we also bound the rate of convergence within the Wasserstein and Kolmogorov--Smirnov distance. Our analysis of the expectation is based on classical results for random $m$-ary search trees. For the remaining results, combinatorial considerations are used to make the contraction method applicable. |
| title | Probabilistic analysis of optimal multi-pivot QuickSort |
| topic | Probability |
| url | https://arxiv.org/abs/2503.22334 |