Accueil › Cours › Tri Shell, tri par comptage, fusion

Les leçons de ce chapitre

1. Le tri Shell
2. Le tri par comptage
3. Fusionner deux tableaux triés

Leçon 24.1 : Le tri Shell

12 min

Le tri Shell améliore le tri par insertion. Le tri par insertion est lent quand un petit élément est loin à droite : il avance d'une case à la fois. Le tri Shell fait d'abord des insertions entre éléments éloignés de h cases, puis réduit h jusqu'à 1. Le dernier passage (h = 1) est un tri par insertion normal, mais presque tout est déjà en place.

• Le pas de départ : la suite h = 1, 4, 13, 40… (h ← 3 × h + 1) tant que h < n.
• Pour chaque h : un tri par insertion où l'on compare T[j − h] au lieu de T[j − 1].
• Puis h ← h div 3, jusqu'à h = 1 inclus.

Astuce : Avec h = 1, la boucle intérieure est exactement celle du tri par insertion : le tri Shell est une insertion « préparée ».

En Python

Tri Shell de 8 entiers lus.

n = 8
t = [0] * n
for i in range(n):
    t[i] = int(input())
h = 1
while h < n:
    h = 3 * h + 1
while h > 1:
    h = h // 3
    for i in range(h, n):
        v = t[i]
        j = i
        while j >= h and t[j - h] > v:
            t[j] = t[j - h]
            j = j - h
        t[j] = v
for i in range(n):
    print(t[i])

En algorithme

Avec des indices de 1 à n, la condition devient j > h.

Algorithme TriShell
Début
  n ← 8
  Pour i de 1 à n Faire
    Lire(T[i])
  FinPour
  h ← 1
  Tant que h < n Faire
    h ← 3 * h + 1
  FinTantQue
  Tant que h > 1 Faire
    h ← h div 3
    Pour i de h + 1 à n Faire
      v ← T[i]
      j ← i
      Tant que (j > h) et (T[j - h] > v) Faire
        T[j] ← T[j - h]
        j ← j - h
      FinTantQue
      T[j] ← v
    FinPour
  FinTantQue
  Pour i de 1 à n Faire
    Ecrire(T[i])
  FinPour
Fin

TDO
Objet | Type/Nature
T | Tableau de 8 Entiers
n, i, j, h, v | Entier

Leçon 24.2 : Le tri par comptage

10 min

Quand les valeurs sont des entiers dans un petit intervalle (des notes de 0 à 20), on peut trier sans comparer : on compte combien de fois chaque valeur apparaît, puis on réécrit le tableau dans l'ordre des valeurs.

• Un tableau nb de 21 cases à 0 : nb[v] compte les notes égales à v.
• Puis pour v de 0 à 20 : écrire v, nb[v] fois.

Attention : Ce tri ne marche que pour des entiers dans un intervalle connu et pas trop grand : pour des réels ou des noms, il faut un autre tri.

En Python

On trie 8 notes entières (0 à 20) par comptage.

n = 8
t = [0] * n
for i in range(n):
    t[i] = int(input())
nb = [0] * 21
for i in range(n):
    nb[t[i]] = nb[t[i]] + 1
k = 0
for v in range(21):
    for c in range(nb[v]):
        t[k] = v
        k = k + 1
for i in range(n):
    print(t[i])

En algorithme

En algorithme, le tableau NB va de 0 à 20 : on le déclare avec 21 cases et on décale de 1.

Algorithme TriComptage
Début
  n ← 8
  Pour i de 1 à n Faire
    Lire(T[i])
  FinPour
  Pour v de 1 à 21 Faire
    NB[v] ← 0
  FinPour
  Pour i de 1 à n Faire
    NB[T[i] + 1] ← NB[T[i] + 1] + 1
  FinPour
  k ← 1
  Pour v de 0 à 20 Faire
    Pour c de 1 à NB[v + 1] Faire
      T[k] ← v
      k ← k + 1
    FinPour
  FinPour
  Pour i de 1 à n Faire
    Ecrire(T[i])
  FinPour
Fin

TDO
Objet | Type/Nature
T | Tableau de 8 Entiers
NB | Tableau de 21 Entiers
n, i, v, c, k | Entier

Leçon 24.3 : Fusionner deux tableaux triés

11 min

Deux tableaux A et B sont déjà triés. Pour obtenir un tableau C trié qui contient tous leurs éléments, pas besoin de tout retrier : on avance dans les deux tableaux en même temps et on prend chaque fois le plus petit des deux éléments en tête.

• Trois indices : i dans A, j dans B, k dans C.
• Tant que les deux tableaux ont des éléments : on copie le plus petit et on avance son indice.
• Puis on recopie ce qui reste dans l'un des deux tableaux.

Astuce : La fusion parcourt chaque élément une seule fois : elle est bien plus rapide qu'un nouveau tri.

En Python

Fusion de deux listes triées données.

A = [2, 7, 11, 20]
B = [3, 5, 12, 18, 25]
na = 4
nb = 5
C = [0] * (na + nb)
i = 0
j = 0
k = 0
while i < na and j < nb:
    if A[i] <= B[j]:
        C[k] = A[i]
        i = i + 1
    else:
        C[k] = B[j]
        j = j + 1
    k = k + 1
while i < na:
    C[k] = A[i]
    i = i + 1
    k = k + 1
while j < nb:
    C[k] = B[j]
    j = j + 1
    k = k + 1
for k in range(na + nb):
    print(C[k])

En algorithme

Les trois boucles Tant que : la fusion, puis les restes de A et de B.

Algorithme Fusion
Début
  A[1] ← 2
  A[2] ← 7
  A[3] ← 11
  A[4] ← 20
  B[1] ← 3
  B[2] ← 5
  B[3] ← 12
  B[4] ← 18
  B[5] ← 25
  na ← 4
  nb ← 5
  i ← 1
  j ← 1
  k ← 1
  Tant que (i ≤ na) et (j ≤ nb) Faire
    Si A[i] ≤ B[j] Alors
      C[k] ← A[i]
      i ← i + 1
    Sinon
      C[k] ← B[j]
      j ← j + 1
    FinSi
    k ← k + 1
  FinTantQue
  Tant que i ≤ na Faire
    C[k] ← A[i]
    i ← i + 1
    k ← k + 1
  FinTantQue
  Tant que j ≤ nb Faire
    C[k] ← B[j]
    j ← j + 1
    k ← k + 1
  FinTantQue
  Pour k de 1 à na + nb Faire
    Ecrire(C[k])
  FinPour
Fin

TDO
Objet | Type/Nature
A | Tableau de 4 Entiers
B | Tableau de 5 Entiers
C | Tableau de 9 Entiers
na, nb, i, j, k | Entier

S'entraîner gratuitement

Chaque leçon a 3 exercices gratuits avec indices pour appliquer ce chapitre avec Hannibot.

← Chapitre précédent : Les fichiers · Chapitre suivant : JavaScript : les bases →

Tous les chapitres · Voir les devoirs corrigés de 2ème TI

Cours écrit pour Mission Carthage d'après le programme officiel. Ton professeur reste la référence.