Le tri est l'une des opérations de base que nous effectuons sur les objets. Même dans l'enfance, les enfants apprennent à trier au fur et à mesure qu'ils développent leurs capacités de réflexion. Les ordinateurs et les logiciels ne font pas exception. Il existe une grande variété d' algorithmes de tri en Java . Je vous suggère de vérifier ce qu'ils sont et comment ils fonctionnent. Et si on vous posait des questions sur l'un d'entre eux lors d'un entretien un jour ?
Introduction
Le tri des éléments fait partie des catégories d'algorithmes qu'un développeur doit connaître. Si l'informatique n'était autrefois pas prise au sérieux lorsque j'étais à l'école, les étudiants d'aujourd'hui doivent être capables d'implémenter et de comprendre des algorithmes de tri. Les algorithmes de base, les plus simples, sont implémentés à l'aide d'une boucle for . Naturellement, pour trier une collection d'éléments, comme un tableau, vous devez d'une manière ou d'une autre parcourir la collection. Par exemple:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
Que peut-on dire de ce segment de code ? Nous avons une boucle dans laquelle nous changeons l'indice ( int i) de 0 au dernier élément du tableau. En fait, nous prenons simplement chaque élément du tableau et imprimons son contenu. Plus il y a d'éléments dans le tableau, plus le code mettra du temps à se terminer. Autrement dit, si nest le nombre d'éléments, quand n = 10le programme prendra deux fois plus de temps à s'exécuter que quand n = 5. Si notre programme a une seule boucle, le temps d'exécution croît linéairement : plus il y a d'éléments, plus le temps d'exécution est long. Il s'avère que l'algorithme ci-dessus fonctionne en temps linéaire (une fonction linéaire de n). Dans de tels cas, on dit que la complexité de l'algorithme est "O(n)". Cette notation est aussi appelée "grand O" ou "comportement asymptotique". Mais tu peux juste te rappeler "
L'algorithme de tri le plus simple (tri à bulles)
Supposons que nous ayons un tableau et que nous puissions le parcourir. Super. Essayons maintenant de le trier par ordre croissant. Qu'est-ce que cela signifie? Cela signifie que, étant donné deux éléments (par exemple, a = 6, b = 5), nous devons réorganiser aet bsi aest supérieur à b(if a > b). Qu'est-ce que cela signifie lorsque nous utilisons un index pour travailler avec une collection (comme c'est le cas avec un tableau) ? Cela signifie que si l'élément avec l'indice a est plus grand que l'élément avec l'indice b( array[a] > array[b]), alors les éléments doivent être permutés. Il existe différentes manières de changer de place. Mais nous allons utiliser une technique simple, compréhensible et facile à retenir :
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Maintenant, nous pouvons écrire ce qui suit :
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
Comme vous pouvez le voir, les éléments ont vraiment été permutés. Nous avons commencé avec l'index 1, car si le tableau n'a qu'un seul élément, l'expression array[i] < array[i-1]est invalide pour index 0. Cela nous protège également des cas où le tableau n'a pas d'éléments ou un seul élément, et cela rend le code plus beau. Mais le tableau résultant n'est toujours pas trié, car une passe ne suffit pas pour effectuer le tri. Nous devrons ajouter une autre boucle dans laquelle nous effectuerons des passes encore et encore jusqu'à ce que nous obtenions un tableau trié :
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
Nous avons donc terminé notre premier algorithme de tri. Nous répétons la boucle externe ( while) jusqu'à ce que nous décidions qu'aucune autre itération n'est nécessaire. Par défaut, avant chaque nouvelle itération, nous supposons que notre tableau est trié et nous n'avons plus besoin de boucler. En conséquence, nous parcourons séquentiellement les éléments et vérifions cette hypothèse. Mais si les éléments ne sont pas dans l'ordre, alors nous échangeons des éléments et comprenons que nous n'avons plus aucune garantie que les éléments sont dans le bon ordre. Cela signifie que nous devons effectuer une autre itération. Par exemple, supposons que nous ayons [3, 5, 2]. 5est plus que 3- tout va bien. Mais 2c'est moins que 5. Cependant, [3, 2, 5]nécessite un autre passage, puisque3 > 2et ils doivent être échangés. Parce que nous utilisons une boucle dans une boucle, la complexité de notre algorithme augmente. Étant donné nles éléments, il devient n * n, c'est-à-dire O(n^2). C'est ce qu'on appelle la complexité quadratique. En général, nous ne pouvons pas savoir exactement combien d'itérations seront nécessaires. L'expression de la complexité d'un algorithme montre comment la complexité augmente dans le pire des cas. C'est-à-dire qu'il indique de combien le temps d'exécution augmentera à mesure que le nombre d'éléments nchange. Le tri à bulles est l'un des algorithmes de tri les plus simples et les plus inefficaces. Il est aussi parfois appelé "sorte stupide". Matériel sur ce sujet:
Un autre algorithme de tri est le tri par sélection. Il a également une complexité quadratique, mais nous en reparlerons plus tard. L'idée est donc simple. A chaque passage, on sélectionne le plus petit élément et on le décale au début. De plus, chaque passe commence un pas vers la droite. En d'autres termes, la première passe commence à partir du zéroième élément, la deuxième passe à partir du premier, etc. Cela ressemblera à ceci :
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
Ce tri est instable, car des éléments identiques (quelle que soit la caractéristique que nous utilisons pour trier les éléments) peuvent changer leurs positions relatives. Il y a un bon exemple dans l'article de Wikipedia sur le tri par sélection . Matériel sur ce sujet:
Le tri par insertion a également une complexité quadratique, puisque nous avons à nouveau une boucle dans une boucle. En quoi le tri par insertion est-il différent ? Cet algorithme de tri est "stable". Cela signifie que des éléments identiques ne changeront pas leur ordre relatif. Encore une fois, nous voulons dire identiques en termes de caractéristiques par lesquelles nous trions.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
Sorte de navette
Il existe un autre algorithme de tri simple : le tri navette. Ceci est également connu sous le nom de tri à bulles bidirectionnel ou de tri à shaker. Ces noms alternatifs nous disent que le type de navette ne concerne pas la navette spatiale. Il s'agit de quelque chose qui va et vient. Maintenant, vous pouvez penser à cela quand vous pensez à cet algorithme. Quelle est l'essence de l'algorithme ? L'essence de l'algorithme est que nous itérons de gauche à droite, en échangeant des éléments et en vérifiant si l'un des éléments restant dans l'autre sens doit être échangé.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
Un autre algorithme de tri simple est le tri shell. L'essentiel est similaire au tri à bulles, mais à chaque itération, nous avons un écart différent entre les éléments comparés. Il est réduit de moitié à chaque itération. Voici une implémentation :
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
En plus de ces algorithmes de tri simples, il existe également des algorithmes de tri plus compliqués. Par exemple, tri par fusion. Il y a deux choses à noter. Tout d'abord, la récursivité vient à notre secours ici. Deuxièmement, la complexité de l'algorithme n'est plus quadratique, comme nous en avons l'habitude. La complexité de cet algorithme est logarithmique. Cela s'écrit O(n log n). Alors mettons-le en œuvre. Tout d'abord, nous allons écrire un appel récursif à la méthode sort :
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
Maintenant, ajoutons l'action principale à notre implémentation. Voici notre super méthode :
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
Nous pouvons exécuter notre exemple en appelantmergeSort(array, 0, array.length-1). Comme vous pouvez le voir, le processus se résume à accepter un tableau d'entrée avec des indications sur le début et la fin de la section qui doit être triée. Lorsque le tri commence, ce sont le début et la fin du tableau. Ensuite, nous calculons le délimiteur, qui est l'index où nous allons diviser le tableau. Si le tableau peut être divisé en 2 parties, nous appelons la méthode de tri de manière récursive pour les deux moitiés du tableau. Nous préparons un tampon auxiliaire dans lequel nous insérerons la section triée. Ensuite, définissez l'index au début de la section à trier et commencez à parcourir chaque élément du tampon vide, en le remplissant avec les plus petits éléments. Si l'élément pointé par l'index est inférieur à l'élément pointé par le délimiteur, nous plaçons l'élément dans le tampon et décalons l'index. Sinon, nous plaçons l'élément pointé par le délimiteur dans le tampon et décalons le délimiteur. Dès que le délimiteur dépasse les limites de la section triée ou que nous remplissons tout le tableau, la plage spécifiée est considérée comme triée.Matériel sur ce sujet:
Un autre algorithme de tri intéressant est le tri par comptage. La complexité algorithmique est ici O(n+k), où nest le nombre d'éléments et kest la valeur maximale d'un élément. Cet algorithme a un défaut : nous avons besoin de connaître les valeurs minimales et maximales du tableau. Voici un exemple de tri par comptage :
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
Vous pouvez comprendre que c'est très gênant quand on a besoin de connaître à l'avance les valeurs minimales et maximales. Et nous avons un autre algorithme ici : le tri par base. Je ne présenterai ici l'algorithme que visuellement. Voir le matériel complémentaire pour la mise en œuvre : Matériel :
Eh bien, c'est l'heure du dessert — le tri rapide, l'un des algorithmes de tri les plus célèbres. Il a une complexité logarithmique : O(n log n). Cet algorithme de tri a été développé par Tony Hoare. Fait intéressant, il l'a inventé alors qu'il vivait en Union soviétique, où il a étudié la traduction automatique à l'Université de Moscou et a développé un livre de phrases russe-anglais. De plus, Java utilise une version plus complexe de cet algorithme dans Arrays.sort. Qu'en est-il Collections.sort? Pourquoi ne pas jeter un œil à la façon dont les choses sont triées « sous le capot » ? Voici le code :
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
Tout cela est très effrayant, alors approfondissons-le. Pour le tableau d'entrée ( int[]source), nous créons deux marqueurs : gauche ( L) et droite ( R). Lors du premier appel de méthode, ils correspondent au début et à la fin du tableau. Ensuite, nous identifions l'élément pivot, qui porte bien son nom pivot. Après cela, notre tâche consiste à déplacer les valeurs plus petites que pivotvers la gauche de pivot, et les plus grandes — vers la droite. Pour ce faire, nous déplaçons d'abord le Lmarqueur jusqu'à ce que nous trouvions une valeur supérieure à pivot. Si aucune valeur inférieure n'est trouvée, alors
L devient égal à
pivot. Ensuite, nous déplaçons le
Rmarqueur jusqu'à ce que nous trouvions une valeur inférieure à
pivot. Si aucune valeur supérieure n'est trouvée, alors
Rdevient égal à
pivot. Ensuite, si le
Lmarqueur est avant le
Rmarqueur ou coïncide avec lui, alors nous essayons d'échanger les éléments si l'
Lélément est inférieur à l'
Rélément. Ensuite, nous nous déplaçons
Lvers la droite de 1, et nous nous déplaçons
Rvers la gauche de 1. Lorsque le
Lmarqueur se déplace au-delà du
Rmarqueur, cela signifie que l'échange est terminé : les petites valeurs sont à gauche de
pivot, les grandes valeurs sont à droite de
pivot. Après cela, nous appelons la même méthode de tri de manière récursive sur les sous-tableaux - du début de la section à trier au marqueur de droite, et du marqueur de gauche à la fin de la section à trier. Pourquoi du début au bon repère ? Car à la fin d'une itération, il s'avère que le marqueur droit bouge suffisamment pour devenir la limite de la partie gauche. Cet algorithme est plus complexe qu'un simple tri, il est donc préférable de l'esquisser. Prenez une feuille blanche et écrivez : 4 2 6 7 3. Puis écrivez
pivotau milieu, c'est-à-dire sous le chiffre 6. Encerclez-le. Sous 4, écrivez
L, et sous 3, écrivez
R. 4 moins que 6, 2 moins que 6. Nous finissons par nous déplacer
Lvers la
pivotposition, car
Lnous ne pouvons pas dépasser
pivot, selon l'état. Écrivez à nouveau 4 2 6 7 3. Encerclez 6 (
pivot) et placez
L-le en dessous. Déplacez maintenant le
Rmarqueur. 3 est inférieur à 6, donc placez le
Rmarqueur sur 3. Puisque 3 est inférieur à 6 (
pivot), nous effectuons un
swap. Écrivez le résultat : 4 2 3 7 6. Encerclez 6, car c'est toujours le
pivot. Le
Lmarqueur est sur 3. Le
Rmarqueur est sur 6. N'oubliez pas que nous déplaçons les marqueurs jusqu'à
Laller au-delà de
R. Passer
Lau numéro suivant. Ici, j'aimerais explorer deux possibilités : 1) le cas où l'avant-dernier nombre est 7 et 2) le cas où il s'agit de 1, et non de 7.
Si l'avant-dernier nombre est 1 : Déplacez le
Lmarqueur vers 1, car nous pouvons déplacer
Ltant que le
Lle marqueur pointe vers un nombre inférieur à
pivot. Mais nous ne pouvons pas nous éloigner
Rde 6, car nous ne pouvons déplacer R que si le
Rmarqueur pointe vers un nombre supérieur à
pivot. Nous n'effectuons pas de
swap, car 1 est inférieur à 6. Écrivez la situation actuelle : 4 2 3 1 6. Encerclez 6 (
pivot).
Lpasse
pivotet s'arrête de bouger.
Rne bouge pas. Nous n'effectuons pas d'échange. Maj
Let
Rd'une position. Écrivez le
Rmarqueur sous 1. Le
Lmarqueur est hors limites. Parce que
Lc'est hors limites, on ne fait rien. Mais, nous écrivons à nouveau 4 2 3 1, car c'est notre côté gauche, qui est inférieur à
pivot(6). Sélectionnez le nouveau
pivotet recommencez tout :)
Si l'avant-dernier chiffre est 7 :Déplacez le
Lmarqueur vers 7. Nous ne pouvons pas déplacer le marqueur de droite, car il pointe déjà sur le pivot. 7 est supérieur à
pivot, nous effectuons donc a
swap. Écrivez le résultat : 4 2 3 6 7. Encerclez 6, car c'est le
pivot. Le
Lmarqueur est maintenant décalé à 7, et le
Rmarqueur est décalé à 3. Cela n'a pas de sens de trier la partie de
Ljusqu'à la fin, car il n'y a qu'un seul élément. Cependant, nous envoyons la pièce de 4 au
Rmarqueur pour le tri. On choisit a
pivotet on recommence :) A première vue, il peut sembler que si on additionne beaucoup de valeurs égales à
pivot, alors vous casserez l'algorithme. Mais ce n'est pas le cas. Vous pouvez imaginer des combinaisons délicates et sur le papier vous convaincre que tout est correct et vous émerveiller que des actions aussi simples mettent en œuvre un mécanisme de tri aussi fiable. Le seul inconvénient est que cet algorithme de tri n'est pas stable. Parce qu'un swap peut changer l'ordre relatif d'éléments identiques si l'un d'eux est rencontré avant
pivotque l'autre élément ne soit permuté dans la partie avant
pivot.
La ligne du bas
Ci-dessus, nous avons examiné un ensemble "de gentleman" d'algorithmes de tri implémentés en Java. Les algorithmes sont généralement utiles, tant d'un point de vue appliqué que pour apprendre à penser. Certaines sont plus simples, d'autres plus compliquées. Des gens intelligents ont défendu leurs thèses pour certains. Pour d'autres, ils ont écrit des livres super épais. J'espère que les documents supplémentaires vous aideront à en apprendre encore plus, car cet article n'est qu'un aperçu qui s'est déjà avéré lourd. Et son but est de fournir une petite introduction. Vous pouvez également trouver une introduction aux algorithmes si vous lisez
"Grokking Algorithms ". J'aime aussi la playlist de Jack Brown :
AQA Decision 1 1.01 Tracing an Algorithm . Pour le plaisir, vous pouvez voir des visualisations d'algorithmes lors
du tri.visualgo.net .
Volodymyr is one of those who learned Java development thanks to the CodeGym course, and after studying, got a job in our company. ...
[Lisez la bio complète]
GO TO FULL VERSION