Tri par insertion en Java

1. Vue d'ensemble

Dans ce didacticiel, nous allons discuter de l'algorithme de tri par insertion et examiner son implémentation Java .

Le tri par insertion est un algorithme efficace pour commander un petit nombre d'articles. Cette méthode est basée sur la façon dont les joueurs de cartes trient une main de cartes à jouer.

Nous commençons avec une main gauche vide et les cartes posées sur la table. Nous retirons ensuite une carte à la fois de la table et l'insérons dans la bonne position dans la main gauche. Pour trouver la bonne position pour une nouvelle carte, nous la comparons avec le jeu de cartes déjà trié dans la main, de droite à gauche.

Commençons par comprendre les étapes de l'algorithme sous forme de pseudocode.

2. Pseudocode

Nous allons présenter notre pseudocode pour le tri par insertion comme une procédure appelée INSERTION-SORT , prenant comme paramètre un tableau A [1 .. n] de n éléments à trier. L'algorithme trie le tableau d'entrée sur place (en réorganisant les éléments dans le tableau A).

Une fois la procédure terminée, le tableau d'entrée A contient une permutation de la séquence d'entrée mais dans l'ordre trié:

INSERTION-SORT(A) for i=2 to A.length key = A[i] j = i - 1 while j > 0 and A[j] > key A[j+1] = A[j] j = j - 1 A[j + 1] = key

Passons brièvement en revue l'algorithme ci-dessus.

L'index i indique la position de l'élément courant dans le tableau à traiter.

On part du deuxième élément car par définition un tableau avec un élément est considéré comme trié. L'élément à l'index i est appelé une clé . Une fois que vous avez la clé, la deuxième partie de l'algorithme consiste à trouver son index correct. Si la clé est plus petite que la valeur de l'élément à l'index j , la clé se déplace d'une position vers la gauche. Le processus se poursuit jusqu'au cas où nous atteignons un élément plus petit que la clé.

Il est important de noter qu'avant de démarrer l'itération pour trouver la position correcte de la clé à l'index i , le tableau A [1 .. j - 1] est déjà trié .

3. Mise en œuvre impérative

Pour le cas impératif, nous allons écrire une fonction appelée insertionSortImperative , en prenant comme paramètre un tableau d'entiers. La fonction commence à parcourir le tableau à partir du deuxième élément.

A tout moment donné au cours de l'itération, nous pourrions considérer ce tableau comme étant logiquement divisé en deux parties; le côté gauche étant celui trié et le côté droit contenant les éléments non encore triés.

Une note importante ici est qu'après avoir trouvé la position correcte à laquelle nous insérerons le nouvel élément, nous déplaçons (et ne les échangeons pas) vers la droite pour libérer un espace pour celui-ci.

public static void insertionSortImperative(int[] input) { for (int i = 1; i 
    
     = 0 && input[j] > key) { input[j + 1] = input[j]; j = j - 1; } input[j + 1] = key; } }
    

Ensuite, créons un test pour la méthode ci-dessus:

@Test public void givenUnsortedArray_whenInsertionSortImperative_thenSortedAsc() { int[] input = {6, 2, 3, 4, 5, 1}; InsertionSort.insertionSortImperative(input); int[] expected = {1, 2, 3, 4, 5, 6}; assertArrayEquals("the two arrays are not equal", expected, input); }

Le test ci-dessus prouve que l'algorithme trie correctement dans l'ordre croissant le tableau d'entrée .

4. Mise en œuvre récursive

La fonction pour le cas récursif est appelée insertionSortR ecursive et accepte en entrée un tableau d'entiers (comme pour le cas impératif).

La différence ici avec le cas impératif (malgré le fait qu'il soit récursif) est qu'il appelle une fonction surchargée avec un deuxième argument égal au nombre d'éléments à trier.

Comme nous voulons trier le tableau complet, nous passerons un nombre d'éléments égal à sa longueur:

public static void insertionSortRecursive(int[] input) { insertionSortRecursive(input, input.length); }

Le cas récursif est un peu plus difficile. Le cas de base se produit lorsque nous tentons de trier un tableau avec un élément. Dans ce cas, nous ne faisons rien.

Tous les appels récursifs suivants trient une partie prédéfinie du tableau d'entrée - à partir du deuxième élément jusqu'à ce que nous atteignions la fin du tableau:

private static void insertionSortRecursive(int[] input, int i) { if (i <= 1) { return; } insertionSortRecursive(input, i - 1); int key = input[i - 1]; int j = i - 2; while (j>= 0 && input[j] > key) { input[j + 1] = input[j]; j = j - 1; } input[j + 1] = key; }

Et voici à quoi ressemble la pile d'appels pour un tableau d'entrée de 6 éléments:

insertionSortRecursive(input, 6) insertionSortRecursive(input, 5) and insert the 6th item into the sorted array insertionSortRecursive(input, 4) and insert the 5th item into the sorted array insertionSortRecursive(input, 3) and insert the 4th item into the sorted array insertionSortRecursive(input, 2) and insert the 3rd item into the sorted array insertionSortRecursive(input, 1) and insert the 2nd item into the sorted array

Voyons également le test pour cela:

@Test public void givenUnsortedArray_whenInsertionSortRecursively_thenSortedAsc() { int[] input = {6, 4, 5, 2, 3, 1}; InsertionSort.insertionSortRecursive(input); int[] expected = {1, 2, 3, 4, 5, 6}; assertArrayEquals("the two arrays are not equal", expected, input); }

Le test ci-dessus prouve que l'algorithme trie correctement dans l'ordre croissant le tableau d'entrée .

5. Complexité temporelle et spatiale

Le temps nécessaire à l'exécution de la procédure INSERTION-SORT est O (n ^ 2) . Pour chaque nouvel élément, nous parcourons de droite à gauche la partie déjà triée du tableau pour trouver sa position correcte. Ensuite, nous l'insérons en déplaçant les éléments d'une position vers la droite.

L'algorithme trie sur place donc sa complexité spatiale est O (1) pour l'implémentation impérative et O (n) pour l'implémentation récursive.

6. Conclusion

Dans ce didacticiel, nous avons vu comment implémenter le tri par insertion.

Cet algorithme est utile pour trier un petit nombre d'éléments. Cela devient inefficace lors du tri des séquences d'entrée contenant plus de 100 éléments.

Gardez à l'esprit que malgré sa complexité quadratique, il effectue le tri sur place sans avoir besoin d'espace auxiliaire comme c'est le cas pour le tri par fusion .

Le code entier peut être trouvé sur GitHub.