Forum programmation
 
AccueilPortailFAQRechercherS'enregistrerMembresGroupesConnexion

Partagez | 
 

 Tri par insertion

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
mtcs
Administrateur
Administrateur
avatar

Nombre de messages : 1605
Date d'inscription : 21/11/2006

MessageSujet: Tri par insertion   Ven 9 Fév - 15:56

Le tri par insertion est le tri le plus efficace sur des listes de petite taille. C'est pourquoi il est utilisé par d'autres méthodes comme le Tri rapide (ou quicksort).
Le principe de ce tri est très simple: c'est le tri que toute personne normale utilise quand elle a des dossiers (ou n'importe quoi d'autre) à classer. On prend un dossier et on le met à sa place parmi les dossiers déjà triés. Puis on recommence avec le dossier suivant.
Pour procéder à un tri par insertion, il suffit de parcourir une liste : on prend les éléments dans l'ordre. Ensuite, on les compare avec les éléments précédents jusqu'à trouver la place de l'élément qu'on considère. Il ne reste plus qu'à décaler les éléments du tableau pour insérer l'élément considéré à sa place dans la partie déjà triée.


Propriétés

Dans le cas du tri par insertion sur un tableau comme implémenté plus bas (implémentation la plus courante), les propriétés suivantes sont vérifiées:




  1. Le nombre de comparaisons nécessaires est de l'ordre de N²/2.
  2. Le nombre moyen d'échanges est de l'ordre de N²/4.


Si une liste chaînée est utilisée, il n'y a plus d'échanges à faire (les insertions se font en temps constant), mais le nombre de comparaisons pour trouver l'emplacement où insérer reste de l'ordre de N²/4.
A contrario, avec un tableau il est possible de faire un nombre de comparaisons de l'ordre de N.ln(N) en utilisant une recherche par dichotomie pour trouver l'emplacement où insérer l'élément. Néanmoins le nombre moyen d'échanges ne sera pas modifié, et l'algorithme reste peu efficace sur les grands tableaux par rapport au tri rapide.
Dans le cas d'une liste presque triée, où seules quelques comparaisons et échanges sont nécessaires par élément, l'implémentation la plus courante du tri par insertion est souvent la meilleure méthode de tri.
Le tri par insertion est un tri stable (conservant l'ordre d'apparition des éléments égaux) et un tri sur place (les éléments sont directement triés dans la structure).

Code:
Tri par insertion en Pascal en ordre croissant.
const MAX = 100;
type tab = array [1..MAX] of integer;

Procedure TriInsertion(n : integer ; var t : tab);
  var i, j, k : integer;
  begin
      for i:=2 to n do
        begin
            k := t[i];  (* k est la valeur à insérer *)
                        (* dans l'endroit approprié du tableau *)
                        (* On décale toutes les valeurs du tableau < k *)
                        (* à droite pour vider une place pour k *)
            j := i - 1;
            while (j >= 1) and (t[j] > k) do
                begin
                  t[j + 1] := t[j];
                  j := j - 1;
                end;

        (* finalement la valeur k est insérée à son emplacement adéquat *)
              t[j + 1] := k;
          end;
  end;
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Chaker
Administrateur
Administrateur
avatar

Nombre de messages : 731
Age : 28
Date d'inscription : 17/01/2007

MessageSujet: Re: Tri par insertion   Ven 9 Fév - 22:04

merci Mohamed Very Happy
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
mtcs
Administrateur
Administrateur
avatar

Nombre de messages : 1605
Date d'inscription : 21/11/2006

MessageSujet: Re: Tri par insertion   Sam 10 Fév - 13:29

merci à vous chaker
Revenir en haut Aller en bas
Voir le profil de l'utilisateur
Contenu sponsorisé




MessageSujet: Re: Tri par insertion   

Revenir en haut Aller en bas
 
Tri par insertion
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum programmation :: Programmation :: Delphi & Pascal :: Pascal :: Cours-
Sauter vers: