Geodesic
Partial Quicksort and Quickpartitionsort
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (2010).

Voir la notice de l'article provenant de la source Episciences

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$. 
@article{DMTCS_2010_special_258_a17,
     author = {Mart{\'\i}nez, Conrado and R\"osler, Uwe},
     title = {Partial {Quicksort} and {Quickpartitionsort}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)},
     year = {2010},
     doi = {10.46298/dmtcs.2781},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2781/}
}
TY  - JOUR
AU  - Martínez, Conrado
AU  - Rösler, Uwe
TI  - Partial Quicksort and Quickpartitionsort
JO  - Discrete mathematics & theoretical computer science
PY  - 2010
VL  - DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2781/
DO  - 10.46298/dmtcs.2781
LA  - en
ID  - DMTCS_2010_special_258_a17
ER  - 
%0 Journal Article
%A Martínez, Conrado
%A Rösler, Uwe
%T Partial Quicksort and Quickpartitionsort
%J Discrete mathematics & theoretical computer science
%D 2010
%V DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2781/
%R 10.46298/dmtcs.2781
%G en
%F DMTCS_2010_special_258_a17
Martínez, Conrado; Rösler, Uwe. Partial Quicksort and Quickpartitionsort. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (2010). doi : 10.46298/dmtcs.2781. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2781/

Cité par Sources :