Tri rapide (Quick sort)
Description
Bonjour à tous,
Soit une liste de réels (mais peut s'appliquer à plusieurs objets mathématiques obéissant
une loi d'ordre) à trier par ordre croissant avec l’algorithme du tri rapide
(connu aussi sous le le nom de Quick sort ou qsort) :
1) On prend comme pivot (p) le premier élément de la liste (par exemple).
2) On constitue 2 listes (g) à gauche et (d) à droite du pivot p où g ne contient que
les éléments inférieurs à p et où d contient les éléments supérieurs à p
3) Récursivement, on applique le même algorithme aux listes [g]+[p]+[d] jusqu'à
obtention de la liste triée finale.
Ce programme est court et simple à comprendre (plus pédagogique) mais d'autres variantes
plus longues et mieux optimisées existent :
notamment la fonction native « sorted » de Python.
Cordialement,
hb
Soit une liste de réels (mais peut s'appliquer à plusieurs objets mathématiques obéissant
une loi d'ordre) à trier par ordre croissant avec l’algorithme du tri rapide
(connu aussi sous le le nom de Quick sort ou qsort) :
1) On prend comme pivot (p) le premier élément de la liste (par exemple).
2) On constitue 2 listes (g) à gauche et (d) à droite du pivot p où g ne contient que
les éléments inférieurs à p et où d contient les éléments supérieurs à p
3) Récursivement, on applique le même algorithme aux listes [g]+[p]+[d] jusqu'à
obtention de la liste triée finale.
Ce programme est court et simple à comprendre (plus pédagogique) mais d'autres variantes
plus longues et mieux optimisées existent :
notamment la fonction native « sorted » de Python.
Cordialement,
hb