Ordinamento conteggio in Java

1. Panoramica

Gli algoritmi di ordinamento di uso generale come Merge Sort non fanno supposizioni sull'input, quindi non possono battere O (n log n) nel peggiore dei casi. Counting Sort, al contrario, ha un'ipotesi sull'input che lo rende un algoritmo di ordinamento temporale lineare.

In questo tutorial, faremo conoscenza con i meccanismi del Counting Sort e poi lo implementeremo in Java.

2. Ordinamento conteggio

Il conteggio dell'ordinamento, a differenza della maggior parte degli algoritmi di ordinamento classici, non ordina l'input fornito confrontando gli elementi. Invece, assume che gli elementi di input siano n numeri interi nell'intervallo [0, k ] . Quando k = O (n), l'ordinamento conteggio verrà eseguito nel tempo O (n) .

Tieni presente, quindi, che non possiamo utilizzare l'ordinamento conteggio come algoritmo di ordinamento generico. Tuttavia, quando l'input è allineato con questa ipotesi, è abbastanza veloce!

2.1. Array di frequenza

Supponiamo di ordinare un array di inputcon valori nell'intervallo [0, 5]:

Innanzitutto, dovremmo contare l'occorrenza di ogni numero nell'array di input. Se rappresentiamo i conteggi con l'array C , allora C [i] rappresenta la frequenza del numero i nell'array di input :

Ad esempio, poiché 5 appare 3 volte nella matrice di input, il valore per l'indice 5 è uguale a 3.

Ora dato l'array C, dovremmo determinare quanti elementi sono minori o uguali a ciascun elemento di input. Per esempio:

  • Un elemento è minore o uguale a zero, o in altre parole, c'è solo un valore zero, che è uguale a C [0]
  • Due elementi sono minori o uguali a uno, che è uguale a C [0] + C [1]
  • Quattro valori sono minori o uguali a due, che è uguale a C [0] + C [1] + C [2]

Quindi, se continuiamo a calcolare la somma di n elementi consecutivi in C, possiamo sapere quanti elementi sono minori o uguali al numero n-1 nell'array di input. Ad ogni modo, applicando questa semplice formula possiamo aggiornare la C come segue:

2.2. L'algoritmo

Ora possiamo usare l'array ausiliario C per ordinare l'array di input. Ecco come funziona l'ordinamento conteggio:

  • Itera la matrice di input al contrario
  • Per ogni elemento i, C [i] - 1 rappresenta la posizione del numero i nell'array ordinato. Ciò è dovuto al fatto che ci sono elementi C [i] minori o uguali a i
  • Quindi, diminuisce la C [i] alla fine di ogni round

Per ordinare l'array di input di esempio, dovremmo prima iniziare con il numero 5, poiché è l'ultimo elemento. Secondo C [5], ci sono 11 elementi minori o uguali al numero 5.

Quindi, 5 dovrebbe essere l'undicesimo elemento nell'array ordinato, da cui l'indice 10:

Dato che abbiamo spostato 5 nell'array ordinato, dovremmo diminuire C [5]. L'elemento successivo nell'ordine inverso è 2. Poiché ci sono 4 elementi minori o uguali a 2, questo numero dovrebbe essere il 4 ° elemento dell'array ordinato:

Allo stesso modo, possiamo trovare il punto giusto per l'elemento successivo che è 0:

Se continuiamo a iterare al contrario e spostiamo ogni elemento in modo appropriato, avremmo qualcosa come:

3. Ordinamento conteggio - Implementazione Java

3.1. Calcolo della matrice di frequenza

Prima di tutto, dato un array di elementi di input e il k, dovremmo calcolare l'array 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; }

Analizziamo la firma del metodo:

  • input rappresenta un array di numeri che andremo a ordinare
  • L' ingresso matrice è una matrice di numeri interi nell'intervallo [0, k ] - così k rappresenta il numero massimo nella ingresso
  • Il tipo restituito è un array di numeri interi che rappresenta l' array C.

Ed ecco come funziona il metodo countElements :

  • Innanzitutto, abbiamo inizializzato l' array C. Poiché l'intervallo [0, k] contiene k + 1 numeri, stiamo creando un array in grado di contenere k + 1 numeri
  • Quindi per ogni numero nell'input, stiamo calcolando la frequenza di quel numero
  • Infine, stiamo aggiungendo elementi consecutivi per sapere quanti elementi sono minori o uguali a un determinato numero

Inoltre, possiamo verificare che il metodo countElements funzioni come previsto:

@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. Ordinamento della matrice di input

Ora che possiamo calcolare l'array di frequenza, dovremmo essere in grado di ordinare qualsiasi dato insieme di numeri:

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; }

Ecco come funziona il metodo di ordinamento :

  • Innanzitutto, calcola l' array 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

In questo tutorial, in primo luogo, abbiamo imparato come funziona internamente l'ordinamento conteggio. Quindi abbiamo implementato questo algoritmo di ordinamento in Java e abbiamo scritto alcuni test per verificarne il comportamento. Infine, abbiamo dimostrato che l'algoritmo è un algoritmo di ordinamento stabile con complessità temporale lineare.

Come al solito, i codici di esempio sono disponibili nel nostro progetto GitHub, quindi assicurati di controllarlo!