Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Importer

Bienvenue sur Scribd !

  • 128 vues

    Les Types de Tri

    Transféré par

    Nour Elhouda

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme RTF, PDF, TXT ou lisez en ligne sur Scribd

    Les Types de Tri

    Transféré par

    Nour Elhouda
    128 vues1 page

    Copyright

    © © All Rights Reserved

    Formats disponibles

    RTF, PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme RTF, PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format rtf, pdf ou txt
    128 vues1 page

    Les Types de Tri

    Transféré par

    Nour Elhouda

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme RTF, PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format rtf, pdf ou txt
    Vous êtes sur la page 1sur 1

    Tri par insertion:

    Le tri par insertion fonctionne en insérant l’ensemble de valeurs dans le fichier trié existant.

    Il construit le tableau trié en insérant un seul élément à la fois. Ce processus se poursuit jusqu’à ce que le
    tableau entier soit trié dans un certain ordre. Le concept principal du tri par insertion consiste à insérer
    chaque élément à l’endroit approprié dans la liste finale. La méthode de tri par insertion permet
    d’économiser une quantité efficace de mémoire.

    Avantages du tri par insertion:

    · Facilement mis en œuvre et très efficace lorsqu’il est utilisé avec de petits ensembles de
    données.

    · L’espace mémoire supplémentaire requis pour le tri par insertion est inférieur (c’est-à-dire O (1)).

    · Il est considéré comme une technique de tri en direct car la liste peut être triée lorsque les
    nouveaux éléments sont reçus.

    · C’est plus rapide que les autres algorithmes de tri.

    Tri par fusion:

    Le tri par fusion est un algorithme récursif et la complexité temporelle peut être exprimée comme une
    relation de récurrence.

    Le principe:

    1. Diviser : diviser la liste de N éléments à trier en deux sous-listes de N/2 éléments

    2. Régner : trier les deux sous-listes récursivement à l’aide du tri par fusion

    3. Combiner : fusionner les deux sous-listes triées pour produire la réponse triée

    Tri rapide:

    Cet algorithme appelé ALGORITHME TRI RAPIDE (QuickSort), il s'agit d'ordonner le tableau à partir d'un
    pivot (valeur choisie dans le tableau (généralement la première valeur). Dans ce mêmetableau on classe
    à gauche les valeurs inférieurs et à droite les valeurs supérieurs. Ensuite on rappelle l'ALGORIHTME TRI
    RAPIDE, une fois pour la partie gauche, une fois pour la partie droite.

    Avantages et inconvénients:

    Il possède un bon comportement de cas moyen. La complexité du tri rapide est complexe, car elle est
    plus rapide que des algorithmes tels que le tri à bulle, le tri par insertion et le tri par sélection.
    Cependant, il est complexe et très récursif, c’est la raison pour laquelle il n’est pas adapté aux grands
    tableaux.

    Vous aimerez peut-être aussi