Voltar
Artigo Acesso aberto Revisado por pares
BIBTEX RIS

Exploiting partial order with Quicksort

1984; Wiley; Volume: 14; Issue: 6 Linguagem: Inglês

10.1002/spe.4380140603

ISSN

1097-024X

Autores

R. Geoff Dromey,

Tópico(s)

DNA and Biological Computing

Resumo

Abstract The widely known Quicksort algorithm does not attempt to actively take advantage of partial order in sorting data. A simple change can be made to the Quicksort strategy to give a bestcase performance of n , for ordered data, with a smooth transition to O(n log n) for random data. This algorithm (Transort) matches the performance of Sedgewick's claimed best implementation of Quicksort for random data.

Referência(s)