Radix Sort en Java

1. Introduction

Dans ce didacticiel, nous découvrirons Radix Sort, analyserons ses performances et examinerons son implémentation.

Ici, nous nous concentrons sur l'utilisation de Radix Sort pour trier les entiers, mais ce n'est pas limité aux nombres. Nous pouvons également l'utiliser pour trier d'autres types tels que String .

Dans un souci de simplicité, nous allons nous concentrer sur le système décimal dans lequel les nombres sont exprimés en base (base) 10.

2. Aperçu de l'algorithme

Le tri Radix est un algorithme de tri qui trie les nombres en fonction de la position de leurs chiffres. Fondamentalement, il utilise la valeur de position des chiffres dans un nombre. Contrairement à la plupart des autres algorithmes de tri, tels que le tri par fusion, le tri par insertion, le tri par bulles, il ne compare pas les nombres.

Le tri Radix utilise un algorithme de tri stable comme sous-programme pour trier les chiffres. Nous avons utilisé une variante du tri de comptage comme sous-programme ici qui utilise la base pour trier les chiffres dans chaque position. Le tri par comptage est un algorithme de tri stable qui fonctionne bien dans la pratique.

Le tri Radix fonctionne en triant les chiffres du chiffre le moins significatif (LSD) au chiffre le plus significatif (MSD). Nous pouvons également implémenter le tri Radix pour traiter les chiffres de MSD.

3. Un exemple rapide

Voyons comment cela fonctionne avec un exemple. Considérons le tableau suivant:

Itération 1:

Nous allons trier ce tableau en traitant les chiffres du LSD et en nous déplaçant vers MSD.

Commençons donc par les chiffres à un endroit:

Après la première itération, le tableau ressemble maintenant à:

Notez que les nombres ont été triés en fonction des chiffres à un endroit.

Itération 2:

Passons aux chiffres en dizaines:

Maintenant, le tableau ressemble à:

Nous voyons que le nombre 7 a occupé la première position du tableau puisqu'il n'a pas de chiffre à la dizaine. Nous pourrions également penser à cela comme ayant un 0 à la place des dizaines.

Itération 3:

Passons aux chiffres à la position des centaines:

Après cette itération, le tableau ressemble à:

Et l'algorithme s'arrête ici, avec tous les éléments triés.

4. Mise en œuvre

Regardons maintenant l'implémentation.

void sort(int[] numbers) { int maximumNumber = findMaximumNumberIn(numbers); int numberOfDigits = calculateNumberOfDigitsIn(maximumNumber); int placeValue = 1; while (numberOfDigits-- > 0) { applyCountingSortOn(numbers, placeValue); placeValue *= 10; } }

L'algorithme fonctionne en trouvant le nombre maximum dans le tableau, puis en calculant sa longueur. Cette étape nous aide à nous assurer que nous exécutons le sous-programme pour chaque valeur de position.

Par exemple, dans le tableau, [7, 37, 68, 123, 134, 221, 387, 468, 769] , le nombre maximum est 769 et sa longueur est 3.

Donc, nous itérons et appliquons le sous-programme trois fois sur les chiffres dans chaque position:

void applyCountingSortOn(int[] numbers, int placeValue) { int range = 10 // decimal system, numbers from 0-9 // ... // calculate the frequency of digits for (int i = 0; i < length; i++) { int digit = (numbers[i] / placeValue) % range; frequency[digit]++; } for (int i = 1; i 
    
     = 0; i--) { int digit = (numbers[i] / placeValue) % range; sortedValues[frequency[digit] - 1] = numbers[i]; frequency[digit]--; } System.arraycopy(result, 0, numbers, 0, length); }
    

Dans le sous-programme, nous avons utilisé la base (plage) pour compter l'occurrence de chaque chiffre et incrémenter sa fréquence. Ainsi, chaque case dans la plage de 0 à 9 aura une valeur basée sur la fréquence des chiffres. Nous utilisons ensuite la fréquence pour positionner chaque élément dans le tableau. Cela nous aide également à minimiser l'espace requis pour trier le tableau.

Testons maintenant notre méthode:

@Test public void givenUnsortedArray_whenRadixSort_thenArraySorted() { int[] numbers = {387, 468, 134, 123, 68, 221, 769, 37, 7}; RadixSort.sort(numbers); int[] numbersSorted = {7, 37, 68, 123, 134, 221, 387, 468, 769}; assertArrayEquals(numbersSorted, numbers); }

5. Tri Radix vs Tri par comptage

Dans le sous-programme, la longueur du tableau de fréquences est de 10 (0-9). Dans le cas du tri par comptage, nous n'utilisons pas la plage . La longueur du tableau de fréquences sera le nombre maximum du tableau + 1. Nous ne les divisons donc pas en bins alors que Radix Sort utilise les bins pour trier.

Le tri par comptage est assez efficace lorsque la longueur du tableau n'est pas beaucoup plus petite que la valeur maximale du tableau, tandis que Radix Sort permet des valeurs plus grandes dans le tableau.

6. Complexité

Les performances de Radix Sort dépendent de l'algorithme de tri stable choisi pour trier les chiffres.

Ici, nous avons utilisé le tri Radix pour trier un tableau de n nombres en base b . Dans notre cas, la base est 10. Nous avons appliqué le tri de comptage d fois où d représente le nombre de chiffres. Ainsi, la complexité temporelle de Radix Sort devient O (d * (n + b)) .

La complexité de l'espace est O (n + b) puisque nous avons utilisé ici une variante du tri de comptage comme sous-programme.

7. Conclusion

Dans cet article, nous avons décrit l'algorithme de tri Radix et illustré comment l'implémenter.

Comme d'habitude, les implémentations de code sont disponibles à l'adresse over sur Github.