Les algorithmes de tri

Par ftymen

Description détaillée sur un exemple simple des algorithmes de tri par sélection, insertion et bulle.


1 – Tri par sélection

Répéter
1. chercher le plus petit (le plus grand) élément
2. le mettre au début (à la fin)
Exemple :
Trier le tableau [3][6][1][1][4]

[3][6][1][1][4]
On repère le nombre le plus petit dans la liste des 5 nombres
[3][6][1][1][4]
On intervertit ce nombre avec celui placé en première position.
[1][6][3][1][4]

Le premier nombre de la liste est le plus petit.

Il reste à effectuer la même opération sur le reste du tableau.

[1][6][3][1][4] → Repérage du nombre le plus petit : positions 2 à 5
[1][1][3][6][4] → On intervertit ce nombre avec celui placé en 2ème position.
[1][1][3][6][4] → Repérage du nombre le plus petit : positions 3 à 5. Rien à faire le nombre est en bonne position.
[1][1][3][6][4] → Repérage du nombre le plus petit : positions 4 à 5.
[1][1][3][4][6] → On intervertit ce nombre avec celui placé en 4ème position.

Le dernier nombre est forcément le plus grand.
On obtient le tableau rangé suivant
[1][1][3][4][6]

2 – Tri par insertion
Dans ce cas, itérativement, nous insérons le prochain élément dans la partie qui est déjà triée précédemment.

En insérant un élément dans la partie triée, il se pourrait qu’on ait à déplacer plusieurs autres.
Exemple :
Trier le tableau [3][6][1][1][4]
[3][6][1][1][4]

On prend le premier élément du tableau :
[3]

On prend le 2ème élément du tableau et on le compare au 1er .
[3] → [6]
[3][6]
On obtient un tableau de 2 éléments ordonné.

On prend le 3ème élément du tableau initial et on compare au dernier élément du tableau ordonné
[3][6] → [1]

[3][1][6] →[1]<[6] On insère le [1] avant le [6]
[1][3][6] →[1]<[3] On insère le [1] avant le [3]
[1][3][6]
On obtient un tableau de 3 éléments ordonné.

Même chose avec le 4ème élément du tableau initial.
[1][3][6] → [1]

[1][3][1][6] →[1]<[6] On insère le [1] avant le [6]
[1][1][3][6] →[1]<[3] On insère le [1] avant le [3]
[1][1][3][6]
On obtient un tableau de 4 éléments ordonné.

Même chose avec le 5ème élément du tableau initial.
[1][1][3][6] → [4]

[1][1][3][4][6] →[4]<[6] On insère le [4] avant le [6]
[1][1][3] [4] [6]
On obtient un tableau de 5 éléments ordonné.

3 – Tri bulle
Le principe du tri bulle est de comparer deux à deux les éléments e1 et e2 consécutifs d’un tableau et d’effecteur une permutation si e1 > e2.
On continue de trier jusqu’à ce qu’il n’y ait plus de permutation.

Exemple :
Trier le tableau [3][6][1][1][4]
On compare deux nombres consécutifs et on intervertit l’ordre si nécessaire.
[3][6][1][1][4]
[3][6][1][1][4] → On compare le [6] et le [1]
[3][1][6][1][4] → On intervertit le [6] et le [1]
[3][1][6][1][4] → On compare le [6] et le [1]
[3][1][1][6][4] → On intervertit le [6] et le [1]
[3][1][1][6][4] → On compare le [6] et le [4]
[3][1][1][4][6] → On intervertit le [6] et le [4]

On recommence l’opération tant qu’il y a des permutations.
[3][1][1][4][6] → On compare le [3] et le [1]
[1][3][1][4][6] → On intervertit le [1] et le [3]
[1][3][1][4][6] → On compare le [3] et le [1]
[1][1][3][4][6] → On intervertit le [1] et le [3]
Il n’y a plus de permutations possibles.
On obtient le tableau rangé suivant :
[1][1][3][4][6]


Cet article contient des documents réservés aux enseignants.
Voir en bas de la page pour se connecter dans l'espace enseignant.

 Catégorie: ISN P5JS Processing Python

Laisser une réponse