Algorithmes de tri

Introduction

Les algorithmes de tri sont des « classiques » des algorithmes informatiques. Ils sont utilisés dans de nombreux logiciel comme par exemple les tableurs.

Il est assez rare d’implémenter soi-même un algorithme de tri car ils sont souvent déjà présents dans des méthodes des langages informatiques (par exemple sort() pour les tableaux en Python). Néanmoins ils ont un grand intérêt pédagogique.

1) En utilisant 8 cartes prises au hasard d'un jeu de cartes, essayez d'écrire un algorithme pour remettre les cartes dans l'ordre.

Tri par insertion

Voici l’algorithme de tri par insertion :

VARIABLE
t : tableau d'entiers
i : nombre entier
j : nombre entier
k : nombre entier
DEBUT
j←2
tant que j<=longueur(t):   //boucle 1
  i←j-1
  k←t[j]
  tant que i>0 et que t[i]>k:   //boucle 2
    t[i+1]←t[i]
    i←i-1
  fin tant que
  t[i+1]←k
  j←j+1
fin tant que
FIN

Fonctionnement

Faisons tourner cet algorithme sur le tableau t=[27,10,12,8,11] :

j=2
2≤5 on rentre dans la boucle 1
i=1
k=10
1>0 et 27>10 on rentre dans la boucle 2
t[2] = 27    (t=[27,27,12,8,11])
i=0
retour au début de la boucle 2

i=0
j=2
k=10
i=0 : on n’entre pas dans la boucle 2
t[1]=10    (t=[10,27,12,8,11])
j=3
retour au début de la boucle 1

j=3
3≤5 on rentre dans la boucle 1
i=2
k=12
2>0 et 27>12 on rentre dans la boucle 2
t[3] = 27    (t=[10,27,27,8,11])
i=1
retour au début de la boucle 2

j=3
i=1
k=12
1>0 mais 10<12 : on n’entre pas dans la boucle 2
t[2]=12    (t=[10,12,27,8,11])
j=4
retour au début de la boucle 1

2) Complétez le déroulement de l’algorithme pour j=4.

3) Résumons maintenant l’algorithme de tri par insertion avec des schémas :

4) Faire le même type de schémas avec le tableau t=[12,8,23,10,15]

Complexité

5) Étudions la complexité de l’algorithme de tri par insertion en commençant par calculer le nombre d’opérations :

VARIABLE
t : tableau d'entiers
i : nombre entier
j : nombre entier
k : nombre entier
DEBUT
j←2
tant que j<=longueur(t):   // boucle 1
  i←j-1
  k←t[j]
  tant que i>0 et que t[i]>k:   // boucle 2
    t[i+1]←t[i]
    i←i-1
  fin tant que
  t[i+1]←k
  j←j+1
fin tant que
FIN

6) Quelle est alors la complexité de cet algorithme ?

Tri par sélection

Voici l’algorithme de tri par sélection :

VARIABLE
t : tableau d'entiers
i : nombre entier
min : nombre entier
j : nombre entier
DEBUT
i←1
tant que i<longueur(t):   //boucle 1
  j←i+1
  min←i
  tant que j<=longueur(t):   //boucle 2
    si t[j]<t[min]:
      min←j
    fin si
    j←j+1
  fin tant que
  si min≠i :
    échanger t[i] et t[min]
  fin si
  i←i+1
fin tant que
FIN

Fonctionnement

7) Plutôt que de dérouler encore cet algorithme, nous allons directement l’expliquer avec des schémas sur le tableau t=[12,8,23,10,15]

8) Expliquer l’algorithme avec des schémas sur le tableau t=[15,16,11,13,12]

Complexité

9) Calculons le nombre d’opérations de l’algorithme de tri par sélection :

VARIABLE
t : tableau d'entiers
i : nombre entier
min : nombre entier
j : nombre entier
DEBUT
i←1
tant que i<longueur(t):   //boucle 1
  j←i+1
  min←i
  tant que j<=longueur(t):   //boucle 2
    si t[j]<t[min]:
      min←j
    fin si
    j←j+1
  fin tant que
  si min≠i :
    échanger t[i] et t[min]
  fin si
  i←i+1
fin tant que
FIN

10) Donner alors la complexité de cet algorithme.