Chapitre 4 : Algorithmes de tri
4.1 Tri d'un tableau
Données : un tableau de nombres
        Ex :
X[1] X[2] X[3] X[4] X[5]
10 6 5 2 9
Problème : écrire un programme pour trier (par ordre croissant) ce tableau.
        Ex :  on obtient après traitement le tableau suivant :
X[1] X[2] X[3] X[4] X[5]
2 5 6 9 10

Cette opération a priori banale est très utilisée (surtout en informatique de gestion) et représente (dit-on) plus de 20% de l'activité informatique (en temps de calcul) planétaire !

Idée:     i<--1
           - chercher le min de X[i]...X[n] = X[j]
           - échanger X[j] et X[i]
            i<--i+1  et répéter l'opération
Plus précisément :
            pour i=1 jusqu'à n faire
            - X[j] = le min de   X[i]...X[n]
            - échanger X[j] et X[i]

Exercice:  Appliquer l'algorithme au tableau suivant :
 
X[1] X[2] X[3] X[4] X[5]
10 6 5 2 9
i=1
__ __ __ __ __
i=2
__ __ __ __ __
i=3
__ __ __ __ __
i=4
__ __ __ __ __
i=5
2 5 6 9 10
On remarque que l'exécution de l'algorithme pour i=5 n'amène à rien, d'où la restriction : pour i=1 jusqu'à n-1.
Il nous faut préciser les deux instructions :

X[j] = le min de X[i]... X[n]:
                        j<--i
                        pour k=i+1 jusqu'à n
                            si X[k]<X[j] alors j<--k
                            finsi
échanger X[j] et X[i]:
                        T<--X[i]
                        X[i]<--X[j]
                        X[j]<--T
d'où
                           Algorithme 1

pour i = 1 jusqu'à n-1 faire 
              j<--i; 
              pour k=i+1 jusqu'à n faire 
                            si X[k]<X[j] alors j<--k 
                            finsi 
              finpour; 
              T<--X[i]; 
              X[i]<--X[j]; 
              X[j]<--T 
finpour

Exercice: Dessiner l'organigramme correspondant.

Exercice: Exécuter l'algorithme sur le tableau suivant :

X[1] X[2] X[3] X[4] X[5]
8 6 4 2 0
Combien de comparaisons sont nécessaires ? Généraliser à un tableau à n colonnes.

4.2  Tri d'un tableau d'entiers bornés

Données: un tableau de nombre X[1]...X[n] et un entier m tels que :
        X[i] est entier pour tout 1=<i=<n,
         0=<X[i]=<m.
 Ex : n=7, m=2
X[1] X[2] X[3] X[4] X[5] X[6] X[7]
0 2 1 2 0 1 1
Problème: trier dans l'ordre croissant les valeurs des X[i].

Idée: tirer profit du surplus (par rapport à la section précédente) d'information dont on dispose :
        -X[i] entier,
        -on connaît un majorant m de tout les X[i].

On procède en deux temps :
Compression :
créer un tableau y[0...m] où y[i] est le nombre de fois où l'entier i apparaît dans le tableau X.
 Ex :

Y[0] Y[1] Y[2]
2 3 2
Décompression :
à partir de Y, reconstruire X trié
Ex :
X[1] X[2] X[3] X[4] X[5] X[6] X[7]
0 0 1 1 1 2 2
Exercice: Appliquer l'idée au tableau suivant n=6, m=3:
X[1] X[2] X[3] X[4] X[5] X[6]
3 0 3 2 3 2
                  Algorithme 1
{initialisation du tableau Y au vide}
pour i = 0 jusqu'à n faire 
         Y[i]<--0; 
finpour 
{compression}
pour j = 1 jusqu'à n faire 
         Y[X[j]]<--Y[X[j]]+1; 
finpour 
{décompression}
i<--0; 
pour j = 1 jusqu'à n faire 
         tant que Y[i]=0 faire 
                     i<--i+1; 
         fin tant que 
         X[j]<--i; 
         Y[i]<--Y[i]-1; 
finpour
On montre que cet algorithme est plus rapide que le précédent :
        pour n (taille du tableau X) "grand" par rapport à m
                            temps algorithme 1 ~ n²,
                            temps algorithme 2 ~ n.
car on utilise l'information "X[i] entier compris entre 0 et m".
Mais l'algorithme 2 consomme plus de mémoire (le tableau Y).

 Exercice :
                -Dessiner l'organigramme correspondant à l'algorithme 2.
                -Programmer les deux algorithmes.
                -Vérifier pratiquement que pour n grand, le temps d'exécution de l'algorithme 1 est plus important que celui de l'algorithme 2.