Partial Quicksort and Quickpartitionsort - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2010

Partial Quicksort and Quickpartitionsort

Résumé

Partial Quicksort sorts the $l$ smallest elements in a list of length $n$. We provide a complete running time analysis for this combination of Find and Quicksort. Further we give some optimal adapted versions, called Partition Quicksort, with an asymptotic running time $c_1l\ln l+c_2l+n+o(n)$. The constant $c_1$ can be as small as the information theoretic lower bound $\log_2 e$.
Fichier principal
Vignette du fichier
dmAM0135.pdf (236.99 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01185579 , version 1 (20-08-2015)

Identifiants

Citer

Conrado Martínez, Uwe Rösler. Partial Quicksort and Quickpartitionsort. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.505-512, ⟨10.46298/dmtcs.2781⟩. ⟨hal-01185579⟩

Collections

TDS-MACS
163 Consultations
1386 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More