Tri Shell en Java

1. Introduction

Dans ce didacticiel, nous décrirons l'algorithme de tri Shell en Java.

2. Présentation du tri Shell

2.1. La description

Décrivons d'abord l'algorithme de tri Shell pour savoir ce que nous essayons d'implémenter.

Le tri Shell est basé sur l'algorithme de tri par insertion et appartient au groupe des algorithmes très efficaces. En général, l'algorithme divise un ensemble d'origine en sous-ensembles plus petits, puis chacun d'entre eux est trié à l'aide du tri par insertion .

Mais la façon dont cela crée les sous-ensembles n'est pas simple. Il ne choisit pas les éléments voisins pour former un sous-ensemble comme on pourrait s'y attendre. Au lieu de cela, le tri shell utilise ce que l'on appelle l' intervalle ou l' écart pour la création de sous-ensembles. Par exemple, si nous avons l'écart I , cela signifie qu'un sous-ensemble contiendra les éléments séparés par des positions I.

Premièrement, l'algorithme trie les éléments qui sont éloignés les uns des autres. Ensuite, l'écart devient plus petit et des éléments plus proches sont comparés. De cette façon, certains éléments qui ne sont pas dans une position correcte peuvent être positionnés plus rapidement que si nous faisions les sous-ensembles à partir des éléments voisins.

2.2. Un exemple

Voyons cela dans l'exemple avec les espaces de 3 et 1 et la liste non triée de 9 éléments:

Si nous suivons la description ci-dessus, dans la première itération, nous aurons trois sous-ensembles avec 3 éléments (mis en évidence par la même couleur):

Après avoir trié chacun des sous-ensembles dans la première itération, la liste ressemblerait à ceci:

Nous pouvons noter que, bien que nous n'ayons pas encore de liste triée, les éléments sont désormais plus proches des positions souhaitées.

Enfin, nous devons faire un autre tri avec l'incrément d'un et c'est en fait un tri d'insertion de base. Le nombre d'opérations de décalage que nous devons effectuer pour trier une liste est maintenant plus petit qu'il ne le serait si nous n'avions pas fait la première itération:

2.3. Choix des séquences d'intervalle

Comme nous l'avons mentionné, le tri shell a une manière unique de choisir les séquences d'intervalle. C'est une tâche difficile et nous devons faire attention à ne pas choisir trop ou trop peu de lacunes. Plus de détails peuvent être trouvés dans la liste des séquences d'intervalle les plus proposées.

3. Mise en œuvre

Jetons maintenant un œil à l'implémentation. Nous utiliserons la séquence originale de Shell pour les incréments d'intervalle:

N/2, N/4, …, 1 (continuously dividing by 2)

La mise en œuvre elle-même n'est pas trop complexe:

public void sort(int arrayToSort[]) { int n = arrayToSort.length; for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arrayToSort[j - gap] > key) { arrayToSort[j] = arrayToSort[j - gap]; j -= gap; } arrayToSort[j] = key; } } }

Nous avons d'abord créé une séquence d'espacement avec une boucle for, puis effectué le tri d'insertion pour chaque taille d'espace.

Maintenant, nous pouvons facilement tester notre méthode:

@Test public void givenUnsortedArray_whenShellSort_thenSortedAsc() { int[] input = {41, 15, 82, 5, 65, 19, 32, 43, 8}; ShellSort.sort(input); int[] expected = {5, 8, 15, 19, 32, 41, 43, 65, 82}; assertArrayEquals("the two arrays are not equal", expected, input); }

4. Complexité

En général, l'algorithme de tri Shell est très efficace avec les listes de taille moyenne . La complexité est difficile à déterminer car elle dépend beaucoup de la séquence d'intervalles, mais la complexité temporelle varie entre O (N) et O (N ^ 2) .

La complexité spatiale dans le pire des cas est O (N) avec un espace auxiliaire O (1) .

5. Conclusion

Dans ce didacticiel, nous avons décrit le tri Shell et illustré comment nous pouvons l'implémenter en Java.

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