| auteur : Rodriguez Eric |
- Tri rapide (quick sort): O(n^2)
- Tri fusion (merge sort): O(n^2)
- Tri "tas" (heap sort): TODO
- Tri "sélection": TODO
- Tri "insertion": TODO
- Tri "radix": O(1) TODO
Autres ?
|
| auteur : Rodriguez Eric |
Le tri "rapide" utilise une stratégie de "divide and conquer" pour trier une liste d'éléments
valeurs[] en procédant de la façon suivante:
- Choix du pivot: on choisit un élément de la liste valeurs[]. Cet élément sera appelé "pivot"
- Partionnement: il faut réordonner les éléments de la liste de sort que les éléments plus petits que la valeur pivot se trouvent avant lui, et les éléments
plus grand que la valeur pivot se trouvent après lui. Les éléments égaux à la valeur pivot
peuvent être déplacés avant ou après celui-ci. Après cette opération, le pivot se trouve
dans sa position finale
- Appels récursifs: on trie de la même façon les sous-listes des élements plus petits
(valeurs_inf[]) et plus grands (valeurs_sup[]) que le pivot.
tri_rapide(valeurs[])
var valeurs_inf[]
var valeurs_sup[]
var valeurs_pivots[]
IF longueur(valeurs[]) <= 1 THEN
RETURN valeurs[]
ELSE
pivot <- une valeur du tableau valeurs[]
FOREACH val IN valeurs[] (à l'exception du pivot)
IF val < pivot THEN valeurs_inf[] <- val END IF
IF val >= pivot THEN valeurs_sup[] <- val END IF
END FOREACH
valeurs_pivots[] <- pivot
RETURN tri_rapide(valeurs_inf[]) & valeurs_pivots[] & tri_rapide(valeurs_sup[])
END IF |
|
Consultez les autres F.A.Q's
|
Les sources présentées sur cette page sont libres de droits
et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation
constitue une œuvre intellectuelle protégée par les droits d'auteur.
Copyright © 2005 Developpez LLC.
Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne
peut être faite de ce site ni de l'ensemble de son contenu : textes, documents
et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez
selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.