IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
logo
Sommaire > Algorithmes généraux > Tris
        Quels sont les algorithmes de tris usuels et leur complexité?
        Pseudo-code du tri "rapide" (quick sort)
        Pseudo-code du tri "fusion" (merge sort)

rechercher
precedent    sommaire    suivant


Quels sont les algorithmes de tris usuels et leur complexité?
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 ?


Pseudo-code du tri "rapide" (quick sort)
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


Pseudo-code du tri "fusion" (merge sort)
auteur : Rodriguez Eric
TODO


rechercher
precedent    sommaire    suivant

Consultez les autres F.A.Q's

Valid XHTML 1.1!Valid CSS!


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.