Quickselect (original) (raw)

En algorithmique, quickselect est un algorithme de sélection qui retourne le ke plus petit élément dans une liste non ordonnée. Comme l'algorithme de tri quicksort, il a été créé par Tony Hoare et il est donc aussi connu comme l' algorithme de sélection de Hoare. Tout comme quicksort, l'algorithme quickselect est en général implémenté en place, et en plus de sélectionner le ke élément, il trie une partie des données. Comme quicksort, il est efficace en pratique avec un temps moyen de . Quickselect et ses variantes sont des algorithmes souvent utilisés dans le monde réel.