Aller au contenu principal

Tri

Objectifs​

Comment trier une liste ?

  • Appliquer les algorithmes de tri suivants :
    • Tri par insertion
    • Tri par sélection
    • Tri fusion
    • Tri rapide

Cours​

Tri

Algorithmique et programmation

Tri d'une liste dans l'ordre croissant

4

1

5

3

2

↓ Algorithme de tri ↓

1

2

3

4

5

Tri par insertion

Insérer les éléments un à un dans une liste d'éléments déjà triés


FONCTION tri_insertion(liste)
  POUR i de 1 à liste.taille - 1
    x ← T[i]
    j ← i
    TANT QUE j > 0 et liste[j - 1] > x
      T[j] ← T[j - 1]
      j ← j - 1
    FIN TANT QUE
    T[j] ← x
  FIN POUR
FIN FONCTION

Tri par insertion

4

1

5

3

2

 

 

 

 

 

 

 

 

 

 


  • i : liste triée jusqu'à l'index i

  • j : index de l'élément à insérer (compare avec j - 1)

Tri par insertion

4

1

5

3

2

i

 

 

 

 

j

 

 

 

 


  • i : liste triée jusqu'à l'index i

  • j : index de l'élément à insérer (compare avec j - 1)

Tri par insertion

4

1

5

3

2

 

i

 

 

 

 

j

 

 

 


  • i : liste triée jusqu'à l'index i

  • j : index de l'élément à insérer (compare avec j - 1)

Tri par insertion

1

4

5

3

2

 

i

 

 

 

j

 

 

 

 


  • i : liste triée jusqu'à l'index i

  • j : index de l'élément à insérer (compare avec j - 1)

Tri par insertion

1

4

5

3

2

 

 

i

 

 

 

 

j

 

 


  • i : liste triée jusqu'à l'index i

  • j : index de l'élément à insérer (compare avec j - 1)

Tri par insertion

1

4

5

3

2

 

 

 

i

 

 

 

 

j

 


  • i : liste triée jusqu'à l'index i

  • j : index de l'élément à insérer (compare avec j - 1)

Tri par insertion

1

4

3

5

2

 

 

 

i

 

 

 

j

 

 


  • i : liste triée jusqu'à l'index i

  • j : index de l'élément à insérer (compare avec j - 1)

Tri par insertion

1

3

4

5

2

 

 

 

i

 

 

j

 

 

 


  • i : liste triée jusqu'à l'index i

  • j : index de l'élément à insérer (compare avec j - 1)

Tri par insertion

1

3

4

5

2

 

 

 

 

i

 

 

 

 

j


  • i : liste triée jusqu'à l'index i

  • j : index de l'élément à insérer (compare avec j - 1)

Tri par insertion

1

3

4

2

5

 

 

 

 

i

 

 

 

j

 


  • i : liste triée jusqu'à l'index i

  • j : index de l'élément à insérer (compare avec j - 1)

Tri par insertion

1

3

2

4

5

 

 

 

 

i

 

 

j

 

 


  • i : liste triée jusqu'à l'index i

  • j : index de l'élément à insérer (compare avec j - 1)

Tri par insertion

1

2

3

4

5

 

 

 

 

i

 

j

 

 

 


  • i : liste triée jusqu'à l'index i

  • j : index de l'élément à insérer (compare avec j - 1)

Tri par insertion

1

2

3

4

5

 

 

 

 

 

 

 

 

 

 


  • i : liste triée jusqu'à l'index i

  • j : index de l'élément à insérer (compare avec j - 1)

Tri par insertion

  • Intuitif

  • Tri "en place" (sans utiliser de mémoire supplémentaire)

  • Lent : pire cas pour une liste inversée

Tri par sélection

Sélectionner le plus petit élément pour le mettre à sa place. Refaire pareil avec les éléments restants


FONCTION tri_selection(liste)
  n ← liste.taille 
  POUR i de 0 à n - 2
    min ← i
    POUR j de i + 1 à n - 1
      SI liste[j] < liste[min], ALORS min ← j
    FIN POUR
    SI min ≠ i
      échanger liste[i] et liste[min]
    FIN SI
  FIN POUR
FIN FONCTION

Tri par sélection

4

1

5

3

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


  • i : liste triée jusqu'à l'index i

  • j : recherche du minimum dans la liste non triée

  • m : index du minimum trouvé

Tri par sélection

4

1

5

3

2

i

 

 

 

 

j

 

 

 

 

m

 

 

 

 


  • i : liste triée jusqu'à l'index i

  • j : recherche du minimum dans la liste non triée

  • m : index du minimum trouvé

Tri par sélection

4

1

5

3

2

i

 

 

 

 

 

j

 

 

 

 

m

 

 

 


  • i : liste triée jusqu'à l'index i

  • j : recherche du minimum dans la liste non triée

  • m : index du minimum trouvé

Tri par sélection

4

1

5

3

2

i

 

 

 

 

 

 

j

 

 

 

m

 

 

 


  • i : liste triée jusqu'à l'index i

  • j : recherche du minimum dans la liste non triée

  • m : index du minimum trouvé

Tri par sélection

4

1

5

3

2

i

 

 

 

 

 

 

 

j

 

 

m

 

 

 


  • i : liste triée jusqu'à l'index i

  • j : recherche du minimum dans la liste non triée

  • m : index du minimum trouvé

Tri par sélection

4

1

5

3

2

i

 

 

 

 

 

 

 

 

j

 

m

 

 

 


  • i : liste triée jusqu'à l'index i

  • j : recherche du minimum dans la liste non triée

  • m : index du minimum trouvé

Tri par sélection

1

4

5

3

2

 

i

 

 

 

 

j

 

 

 

 

m

 

 

 


  • i : liste triée jusqu'à l'index i

  • j : recherche du minimum dans la liste non triée

  • m : index du minimum trouvé

Tri par sélection

1

4

5

3

2

 

i

 

 

 

 

 

j

 

 

 

m

 

 

 


  • i : liste triée jusqu'à l'index i

  • j : recherche du minimum dans la liste non triée

  • m : index du minimum trouvé

Tri par sélection

1

4

5

3

2

 

i

 

 

 

 

 

 

j

 

 

 

 

m

 


  • i : liste triée jusqu'à l'index i

  • j : recherche du minimum dans la liste non triée

  • m : index du minimum trouvé

Tri par sélection

1

4

5

3

2

 

i

 

 

 

 

 

 

 

j

 

 

 

 

m


  • i : liste triée jusqu'à l'index i

  • j : recherche du minimum dans la liste non triée

  • m : index du minimum trouvé

Tri par sélection

1

2

5

3

4

 

 

i

 

 

 

 

j

 

 

 

 

m

 

 


  • i : liste triée jusqu'à l'index i

  • j : recherche du minimum dans la liste non triée

  • m : index du minimum trouvé

Tri par sélection

1

2

5

3

4

 

 

i

 

 

 

 

 

j

 

 

 

 

m

 


  • i : liste triée jusqu'à l'index i

  • j : recherche du minimum dans la liste non triée

  • m : index du minimum trouvé

Tri par sélection

1

2

5

3

4

 

 

i

 

 

 

 

 

 

j

 

 

 

m

 


  • i : liste triée jusqu'à l'index i

  • j : recherche du minimum dans la liste non triée

  • m : index du minimum trouvé

Tri par sélection

1

2

3

5

4

 

 

 

i

 

 

 

 

j

 

 

 

 

m

 


  • i : liste triée jusqu'à l'index i

  • j : recherche du minimum dans la liste non triée

  • m : index du minimum trouvé

Tri par sélection

1

2

3

5

4

 

 

 

i

 

 

 

 

 

j

 

 

 

 

m


  • i : liste triée jusqu'à l'index i

  • j : recherche du minimum dans la liste non triée

  • m : index du minimum trouvé

Tri par sélection

1

2

3

4

5

 

 

 

 

i

 

 

 

 

j

 

 

 

 

m


  • i : liste triée jusqu'à l'index i

  • j : recherche du minimum dans la liste non triée

  • m : index du minimum trouvé

Tri par sélection

1

2

3

4

5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


  • i : liste triée jusqu'à l'index i

  • j : recherche du minimum dans la liste non triée

  • m : index du minimum trouvé

Tri par sélection

  • Intuitif

  • Tri "en place"

  • Très lent : même pire cas que le tri par insertion

Tri fusion

Partager la liste en sous-liste d'un élément. Fusionner les sous-listes ensemble


FONCTION tri_fusion(liste)
  n ← liste.taille
  SI n ≤ 1
    RETOURNER liste
  SINON
    RETOURNER fusion(
      tri_fusion(première moitié de liste), 
      tri_fusion(deuxième moitié de liste)
    )
  FIN SI
FIN FONCTION

Tri fusion


FONCTION fusion(a, b) # deux listes triées
  c = []
  TANT QUE a et b ne sont pas vides
    SI a est vide
      Ajouter b dans c
    SINON SI b est vide
      Ajouter a dans c
    SINON SI a[0] ≤ b[0]
      Ajouter a[0] dans c
      Enlever premier élément de a
    SINON
      Ajouter b[0] dans c
      Enlever premier élément de b
    FIN SI
  FIN TANT QUE
  RETOURNER c
FIN FONCTION

Fusion

Fusion de deux listes triées

1

2

4

8

3

4

6

7

Fusion

1

2

4

8


3

4

6

7


  • Prendre le plus petit élément des deux listes

Fusion

1

2

4

8


3

4

6

7


  • Prendre le plus petit élément des deux listes

Fusion

1

2

4

8


3

4

6

7


  • Prendre le plus petit élément des deux listes

Fusion

1

2

3

4

8


4

6

7


  • Prendre le plus petit élément des deux listes

Fusion

1

2

3

4

8


4

6

7


  • Prendre le plus petit élément des deux listes

Fusion

1

2

3

4

4

8


6

7


  • Prendre le plus petit élément des deux listes

Fusion

1

2

3

4

4

6

8


7


  • Prendre le plus petit élément des deux listes

Fusion

1

2

3

4

4

6

7

8


  • Prendre le plus petit élément des deux listes

Fusion

1

2

3

4

4

6

7

8


  • Prendre le plus petit élément des deux listes

Tri fusion

4

1

5

3

2

Tri fusion

4

1

5

3

2


  • Diviser la liste jusqu'à obtenir des listes d'un élément.

  • Puis, fusionner les listes deux à deux en utilisant la fonction fusion.

Tri fusion

4

1

5

3

2


  • Diviser la liste jusqu'à obtenir des listes d'un élément.

  • Puis, fusionner les listes deux à deux en utilisant la fonction fusion.

Tri fusion

4

1

5

3

2


  • Diviser la liste jusqu'à obtenir des listes d'un élément.

  • Puis, fusionner les listes deux à deux en utilisant la fonction fusion.

Tri fusion

1

4

5

3

2


  • Diviser la liste jusqu'à obtenir des listes d'un élément.

  • Puis, fusionner les listes deux à deux en utilisant la fonction fusion.

Tri fusion

1

4

5

3

2


  • Diviser la liste jusqu'à obtenir des listes d'un élément.

  • Puis, fusionner les listes deux à deux en utilisant la fonction fusion.

Tri fusion

1

4

5

3

2


  • Diviser la liste jusqu'à obtenir des listes d'un élément.

  • Puis, fusionner les listes deux à deux en utilisant la fonction fusion.

Tri fusion

1

4

5

2

3


  • Diviser la liste jusqu'à obtenir des listes d'un élément.

  • Puis, fusionner les listes deux à deux en utilisant la fonction fusion.

Tri fusion

1

2

3

4

5


  • Diviser la liste jusqu'à obtenir des listes d'un élément.

  • Puis, fusionner les listes deux à deux en utilisant la fonction fusion.

Tri fusion

  • Rapide (optimal en moyenne)

  • Stratégie "Diviser pour régner" (divide and conquer) : parallélisable

  • Nécessite de la mémoire supplémentaire (pas "en place")

Tri rapide

Définir un élément pivot et séparer tout les éléments plus petit que et plus grand que le pivot. Récursivement trier les deux listes à gauche et à droite du pivot.

Partition

4

7

1

6

5

8

2

 

 

 

 

 

 

 

 

 

 

 

 

 

 


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Partition

4

7

1

6

5

8

2

p

 

 

 

 

 

 

 

i

 

 

 

 

j


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Partition

4

2

1

6

5

8

7

p

 

 

 

 

 

 

 

i

 

 

 

 

j


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Partition

4

2

1

6

5

8

7

p

 

 

 

 

 

 

 

 

i

 

 

j

 


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Partition

4

2

1

6

5

8

7

p

 

 

 

 

 

 

 

 

i

 

j

 

 


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Partition

4

2

1

6

5

8

7

p

 

 

 

 

 

 

 

 

i

j

 

 

 


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Partition

1

2

4

6

5

8

7

 

 

p

 

 

 

 

 

 

 

 

 

 

 


  • Le pivot est placé à la bonne place.

  • Trier la liste à sa gauche de la même manière

  • Trier la liste à sa droite de la même manière

Tri rapide

4

1

5

3

2

 

 

 

 

 

 

 

 

 

 


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Tri rapide

4

1

5

3

2

p

 

 

 

 

 

i

 

 

j


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Tri rapide

4

1

5

3

2

p

 

 

 

 

 

 

i

 

j


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Tri rapide

4

1

2

3

5

p

 

 

 

 

 

 

i

 

j


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Tri rapide

4

1

2

3

5

p

 

 

 

 

 

 

 

i

j


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Tri rapide

4

1

2

3

5

p

 

 

 

 

 

 

 

i

 


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Tri rapide

3

1

2

4

5

 

 

 

p

 

 

 

 

 

 


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Tri rapide

3

1

2

4

5

p

 

 

 

 

 

i

j

 

 


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Tri rapide

3

1

2

4

5

p

 

 

 

 

 

 

i

 

 


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Tri rapide

2

1

3

4

5

 

 

p

 

 

 

 

 

 

 


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Tri rapide

2

1

3

4

5

p

 

 

 

 

 

i

 

 

 


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Tri rapide

1

2

3

4

5

 

p

 

 

 

 

 

 

 

 


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Tri rapide

1

2

3

4

5

p

 

 

 

 

 

 

 

 

 


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Tri rapide

1

2

3

4

5

p

 

 

 

 

 

 

 

 

 


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Tri rapide

1

2

3

4

5

 

 

 

 

p

 

 

 

 

 


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Tri rapide

1

2

3

4

5

 

 

 

 

p

 

 

 

 

 


  • p : pivot choisi

  • i : éléments à gauche du pivot (plus petit)

  • j : éléments à droite du pivot (plus grand)

Tri rapide

  • Le plus rapide dans la plupart des cas

  • Diviser pour régner

  • Tri "en place"

  • Pas optimal si déjà trié

F pour passer en plein écran ou O pour afficher la vue d'ensemble.
Versions sans animation, plein écran, imprimable.

Accès rapide​

Exercices​

 3  1  5  2  7  6 

Trier la liste selon l'algorithme de tri indiqué. Entre chaque étape, seuls deux éléments peuvent être échangés.

Tri par insertion​

Trier la liste ci-dessus en utilisant le tri par insertion.

Solution
 3  1  5  2  7  6 
135276
132576
123576
123567

Tri par sélection​

Trier la liste ci-dessus en utilisant le tri par sélection.

Solution
 3  1  5  2  7  6 
135276
125376
123576
123567

Tri fusion​

Trier la liste ci-dessus en utilisant le tri fusion.

Solution
3
1
5
2
7
6
13
5
2
7
6
135
2
7
6
135
27
6
135
267
123567

Tri rapide​

Trier la liste ci-dessus en utilisant le tri rapide. Indiquer les pivots.

Solution
 3  1  5  2  7  6 
312576
213576
123576
123576
123567

En gras, les pivots. En souligné, les éléments déjà triés.

Références​

Dernière mise à jour le