Tri de comptage en Java

1. Vue d'ensemble

Les algorithmes de tri à usage général comme Merge Sort ne font aucune hypothèse sur l'entrée, ils ne peuvent donc pas battre le O (n log n) dans le pire des cas. Counting Sort, au contraire, a une hypothèse sur l'entrée qui en fait un algorithme de tri temporel linéaire.

Dans ce tutoriel, nous allons nous familiariser avec la mécanique du tri par comptage, puis l'implémenter en Java.

2. Tri de comptage

Le tri par comptage, contrairement à la plupart des algorithmes de tri classiques, ne trie pas l'entrée donnée en comparant les éléments. Au lieu de cela, il suppose que les éléments d'entrée sont n entiers dans la plage [0, k ] . Lorsque k = O (n), alors le tri de comptage s'exécutera dans le temps O (n) .

Veuillez noter que nous ne pouvons pas utiliser le tri par comptage comme algorithme de tri général. Cependant, lorsque l'entrée est alignée sur cette hypothèse, c'est assez rapide!

2.1. Tableau de fréquences

Supposons que nous allons trier un tableau d'entréeavec des valeurs dans la plage [0, 5]:

Tout d'abord, nous devons compter l'occurrence de chaque nombre dans le tableau d'entrée. Si nous représentons les comptages avec le tableau C , alors C [i] représente la fréquence du nombre i dans le tableau d'entrée :

Par exemple, puisque 5 apparaît 3 fois dans le tableau d'entrée, la valeur de l'index 5 est égale à 3.

Maintenant, étant donné le tableau C, nous devons déterminer combien d'éléments sont inférieurs ou égaux à chaque élément d'entrée. Par exemple:

  • Un élément est inférieur ou égal à zéro, ou en d'autres termes, il n'y a qu'une seule valeur zéro, qui est égale à C [0]
  • Deux éléments sont inférieurs ou égaux à un, qui est égal à C [0] + C [1]
  • Quatre valeurs sont inférieures ou égales à deux, ce qui est égal à C [0] + C [1] + C [2]

Donc, si nous continuons à calculer la somme de n éléments consécutifs dans C, nous pouvons savoir combien d'éléments sont inférieurs ou égaux au nombre n-1 dans le tableau d'entrée. Quoi qu'il en soit, en appliquant cette formule simple, nous pouvons mettre à jour le C comme suit:

2.2. L'algorithme

Nous pouvons maintenant utiliser le tableau auxiliaire C pour trier le tableau d'entrée. Voici comment fonctionne le tri de comptage:

  • Il itère le tableau d'entrée à l'envers
  • Pour chaque élément i, C [i] - 1 représente l'emplacement du nombre i dans le tableau trié. Ceci est dû au fait qu'il y a des éléments C [i] inférieurs ou égaux à i
  • Ensuite, il décrémente le C [i] à la fin de chaque tour

Afin de trier l'exemple de tableau d'entrée, nous devons d'abord commencer par le numéro 5, car c'est le dernier élément. Selon C [5], il y a 11 éléments inférieurs ou égaux au nombre 5.

Donc, 5 devrait être le 11e élément du tableau trié, d'où l'index 10:

Puisque nous avons déplacé 5 vers le tableau trié, nous devrions décrémenter le C [5]. L'élément suivant dans l'ordre inverse est 2. Puisqu'il y a 4 éléments inférieurs ou égaux à 2, ce nombre doit être le 4ème élément du tableau trié:

De même, nous pouvons trouver le bon endroit pour l'élément suivant qui est 0:

Si nous continuons à itérer en sens inverse et que nous déplaçons chaque élément de manière appropriée, nous nous retrouverions avec quelque chose comme:

3. Tri de comptage - Implémentation Java

3.1. Calcul du tableau de fréquences

Tout d'abord, étant donné un tableau d'entrée d'éléments et le k, nous devrions calculer le tableau C:

int[] countElements(int[] input, int k) { int[] c = new int[k + 1]; Arrays.fill(c, 0); for (int i : input) { c[i] += 1; } for (int i = 1; i < c.length; i++) { c[i] += c[i - 1]; } return c; }

Décrivons la signature de la méthode:

  • l'entrée représente un tableau de nombres que nous allons trier
  • Le tableau d' entrée est un tableau d'entiers dans la plage de [0, k ] - donc k représente le nombre maximum dans l' entrée
  • Le type de retour est un tableau d'entiers représentant le tableau C

Et voici comment fonctionne la méthode countElements :

  • Tout d'abord, nous avons initialisé le tableau C. Comme la plage [0, k] contient k + 1 nombres, nous créons un tableau capable de contenir k + 1 nombres
  • Ensuite, pour chaque nombre dans l' entrée, nous calculons la fréquence de ce nombre
  • Et enfin, nous ajoutons des éléments consécutifs ensemble pour savoir combien d'éléments sont inférieurs ou égaux à un nombre particulier

De plus, nous pouvons vérifier que la méthode countElements fonctionne comme prévu:

@Test void countElements_GivenAnArray_ShouldCalculateTheFrequencyArrayAsExpected() { int k = 5; int[] input = { 4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5 }; int[] c = CountingSort.countElements(input, k); int[] expected = { 1, 2, 4, 6, 8, 11 }; assertArrayEquals(expected, c); }

3.2. Tri du tableau d'entrée

Maintenant que nous pouvons calculer le tableau de fréquences, nous devrions être en mesure de trier n'importe quel ensemble donné de nombres:

int[] sort(int[] input, int k) { int[] c = countElements(input, k); int[] sorted = new int[input.length]; for (int i = input.length - 1; i >= 0; i--) { int current = input[i]; sorted[c[current] - 1] = current; c[current] -= 1; } return sorted; }

Voici comment fonctionne la méthode de tri :

  • Tout d'abord, il calcule le tableau C
  • Then, it iterates the input array in reverse and for each element in the input, finds its correct spot in the sorted array. The ith element in the input should be the C[i]th element in the sorted array. Since Java arrays are zero-indexed, the C[i]-1 entry is the C[i]th element – for example, sorted[5] is the sixth element in the sorted array
  • Each time we find a match, it decrements the corresponding C[i] value

Similarly, we can verify that the sort method works as expected:

@Test void sort_GivenAnArray_ShouldSortTheInputAsExpected() { int k = 5; int[] input = { 4, 3, 2, 5, 4, 3, 5, 1, 0, 2, 5 }; int[] sorted = CountingSort.sort(input, k); // Our sorting algorithm and Java's should return the same result Arrays.sort(input); assertArrayEquals(input, sorted); }

4. Revisiting the Counting Sort Algorithm

4.1. Complexity Analysis

Most classic sorting algorithms, like merge sort, sort any given input by just comparing the input elements to each other. These type of sorting algorithms are known as comparison sorts. In the worst case, comparison sorts should take at least O(n log n) to sort n elements.

Counting Sort, on the other hand, does not sort the input by comparing the input elements, so it's clearly not a comparison sort algorithm.

Let's see how much time it consumes to sort the input:

  • It computes the C array in O(n+k) time: It once iterates an input array with size n in O(n) and then iterates the C in O(k) – so that would be O(n+k) in total
  • After computing the C, it sorts the input by iterating the input array and performing a few primitive operations in each iteration. So, the actual sort operation takes O(n)

In total, counting sort takes O(n+k) time to run:

O(n + k) + O(n) = O(2n + k) = O(n + k)

If we assume k=O(n), then counting sort algorithm sorts the input in linear time. As opposed to general-purpose sorting algorithms, counting sorts makes an assumption about the input and takes less than the O(n log n) lower bound to execute.

4.2. Stability

A few moments ago, we laid a few peculiar rules about the mechanics of counting sort but never cleared the reason behind them. To be more specific:

  • Why should we iterate the input array in reverse?
  • Why we decrement the C[i] each time we're using it?

Let's iterate from the beginning to better understand the first rule. Suppose we're going to sort a simple array of integers like the following:

In the first iteration, we should find the sorted location for the first 1:

So the first occurrence of number 1 gets the last index in the sorted array. Skipping the number 0, let's see what happens to the second occurrence of number 1:

The appearance order of elements with the same value is different in the input and sorted array, so the algorithm is not stable when we're iterating from the beginning.

What happens if we don't decrement the C[i] value after each use? Let's see:

Both occurrences of number 1 are getting the last place in the sorted array. So if we don't decrement the C[i] value after each use, we could potentially lose a few numbers while sorting them!

5. Conclusion

Dans ce didacticiel, nous avons d'abord appris comment le tri par comptage fonctionne en interne. Ensuite, nous avons implémenté cet algorithme de tri en Java et écrit quelques tests pour vérifier son comportement. Et enfin, nous avons prouvé que l'algorithme est un algorithme de tri stable avec une complexité temporelle linéaire.

Comme d'habitude, les exemples de codes sont disponibles sur notre projet GitHub, alors assurez-vous de le vérifier!