Tri non récursif

var T:tableau[1..N] d'entiers;

• Tri sélection
• Tri insertion et tri à bulle
• Fusion de tableaux triés
• Tri par dénombrement

Tri sélection

Ce tri est basé sur l'algorithme de recherche du minimum On adapte cet algorithme pour pouvoir effectuer la recherche dans un sous-tableau. On a le déroulement ici

fonction minimumSoustableau(ref T:tableau[1..N] d'entiers, val Imin,Imax:entier):entier; 
  var sauv:entier;
  début
    sauv=Imin;
    pour i allant de Imin+1 à Imax faire
      si T[i]<T[sauv] alors
        sauv=i;
      finsi
    finpour
    retourner(sauv);
  fin
finfonction
  
fonction triSelection(ref T:tableau[1..N] d'entiers):vide;
  var i,j,indice_cle:entier;
  début
    pour i allant de 1 à N-1 faire
      indice_cle=minimumSoustableau(T,i,N);
      echange(T[i],T[indice_cle]);
    finpour
  fin
finfonction

Propriété 6.1. La complexité de l'algorithme triSelection sur une instance de taille N est O(n²)

---

Tri insertion et tri à bulle

Propriété 6.2. Soit T un tableau d'entiers trié d'indice variant entre i et j. Soit e un entier quelqconque, alors on a l'une des propriétés suivantes :

• e≤T[i]
• il existe un unique entier k dans [i..j-1] tel que T[k]<e≤T[k+1]
• e>T[j]

On déduit de cette propriété deux algorithmes permettant de trier un tableau.

Tri insertion

fonction triInsertion(ref T:tableau[1..N] d'entiers):vide;
  var i,j,cle:entier;
  début
    pour i allant de 2 à N faire
      cle=T[i];
      j=i-1;
      tant que j>0 et T[j]>cle faire
        T[j+1]=T[j];
        j=j-1;
      fintantque
      T[j+1]=cle;
    finpour
  fin

On a le déroulement ici

Propriété 6.3. La complexité de l'algorithme triInsertion sur une instance de taille N est :

• au minimum en O(N),
• au maximum et en moyenne en O(N²).

Idée de la démonstration
La boucle pour s'effectue systématiquement et demandera O(N)opérations.
La boucle tant que effectue au minimum 1 opération (cas ou les nombres sont déjà trié) et au maximum O(N) .
La boucle tant que effectue en moyenne O(N/2) opérations.

Tri à bulle

fonction triBulle(ref T:tableau[1..N] d'entiers):vide;
  var i,j,cle:entier;
  début
    pour i allant de 1 à N-1 faire
      pour j allant de N à i+1 par pas de -1 faire
        si T[j]<T[j-1] alors
          echange(T,j,j-1);
        finsi
      finpour
    finpour
  fin

On a le déroulement ici

Propriété 6.4. La complexité de l'algorithme triBulle sur une instance de taille N est O(N²).

---

Fusion de tableaux triés

Lorsque deux tableaux T1 et T2 sont triés il est aisé de construire un nouveau tableau contenant la séquence trié regroupant les séquences correspondantes à T1 et T2.


PREMIERE VERSION
fonction fusion(ref T1:tableau[1..N1] d'entier;
                ref T2:tableau[1..N2] d'entier
                ):tableau[1..N1+N2] d'entier;
  var I1,I2,i:entier;
  var T:tableau[1..N1+N2]d'entier;
  début
    I1=1;
    I2=1;
    pour i allant de 1 à N1+N2 faire
      si T1[I1]≤T2[I2] alors
        T[i]=T1[I1];
        I1=I1+1;
      sinon
        T[i]=T2[I2];
        I2=I2+1;
      finsi
    finpour
    retourner(T)
  fin
finfonction

Complexité : O(n)
Attention, cette version ne fonctionne pas toujours. Par exemple, si I1 a dépassé N1 et vaut par exemple N1+1, on comparera T1[N1+1] à T2[I2] ce qui n'a pas de sens. Il faut donc utiliser un algorithme exact. On a le déroulement ici

---

Tri par dénombrement

Soit une séquence d'éléments de [0..k], il est alors possible de réaliser l'histogramme des valeurs. Par suite le tri des élements de la séquence se fait en temps linéaire O(n).

fonction triHisto(ref T:tableau[1..N] d'entiers):vide;
  var H:tableau[0..maximum(T)] d'entier;
  var i,j,k,max: entier;
  début
    init(H,0);
    pour i allant de 1 à N faire
      H[T[i]]=H[T[i]]+1;
    finpour
    i=1;
    max:=maximum(T);
    pour j allant de 0 à max faire
        pour k allant de 1 à H[j] faire
          T[i]=j;
          i=i+1;
        finpour
    finpour
  fin
finfonction

On a le déroulement ici