Méthodes de tri

id: 33-239-methodes-de-tri slug: 33-239-methodes-de-tri titre: Méthodes de tri chapitre: 6 chapitre_titre: Les traitements avancés lecon: 1 niveau: 4eme-sci ordre: 1 prerequis: [] duree_estimee_min: 45 mots_cles:

• tri
• selection
• bulle
• insertion
• tableau
• algorithme
• permutation langages:
• analyse objectifs:
• Définir ce qu'est un algorithme de tri
• Expliquer le principe du tri par sélection
• Expliquer le principe du tri à bulles
• Expliquer le principe du tri par insertion
• Estimer le nombre de comparaisons et de permutations effectuées par chaque méthode status: published source_pdf: 33_239.pdf source_pages:
• 1 kind: cours

I. Introduction

La conception d'un algorithme de tri dépend du support matériel de la séquence de valeurs à trier (en mémoire centrale ou sur une mémoire secondaire) :

• Mémoires centrales : rapides (en nanosecondes) mais de taille limitée (en Mo).
• Mémoires secondaires : lentes (en microsecondes) mais de grande taille (en Go).

Les algorithmes de tri vont devoir en tenir compte. Les algorithmes que nous allons définir traitent des tableaux situés dans la mémoire centrale.

II. Les méthodes de tri

On a choisi de trier les séquences par ordre croissant (du plus petit au plus grand) relativement à un ordre total noté ≤.

1. Le tri par sélection

Principe

• Commencer par i = 1 et chercher la position de l'élément le plus petit du tableau (pos_min).
• Une fois cet emplacement trouvé, on compare son contenu avec T[1] et s'ils sont différents (T[1] ≠ T[pos_min]), on permute l'élément de l'emplacement trouvé avec l'élément de la première position T[1]. Sinon, T[1] reste à sa place. → Après ce parcours, le premier élément est bien placé.
• On recommence le même procédé pour le reste du tableau (T[2], ..., T[n]) : on recherche le plus petit élément de cette nouvelle partie du tableau et on l'échange éventuellement avec T[2].
• Ainsi de suite jusqu'à la dernière partie du tableau formée par les deux derniers éléments (T[n-1], T[n]).

N.B. La recherche du plus petit élément d'un tableau sera assurée par une fonction renvoyant la position du minimum. Ce minimum est éventuellement répété plusieurs fois dans T ; on décidera de choisir le premier.

2. Le tri à bulles

Principe

Faire remonter le plus grand élément du tableau en comparant les éléments successifs.

• On commence par i = 1, on compare le 1ᵉʳ (T[1]) et le 2ᵉ élément (T[2]) du tableau. S'ils ne sont pas dans le bon ordre, on les permute. On passe ensuite au 2ᵉ (T[2]) et 3ᵉ (T[3]), puis 3ᵉ et 4ᵉ, et ainsi de suite jusqu'au (n-1)ᵉ (T[n-1]) et nᵉ éléments (T[n]).
• À la fin du premier parcours, on aura poussé le plus grand élément du tableau vers sa place finale, qui est le nᵉ élément du tableau.
• On recommence cette opération en parcourant de 1 à n-1, puis de 1 à n-2, et ainsi de suite.
• On arrête quand la partie à trier est réduite à un seul élément, ou que le tableau est devenu trié (c.-à-d. aucune permutation n'a été faite lors du dernier parcours, à vérifier par un indicateur).

3. Le tri par insertion

Principe

On suppose que les i - 1 premiers éléments sont triés.

• On cherche la position du iᵉ élément dans la partie du tableau commençant de 1 à i.
• Si cette position est i, l'élément est donc à sa bonne place.
• Sinon, supposant que cette position est j ; ce j est forcément entre 1 et i - 1. → (1) On affecte T[i] à une variable auxiliaire tmp, (2) On décale d'un pas vers l'avant (à droite) tous les éléments de j à i - 1, (3) Puis on insère l'élément d'indice i (précédemment sauvegardé dans tmp) à la position j.

On commence ce procédé à partir du 2ᵉ élément i = 2 jusqu'à atteindre la fin du tableau.

Synthèse

Les trois méthodes ont une complexité quadratique dans le pire des cas, mais elles diffèrent par le nombre d'échanges effectués : le tri par sélection est intéressant lorsque les permutations coûtent cher, tandis que le tri par insertion est efficace si le tableau est déjà presque trié.