Guide de l'algorithme de tri sur place fonctionne avec une implémentation Java

1. Introduction

Dans ce didacticiel, nous expliquerons comment fonctionne l'algorithme de tri sur place.

2. Algorithmes en place

Les algorithmes en place sont ceux qui n'ont pas besoin de structure de données auxiliaire pour transformer les données d'entrée. Fondamentalement, cela signifie que l'algorithme n'utilise pas d'espace supplémentaire pour la manipulation des entrées. Il remplace pratiquement l'entrée par la sortie.

Cependant, en réalité, l'algorithme peut en fait nécessiter un petit espace supplémentaire non constant pour les variables auxiliaires. La complexité de cet espace est dans la plupart des cas O (log n) , bien que parfois quelque chose de moins que linéaire soit autorisé.

3. Pseudocode

Voyons maintenant un pseudo-code et comparons l'algorithme en place avec l'algorithme déplacé.

Nous supposerons que nous voulons inverser un tableau de n nombres.

3.1. Algorithme en place

Si nous réfléchissons au problème, nous verrons que nous avons un tableau d'entrée et un tableau inversé en sortie. En fin de compte, nous n'avons pas réellement besoin de notre tableau d'origine, seulement du tableau inversé.

Alors, pourquoi ne pas écraser l'entrée au lieu de déplacer ses valeurs vers le tout nouveau tableau, car cela pourrait ressembler à une méthode la plus évidente? Pour ce faire, nous n'aurons besoin que d'une variable supplémentaire pour stocker temporairement les valeurs avec lesquelles nous travaillons actuellement:

reversInPlace(array A[n]) for i from 0 to n/2 temp = A[i] A[i] = A[n - 1 - i] A[n - 1 - i] = temp

Il est à noter que quelle que soit la taille du tableau, l'espace supplémentaire dont nous avons besoin sera toujours O (1) dans ce cas.

L'illustration montre que nous avons besoin de moins d'étapes que dans le cas précédent:

3.2. Algorithme hors de propos

D'un autre côté, nous pouvons également le faire d'une manière assez simple et plus évidente. Nous pouvons créer un nouveau tableau de la même taille, copier les valeurs de l'original dans l'ordre correspondant, puis supprimer le tableau d'origine:

reverseOutOfPlace(array A[n]) create new array B[n] for i from 0 to n - 1 B[i] = A[i] delete A return B

Bien que cela fasse ce que nous voulions, ce n'est pas assez efficace. Nous avons besoin d'espace supplémentaire O (n) puisque nous avons deux tableaux à manipuler . En outre, la création et la suppression d'un nouveau tableau est généralement une opération lente.

Voyons l'illustration du processus:

4. Implémentation Java

Voyons maintenant comment nous pouvons implémenter en Java ce que nous avons appris dans la section précédente.

Tout d'abord, nous allons implémenter un algorithme sur place:

public static int[] reverseInPlace(int A[]) { int n = A.length; for (int i = 0; i < n / 2; i++) { int temp = A[i]; A[i] = A[n - 1 - i]; A[n - 1 - i] = temp; } return A; }

Nous pouvons tester facilement que cela fonctionne comme prévu:

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

Deuxièmement, vérifions l'implémentation de l'algorithme déplacé:

public static int[] reverseOutOfPlace(int A[]) { int n = A.length; int[] B = new int[n]; for (int i = 0; i < n; i++) { B[n - i - 1] = A[i]; } return B; }

Le test est assez simple:

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

5. Exemples

Il existe de nombreux algorithmes de tri qui utilisent une approche en place. Certains d'entre eux sont le tri par insertion, le tri par bulles, le tri par tas, le tri rapide et le tri par shell.Vous pouvez en savoir plus sur eux et vérifier leurs implémentations Java.

En outre, nous devons mentionner le tri en peigne et le tri en tas. Tous ceux-ci ont une complexité spatiale O (log n) .

Il pourrait également être utile d'en savoir plus sur la théorie de la notation Big-O, ainsi que de consulter quelques exemples pratiques de Java sur la complexité de l'algorithme.

6. Conclusion

Dans cet article, nous avons décrit les algorithmes dits en place, illustré leur fonctionnement à l'aide du pseudocode et de quelques exemples, répertorié plusieurs algorithmes qui fonctionnent sur ce principe, et enfin implémenté les exemples de base en Java.

Comme d'habitude, l'intégralité du code peut être trouvée sur GitHub.