Back

Algorithme de tri


Algorithme de Tri

  1. Définitions

    • Un algorithme de tri est un algorithme qui permet d'organiser une collection d'objets selon une relation d'ordre déterminée.
    • Un algorithme de tri est une suite finie d'instructions servant à réordonner une séquence d'éléments suivant un critère fixé à priori. Ce critère est en effet une relation d'ordre total sur les éléments à trier
    • La conception d'un algorithme de tri dépend du support matériel de la séquence de valeurs à trier (en mémoire centrale ou sur une mémoire secondaire).
      • Mémoires centrales: rapides (en nanosecondes) mais de taille limitée(en Mo)
      • Mémoires secondaires: lentes(en microsecondes) mais de grande taille (en Go)
  2. Principes:

    • Trouver le plus petit élément et le mettre au début de la liste
    • Trouver le 2ème plus petit et le mettre en seconde position
    • Trouver le 3ème plus petit élément et le mettre à la 3ème place,
  3. Autrement
  4. Commencer par i=1 et on cherche la position de l'élément le plus petit du tableau (pos_min).
    • Une fois cet emplacement trouvé, on compare son contenu avec T[1] et s'il sont différents(T[1]≠T[pos_min]), on permute l'élément de l'emplacement trouvé par l'élément de la première position T[1] sinon T[1] reste à sa place→ Après ce parcours le premier élément est bien placé.
    • On recommence le même procédé pour le reste du tableau (T[2],..,T[n]), ainsi on recherche le plus petit élément de cette nouvelle partie du tableau et on l'échange éventuellement avec T[2].
    • Ainsi de suite jusqu'à la dernière partie du tableau formée par les deux derniers éléments( T[n-1],..T[n]]).
    procédure <strong>tri_selection</strong>(tableau t, entier n)
          pour i de 1 à n - 1
              min ← i
              pour j de i + 1 à n
                  si t[j] < t[min], alors min ← j
              fin pour
              si min ≠ i, alors échanger t[i] et t[min]
          fin pour
      fin procédure
    

    En pascal

    ;procedure Tri par ************************ion(n : integer ; var t : tab)
    ;var i, j, min, tmp : integer
    begin
      for i:=1 to n-1 do 
      begin
      i:=min;
      for j:=i+1 to n do
      if (t[j] &lt; t[min]) then min:=j;
        if (i &lt;&gt; min) then 
          begin
             tmp := t[i];
             t[i] := t[min];
             t[min] := tmp;
          end;
       end; 
    end;
    
  5. Tri par insertion

    • Principes:
          Ordonner les deux premiers éléments
        • Insérer le 3ème élément de manière à ce que les 3 premiers éléments soient triés
        • Insérer le 4ème élément à “sa” place pour que. . .
        • . . .
        • Insérer le nème élément à sa place.
      Autrement Faire remonter le plus grand élément du tableau en comparant les éléments successifs.
      • On commence par i=1,on compare le 1er(T[1]) et le 2éme élément(T[2]) du tableau, s'il ne sont pas dans le bon ordre, on les permute, on passe ensuite au 2ème (T[2])et 3ème (T[3]), puis 3ème et 4ème et ainsi de suite jusqu'au (n-1)ième (T[n-1])et nième éléments (T[n]).
      • À la fin du premier parcours, on aura pousser le plus grand élément du tableau vers sa place finale qui est le nième élément du tableau.
      • On recommence cette opération en parcourant de 1 à n-1 puis de 1 à n-2 et ainsi de suite.
      • On arrête quand la partie à trier est réduite à un seul élément ou que le tableau est devenu trié (c.à.d aucune permutation n'a été faite lors du dernier parcours à vérifier par un indicateur)
  6. Le tri à bulle

    • Principe

    • Le tri à bulle fait remonter les grands éléments vers la fin du tableau.
    • Cette migration le long du tableau s'effectue par permutation successive.
    • Lire plus

Abonnez vous à notre chaîne YouTube gratuitement