Share
Dans cette section, nous allons examiner cinq algorithmes utilisés pour trier les données dans un tableau. Nous commencerons par un algorithme naïf, le tri à bulle, et nous terminerons par l'algorithme de tri à usage général le plus courant, le tri rapide.
Avec chaque algorithme, j'expliquerai comment le tri est effectué et fournira également des informations sur la complexité optimale, moyenne et maximale, en termes de performances et d'utilisation de la mémoire..
Pour que le code de l’algorithme de tri soit un peu plus facile à lire, un outil commun Échanger Cette méthode sera utilisée par tout algorithme de tri qui doit permuter les valeurs d'un tableau par index.
void Swap (T [] éléments, int gauche, int droite) if (left! = right) T temp = éléments [left]; items [left] = items [right]; items [right] = temp;
| Comportement | Trie le tableau d'entrée en utilisant l'algorithme de tri à bulles. | ||
| Complexité | Meilleur cas | Cas moyen | Pire cas |
| Temps | Sur) | Sur2) | Sur2) |
| Espace | O (1) | O (1) | O (1) |
Le tri en bulle est un algorithme de tri naïf qui opère en effectuant plusieurs passages dans le tableau, en déplaçant chaque fois la plus grande valeur non triée vers la droite (fin) du tableau..
Considérez le tableau d'entiers non trié suivant:
Tableau d'entiers non trié Lors du premier passage dans le tableau, les valeurs trois et sept sont comparées. Étant donné que sept est supérieur à trois, aucun échange n'est effectué. Ensuite, sept et quatre sont comparés. Sept est supérieur à quatre, les valeurs sont donc permutées, ce qui rapproche les sept valeurs d'un pas vers la fin du tableau. Le tableau ressemble maintenant à ceci:
Les 4 et 7 ont échangé leurs positions Ce processus est répété et les sept finissent finalement par être comparés aux huit, ce qui est plus grand, de sorte qu'aucun échange ne peut être effectué, et la fin se termine à la fin du tableau. À la fin du premier passage, le tableau ressemble à ceci:
Le tableau à la fin du passage 1 Parce qu'au moins un échange a été effectué, une autre passe sera effectuée. Après le deuxième passage, les six sont entrés en position.
Le tableau à la fin du passage 2 Encore une fois, puisqu’au moins un échange a été effectué, un autre passage est effectué..
Le passage suivant, cependant, constate qu'aucun échange n'est nécessaire car tous les éléments sont dans l'ordre de tri. Comme aucun échange n'a été effectué, la matrice est connue pour être triée et l'algorithme de tri est complet.
public void Sort (T [] items) bool swapped; do swapped = false; pour (int i = 1; i < items.Length; i++) if (items[i - 1].CompareTo(items[i]) > 0) Swap (éléments, i-1, i); permuté = vrai; while (échangé! = faux);
| Comportement | Trie le tableau d'entrée en utilisant l'algorithme de tri par insertion. | ||
| Complexité | Meilleur cas | Cas moyen | Pire cas |
| Temps | Sur) | Sur2) | Sur2) |
| Espace | O (1) | O (1) | O (1) |
Le tri par insertion fonctionne en effectuant un seul passage dans le tableau et en insérant la valeur actuelle dans la partie déjà triée (début) du tableau. Une fois que chaque index est traité, il est connu que tout ce qui a été rencontré est trié et que tout ce qui suit est inconnu..
Attends quoi?
Le concept important est que le tri par insertion fonctionne en triant les éléments au fur et à mesure qu'ils sont rencontrés. Comme il traite le tableau de gauche à droite, nous savons que tout ce qui se trouve à gauche de l'index actuel est trié. Ce graphique montre comment le tableau est trié à chaque fois qu'un index est rencontré:
Un tableau en cours de traitement par tri par insertion Au fur et à mesure du traitement, le tableau devient de plus en plus trié jusqu'à ce qu'il soit complètement trié.
Regardons un exemple concret. Ce qui suit est un tableau non trié qui sera trié en utilisant le tri par insertion.
Tableau d'entiers non trié Lorsque le processus de tri commence, l'algorithme de tri commence à l'indice zéro avec la valeur trois. Puisqu'il n'y a pas de valeurs qui précèdent, le tableau jusqu'à l'index zéro inclus est connu pour être trié.
L'algorithme passe ensuite à la valeur sept. Puisque sept est supérieur à tout ce qui se trouve dans la plage triée connue (qui n'en comprend actuellement que trois), les valeurs jusqu'à sept inclusivement sont connues pour être en ordre de tri..
À ce stade, il est connu que les index de tableau 0-1 sont triés et que 2-n sont dans un état inconnu..
La valeur à l'index deux (quatre) est vérifiée ensuite. Étant donné que quatre correspond à moins de sept, il est connu que quatre doivent être déplacés à leur place dans la zone de tableau triée. La question est maintenant de savoir à quel index du tableau trié la valeur doit être insérée. La méthode pour ce faire est la FindInsertionIndex indiqué dans l'exemple de code. Cette méthode compare la valeur à insérer (quatre) aux valeurs de la plage triée, en commençant à l'indice zéro, jusqu'à trouver le point auquel la valeur doit être insérée..
Cette méthode détermine que l'index un (entre trois et sept) est le point d'insertion approprié. L'algorithme d'insertion (le Insérer method) effectue ensuite l'insertion en supprimant la valeur à insérer du tableau et en décalant toutes les valeurs du point d'insertion vers l'élément supprimé vers la droite. Le tableau ressemble maintenant à ceci:
Tableau après premier algorithme d'insertion On sait maintenant que le tableau de l'index zéro à deux est trié et que tout ce qui va de l'index trois à la fin est inconnu. Le processus recommence maintenant à l'index trois, qui a la valeur quatre. Comme l'algorithme continue, les insertions suivantes se produisent jusqu'à ce que le tableau soit trié.
Tableau après d'autres algorithmes d'insertion Quand il n'y a pas d'autres insertions à effectuer, ou quand la partie triée du tableau est le tableau entier, l'algorithme est terminé.
Accentsconagua
public void Sort (T [] items) int triRangeRangeEndIndex = 1; tant que (sortRangeEndIndex < items.Length) if (items[sortedRangeEndIndex].CompareTo(items[sortedRangeEndIndex - 1]) < 0) int insertIndex = FindInsertionIndex(items, items[sortedRangeEndIndex]); Insert(items, insertIndex, sortedRangeEndIndex); sortedRangeEndIndex++; private int FindInsertionIndex(T[] items, T valueToInsert) for (int index = 0; index < items.Length; index++) if (items[index].CompareTo(valueToInsert) > 0) index de retour; jeter nouvelle InvalidOperationException ("L'index d'insertion n'a pas été trouvé"); private void Insert (T [] itemArray, int indexInsertingAt, int indexInsertingFrom) // itemArray = 0 1 2 4 5 6 3 7 // insertingAt = 3 // insertingFrom = 6 // actions // 1: stocke l'index dans temp temp = 4 // 2: Fixe l'index à pour index de -> 0 1 2 3 5 6 3 7 temp = 4 // 3: Revient en arrière d'index de à index à +1. // Décale les valeurs de gauche à droite. une fois que. // 0 1 2 3 5 6 6 7 temp = 4 // 0 1 2 3 5 5 6 7 temp = 4 // 4: Écriture de la valeur temp dans l'index à + 1. // 0 1 2 3 4 5 6 7 temp = 4 // Étape 1. T temp = itemArray [indexInsertingAt]; // Étape 2. itemArray [indexInsertingAt] = itemArray [indexInsertingFrom]; // Étape 3. pour (int current = indexInsertingFrom; current> indexInsertingAt; current--) itemArray [current] = itemArray [current - 1]; // Étape 4. itemArray [indexInsertingAt + 1] = temp; | Comportement | Trie le tableau d'entrée en utilisant l'algorithme de tri par sélection. | ||
| Complexité | Meilleur cas | Cas moyen | Pire cas |
| Temps | Sur) | Sur2) | Sur2) |
| Espace | O (1) | O (1) | O (1) |
Le type de sélection est une sorte d'hybride entre le type à bulle et le type à insertion. Comme le tri par bulles, il traite le tableau en itérant du début à la fin, en sélectionnant une valeur et en le déplaçant au bon endroit. Cependant, contrairement au tri par bulles, il sélectionne la plus petite valeur non triée plutôt que la plus grande. Comme pour le tri par insertion, la partie triée du tableau est le début du tableau, alors qu'avec le tri par bulle, la partie triée est à la fin..
Voyons comment cela fonctionne en utilisant le même tableau non trié que nous utilisons.
Tableau d'entiers non trié Lors du premier passage, l'algorithme va tenter de trouver la plus petite valeur du tableau et de le placer dans le premier index. Ceci est effectué par le FindIndexOfSmallestFromIndex, qui trouve l'index de la plus petite valeur non triée à partir de l'index fourni.
Avec un si petit tableau, nous pouvons dire que la première valeur, trois, est la plus petite valeur et qu’elle se trouve déjà au bon endroit. À ce stade, nous savons que la valeur dans l'index de tableau zéro est la plus petite valeur et est donc dans le bon ordre de tri. Alors maintenant, nous pouvons commencer à passer deux fois cette fois-ci en regardant les entrées de tableau un à n-1.
La deuxième passe déterminera que quatre est la plus petite valeur de la plage non triée et échangera la valeur de la deuxième tranche avec la valeur de la tranche dans laquelle quatre ont été conservées (en remplaçant les quatre et les sept). Après le passage deux terminé, la valeur quatre sera insérée dans sa position triée.
Tableau après deuxième passage La plage triée va maintenant de l'index zéro à l'index un, et la plage non triée est de l'index deux à n-1. À la fin de chaque passe suivante, la partie triée de la matrice devient plus grande et la partie non triée devient plus petite. Si aucune insertion n'est effectuée à un moment donné, le tableau est connu pour être trié. Sinon, le processus continue jusqu'à ce que tout le tableau soit connu pour être trié.
Après deux autres passes, le tableau est trié:
Tableau trié public void Sort (T [] items) int triRangeRangeEnd = 0; while (sorteRangeFin < items.Length) int nextIndex = FindIndexOfSmallestFromIndex(items, sortedRangeEnd); Swap(items, sortedRangeEnd, nextIndex); sortedRangeEnd++; private int FindIndexOfSmallestFromIndex(T[] items, int sortedRangeEnd) T currentSmallest = items[sortedRangeEnd]; int currentSmallestIndex = sortedRangeEnd; for (int i = sortedRangeEnd + 1; i < items.Length; i++) if (currentSmallest.CompareTo(items[i]) > 0) currentSmallest = items [i]; currentSmallestIndex = i; return currentSmallestIndex;
| Comportement | Trie le tableau d'entrée en utilisant l'algorithme de tri par fusion. | ||
| Complexité | Meilleur cas | Cas moyen | Pire cas |
| Temps | O (n log n) | O (n log n) | O (n log n) |
| Espace | Sur) | Sur) | Sur) |
Jusqu'à présent, nous avons vu des algorithmes fonctionnant en traitant linéairement le tableau. Ces algorithmes ont l'avantage de fonctionner avec très peu de surcharge de mémoire mais au prix d'une complexité d'exécution quadratique. Avec le tri par fusion, nous allons voir notre premier algorithme diviser pour régner.
Les algorithmes de division et de conquête fonctionnent en décomposant de gros problèmes en problèmes plus petits et plus faciles à résoudre. Nous voyons ces types d'algorithmes dans la vie quotidienne. Par exemple, nous utilisons un algorithme diviser pour régner lorsque nous recherchons un annuaire téléphonique.
Si vous voulez trouver le nom Erin Johnson dans un annuaire, vous ne commencerez pas par A et n’avancez pas page par page. Au contraire, vous ouvririez probablement l’annuaire au milieu. Si vous ouvriez aux M, vous retourneriez quelques pages, peut-être un peu trop loin - les H, peut-être. Ensuite, vous basculeriez en avant. Et vous continuiez à faire des va-et-vient de plus en plus petits jusqu'à ce que vous trouviez finalement la page que vous vouliez (ou si proche du fait que basculer en avant était logique).
Quelle est l'efficacité des algorithmes diviser pour régner?
Supposons que l'annuaire téléphonique compte 1000 pages. Lorsque vous ouvrez au milieu, vous avez divisé le problème en deux problèmes de 500 pages. En supposant que vous n'êtes pas sur la bonne page, vous pouvez maintenant choisir le côté approprié pour rechercher et réduire à nouveau le problème en deux. Votre espace de problème est maintenant de 250 pages. Comme le problème est réduit de moitié, nous pouvons voir qu’un annuaire téléphonique de 1 000 pages peut être consulté en seulement dix pages. Cela représente 1% du nombre total de tours de page nécessaires pour effectuer une recherche linéaire..
Le tri par fusion consiste à couper le tableau en deux, encore et encore, jusqu'à ce que chaque élément ne compte plus qu'un élément. Ensuite, ces éléments sont rassemblés (fusionnés) dans l'ordre de tri.
Commençons par le tableau suivant:
Tableau d'entiers non trié Et maintenant nous avons coupé le tableau en deux:
Tableau non trié coupé en deux Maintenant, ces deux tableaux sont coupés en deux à plusieurs reprises jusqu'à ce que chaque élément soit autonome:
Tableau non trié coupé en deux jusqu'à ce que chaque index soit indépendant Avec le tableau maintenant divisé en parties les plus petites possibles, le processus de fusion de ces parties dans l'ordre de tri se produit.
Tableau trié par groupes de deux Les éléments individuels deviennent des groupes triés de deux, ces groupes de deux se fusionnent pour former des groupes de quatre triés, puis finalement, ils sont tous fusionnés en tant que tableau trié final..
Tableau trié en groupes de quatre (en haut) et le tri terminé (en bas) Prenons un moment pour réfléchir aux opérations individuelles que nous devons mettre en œuvre:
Trier méthode fait cela.Fusionner méthode fait cela.L'un des critères de performance du tri par fusion est que, contrairement aux algorithmes de tri linéaire, le tri par fusion va exécuter toute sa logique de fractionnement et de fusion, y compris les allocations de mémoire, même si le tableau est déjà trié. Bien que ses performances dans le pire des cas soient meilleures que celles des algorithmes de tri linéaire, ses meilleures performances seront toujours pires. Cela signifie que ce n'est pas un candidat idéal lors du tri de données connues pour être presque triées; par exemple, lors de l'insertion de données dans un tableau déjà trié.
public void Sort (T [] items) if (items.Length <= 1) return; int leftSize = items.Length / 2; int rightSize = items.Length - leftSize; T[] left = new T[leftSize]; T[] right = new T[rightSize]; Array.Copy(items, 0, left, 0, leftSize); Array.Copy(items, leftSize, right, 0, rightSize); Sort(left); Sort(right); Merge(items, left, right); private void Merge(T[] items, T[] left, T[] right) int leftIndex = 0; int rightIndex = 0; int targetIndex = 0; int remaining = left.Length + right.Length; while(remaining > 0) if (leftIndex> = left.Length) items [targetIndex] = right [rightIndex ++]; else if (rightIndex> = right.Length) items [targetIndex] = left [leftIndex ++]; else if (left [leftIndex] .CompareTo (right [rightIndex]) < 0) items[targetIndex] = left[leftIndex++]; else items[targetIndex] = right[rightIndex++]; targetIndex++; remaining--;
| Comportement | Trie le tableau d'entrée en utilisant l'algorithme de tri rapide. | ||
| Complexité | Meilleur cas | Cas moyen | Pire cas |
| Temps | O (n log n) | O (n log n) | Sur2) |
| Espace | O (1) | O (1) | O (1) |
Le tri rapide est un autre algorithme de tri par division. Celui-ci fonctionne en effectuant de manière récursive l'algorithme suivant:
Faisons un tri rapide sur le tableau suivant:
Tableau d'entiers non trié La première étape dit que nous sélectionnons le point de partition en utilisant un index aléatoire. Dans l'exemple de code, cela se fait à cette ligne:
int pivotIndex = _pivotRng.Next (gauche, droite);
Choisir un index de partition aléatoire Maintenant que nous connaissons l’indice de partition (quatre), nous regardons la valeur à ce point (six) et nous déplaçons les valeurs du tableau de sorte que tout ce qui est inférieur à la valeur se trouve à gauche du tableau et tout le reste (valeurs supérieures). ou égal) est déplacé vers le côté droit du tableau. Gardez à l'esprit que le déplacement des valeurs peut changer l'index dans lequel la valeur de partition est stockée (nous le verrons bientôt).
L'échange des valeurs est effectué par la méthode de partition dans l'exemple de code..
Déplacement des valeurs à gauche et à droite de la valeur de la partition À ce stade, nous savons que six est au bon endroit dans le tableau. Nous le savons parce que chaque valeur à gauche est inférieure à la valeur de la partition et que tout ce qui se trouve à droite est supérieure ou égale à la valeur de la partition. Maintenant, nous répétons ce processus sur les deux partitions non triées de la matrice.
La répétition est effectuée dans l'exemple de code en appelant de manière récursive la méthode quicksort avec chacune des partitions de la matrice. Notez que cette fois le tableau de gauche est partitionné à l'index un avec la valeur cinq. Le processus de déplacement des valeurs vers leurs positions appropriées déplace la valeur cinq vers un autre index. Je signale ceci pour renforcer le point que vous sélectionnez une valeur de partition, pas un index de partition.
Répéter le pivot et la partition Tri rapide à nouveau:
Répéter le pivot et partitionner à nouveau Et un tri rapide une dernière fois:
Répéter le pivot et partitionner à nouveau Avec seulement une valeur non triée, et puisque nous savons que toutes les autres valeurs sont triées, le tableau est entièrement trié.
Random _pivotRng = new Random (); public void Sort (T [] items) quicksort (items, 0, items.Length - 1); private void quicksort (T [] éléments, int gauche, int droite) if (left < right) int pivotIndex = _pivotRng.Next(left, right); int newPivot = partition(items, left, right, pivotIndex); quicksort(items, left, newPivot - 1); quicksort(items, newPivot + 1, right); private int partition(T[] items, int left, int right, int pivotIndex) T pivotValue = items[pivotIndex]; Swap(items, pivotIndex, right); int storeIndex = left; for (int i = left; i < right; i++) if (items[i].CompareTo(pivotValue) < 0) Swap(items, i, storeIndex); storeIndex += 1; Swap(items, storeIndex, right); return storeIndex;
