Algorithme de tri

• 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)

• 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,

• 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] < t[min]) then min:=j;
    if (i <> min) then 
      begin
         tmp := t[i];
         t[i] := t[min];
         t[min] := tmp;
      end;
   end; 
end;

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)

• 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