Université Bordeaux 1
Licence Semestre 2   Initiation à l'algorithmique
Dernière mise à jour effectuée le 2 Juillet 2007

Tri non récursif


Remarque préliminaire
On considèrera dans tout ce chapitre que l'on manipule des entiers. L'objet du tri est d'ordonner une séquence de N entiers. On considèrera que ces entiers sont rangés dans un tableau
var T:tableau[1..N] d'entiers;
De plus, on considèra que l'ordre est croissant.

  1. Tri sélection
  2. 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(n2)

  3. Tri insertion et tri à bulle
  4. 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(N2).
    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(N2).

  5. Fusion de tableaux triés
  6. 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

  7. Tri par dénombrement
  8. 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