Tri par sélection en Java

1. Introduction

Dans ce didacticiel, nous allons apprendre le tri de sélection , voir son implémentation en Java et analyser ses performances.

2. Aperçu de l'algorithme

Le tri par sélection commence par l'élément en première position d' un tableau non trié et parcourt les éléments suivants pour trouver le plus petit élément . Une fois trouvé, le plus petit élément est échangé avec l'élément en 1ère position.

L'algorithme passe ensuite à l'élément en 2ème position et parcourt les éléments suivants pour trouver l'index du 2ème plus petit élément. Une fois trouvé, le deuxième plus petit élément est échangé avec l'élément en 2ème position.

Ce processus se poursuit jusqu'à ce que nous atteignions le n-1e élément du tableau, ce qui place le n-1e plus petit élément à la n-1e position. Le dernier élément se met automatiquement en place, à la n-1e itération, triant ainsi le tableau.

Nous trouvons le plus grand élément au lieu du plus petit élément pour trier le tableau par ordre décroissant.

Voyons un exemple de tableau non trié et trions-le par ordre croissant pour comprendre visuellement l'algorithme.

2.1. Un exemple

Considérez le tableau non trié suivant:

int [] arr = {5, 4, 1, 6, 2}

Itération 1

Compte tenu du fonctionnement de l'algorithme ci-dessus, nous commençons par l'élément en 1ère position - 5 - et parcourons tous les éléments suivants pour trouver le plus petit élément - 1. Nous échangeons ensuite le plus petit élément avec l'élément en 1ère position.

Le tableau modifié ressemble maintenant à:

{1, 4, 5, 6, 2}

Total des comparaisons effectuées: 4

Itération 2

Dans la deuxième itération, nous passons au 2ème élément - 4 - et parcourons les éléments suivants pour trouver le second plus petit élément - 2. Nous échangeons ensuite le second plus petit élément avec l'élément en 2ème position.

Le tableau modifié ressemble maintenant à:

{1, 2, 5, 6, 4}

Total des comparaisons effectuées: 3

En continuant de la même manière, nous avons les itérations suivantes:

Itération 3

{1, 2, 4, 6, 5}

Total des comparaisons effectuées: 2

Itération 4

{1, 2, 4, 5, 6}

Total des comparaisons effectuées: 1

3. Mise en œuvre

Implémentons le tri de sélection en utilisant quelques boucles for :

public static void sortAscending(final int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int minElementIndex = i; for (int j = i + 1; j  arr[j]) { minElementIndex = j; } } if (minElementIndex != i) { int temp = arr[i]; arr[i] = arr[minElementIndex]; arr[minElementIndex] = temp; } } }

Bien sûr, pour l'inverser, nous pourrions faire quelque chose d'assez similaire:

public static void sortDescending(final int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int maxElementIndex = i; for (int j = i + 1; j < arr.length; j++) { if (arr[maxElementIndex] < arr[j]) { maxElementIndex = j; } } if (maxElementIndex != i) { int temp = arr[i]; arr[i] = arr[maxElementIndex]; arr[maxElementIndex] = temp; } } }

Et avec un peu plus d'huile de coude, nous pourrions les combiner en utilisant des comparateurs .

4. Aperçu des performances

4.1. Temps

Dans l'exemple que nous avons vu précédemment, la sélection du plus petit élément nécessitait un total de (n-1) comparaisons suivies d'un basculement vers la 1ère position. De même, la sélection du plus petit élément suivant nécessitait des comparaisons totales (n-2) suivies d'un échange en 2ème position, et ainsi de suite.

Ainsi, à partir de l'indice 0, on effectue n-1, n-2, n-3, n-4…. 1 comparaisons. Le dernier élément se met automatiquement en place en raison des itérations et des échanges précédents.

Mathématiquement, la somme des n-1 premiers nombres naturels nous dira combien de comparaisons nous avons besoin pour trier un tableau de taille n en utilisant le tri par sélection.

La formule de la somme de n nombres naturels est n (n + 1) / 2 .

Dans notre cas, nous avons besoin de la somme des n-1 premiers nombres naturels. Par conséquent, nous remplaçons n par n-1 dans la formule ci-dessus pour obtenir:

(n-1) (n-1 + 1) / 2 = (n-1) n / 2 = (n ^ 2-n) / 2

Au fur et à mesure que n ^ 2 croît de façon proéminente à mesure que n grandit, nous considérons la puissance plus élevée de n comme la référence de performance, ce qui donne à cet algorithme une complexité temporelle de O (n ^ 2).

4.2. Espace

En termes de complexité de l'espace auxiliaire, le tri par sélection nécessite une variable supplémentaire pour conserver temporairement la valeur à permuter. Par conséquent, la complexité spatiale de Selection Sort est O (1) .

5. Conclusion

Selection Sort est un algorithme de tri très simple à comprendre et à mettre en œuvre. Malheureusement, sa complexité temporelle quadratique en fait une technique de tri coûteuse . De plus, comme l'algorithme doit parcourir chaque élément, le meilleur cas, le cas moyen et le pire des cas de complexité temporelle sont les mêmes .

D'autres techniques de tri comme le tri par insertion et le tri par coquille ont également une complexité temporelle quadratique dans le pire des cas, mais elles fonctionnent mieux dans les cas les meilleurs et les cas moyens.

Consultez le code complet pour le tri par sélection sur GitHub.