Les programmes de tri

Les différents programmes de tri




















I- Le programme de tri

Voici le programme de tri que nous avons créé :
  • Premièrement nous avons créer une fonction nous permettant de nous donner le plus petit élément de la liste



  • Ensuite nous avons défini une fonction nous permettant de retirer des éléments d'une liste

  • Enfin nous avons combiner ces deux fonctions afin de créer notre programme de tri
  • Voici le programme complet :
  • Pour conclure ce programme créé une liste vide puis nous donne le plus petit élément de la liste à trier et envoi cette élément dans la nouvelle liste vide créé précédemment puis supprime cet élément de la liste à trier. A la fin le programme nous rend la nouvelle liste triée.


    II- Le programme de tri à bulle

    Le principe du tri à bulles est de comparer deux valeurs et d'inverser leur position si elles sont mal placées. Si un premier nombre (x) est plus grand qu'un deuxième nombre (y) et que l'on souhaite trier l'ensemble par ordre croissant, alors (x) et (y) sont mal placés et il faut les inverser.
    Si, au contraire, x est plus petit que y, alors on ne fait rien et l'on compare (y) à (z), l'élément suivant.
    Et on parcourt ainsi la liste jusqu'à ce qu'on ait réalisé n-1 passages (n représentant le nombre de valeurs à trier) ou jusqu'à ce qu'il n'y ait plus rien à inverser lors du dernier passage.
    A la fin du premier passage, on place le plus grand élément de la liste au bout du tableau, au bon emplacement. Pour le passage suivant, nous ne sommes donc plus obligés de faire une comparaison avec le dernière élément. Donc à chaque passage, le nombre de valeurs à comparer diminue de 1.

  • Voici le programme de tri à bulles :
  • III - La fonction intégrée de Python

    La fonction intégrée de Python sorted(liste) est la fonction qui permet de trier une liste.

    IV - Tri cartes

    Ce TriCartes est un tri simulant un jeu de cartes ou lorsqu'on donne une carte au joueur une par une, celui-ci les range dans sa main par ordre croissant .
    Le tri carte va faire pareil, une liste de nombre lui ai donné et par tri il va comparé les « cartes » une par une et les classer. Par exemple, tout d'abord on initialise un rang 0.
    On prend la carte suivante, le premier élément de la liste (à partir du rang 0).
    Si celui-ci est supérieur au rang 0, dans ce cas, les « cartes » restent dans le même ordre. Mais si il est inférieur, alors il « sort » de la liste ( comme lorsque l'on enlève notre carte des mains pour la placer au bon endroit) et les éléments se décalent, la carte se place au début de la liste, au rang 0.
    Et ainsi de suite, le deuxième élément sera comparé au premier (C-1) si il est inférieur il change de place, et si il est aussi inférieur à l'élément du rang 0, il prend sa place, et les éléments se décalent : le rang 0 devient le premier et le premier devient le deuxième…
    Si il est supérieur il ne bouge pas et on passe à la carte suivante.



    V - Comparaison d'efficacité

    La fonction tri que nous avons créé à mis 6,3 secondes pour trier une liste de 1000 éléments.
    La fonction Tri à bulle à mis 5,5 secondes à trier cette même liste.
    Ensuite la fonction intégrée de Python à mis 4,3 secondes pour trier cette liste.
    Enfin le fonction tri cartes à mis 5.7 secondes pour trier cette même liste.
    En conclusion nous pouvons dire que c'est la fonction intégré de Python qui est la méthode la plus efficace pour trier une liste.




    Joyeux Noël !




    Retour en haut de page