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 ?
L devient égal à
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 n
est le nombre d'éléments, quand n = 10
le 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 a
et b
si a
est 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]
. 5
est plus que 3
- tout va bien. Mais 2
c'est moins que 5
. Cependant, [3, 2, 5]
nécessite un autre passage, puisque3 > 2
et ils doivent être échangés. Parce que nous utilisons une boucle dans une boucle, la complexité de notre algorithme augmente. Étant donné n
les é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 n
change. 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:
Tri de sélection
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:
Tri par insertion
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));
Matériel sur ce sujet:
Sorte de coquille
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));
Matériel sur ce sujet:
Tri par fusion
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'écritO(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:
Tri par comptage et tri par base
Un autre algorithme de tri intéressant est le tri par comptage. La complexité algorithmique est iciO(n+k)
, où n
est le nombre d'éléments et k
est 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 :
Tri rapide
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 pivot
vers la gauche de pivot
, et les plus grandes — vers la droite. Pour ce faire, nous déplaçons d'abord le L
marqueur jusqu'à ce que nous trouvions une valeur supérieure à pivot
. Si aucune valeur inférieure n'est trouvée, alorspivot
. Ensuite, nous déplaçons le
R
marqueur jusqu'à ce que nous trouvions une valeur inférieure à
pivot
. Si aucune valeur supérieure n'est trouvée, alors
R
devient égal à
pivot
. Ensuite, si le
L
marqueur est avant le
R
marqueur 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
L
vers la droite de 1, et nous nous déplaçons
R
vers la gauche de 1. Lorsque le
L
marqueur se déplace au-delà du
R
marqueur, 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
pivot
au 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
L
vers la
pivot
position, car
L
nous 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
R
marqueur. 3 est inférieur à 6, donc placez le
R
marqueur 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
L
marqueur est sur 3. Le
R
marqueur est sur 6. N'oubliez pas que nous déplaçons les marqueurs jusqu'à
L
aller au-delà de
R
. Passer
L
au 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
L
marqueur vers 1, car nous pouvons déplacer
L
tant que le
L
le marqueur pointe vers un nombre inférieur à
pivot
. Mais nous ne pouvons pas nous éloigner
R
de 6, car nous ne pouvons déplacer R que si le
R
marqueur 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
).
L
passe
pivot
et s'arrête de bouger.
R
ne bouge pas. Nous n'effectuons pas d'échange. Maj
L
et
R
d'une position. Écrivez le
R
marqueur sous 1. Le
L
marqueur est hors limites. Parce que
L
c'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
pivot
et recommencez tout :)
Si l'avant-dernier chiffre est 7 :Déplacez le
L
marqueur 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
L
marqueur est maintenant décalé à 7, et le
R
marqueur est décalé à 3. Cela n'a pas de sens de trier la partie de
L
jusqu'à la fin, car il n'y a qu'un seul élément. Cependant, nous envoyons la pièce de 4 au
R
marqueur pour le tri. On choisit a
pivot
et 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
pivot
que l'autre élément ne soit permuté dans la partie avant
pivot
.
GO TO FULL VERSION