Counting Sort (Ordinamento per conteggio)
Algoritmi come Merge Sort eseguono operazioni per ordinare una certa sequenza di elementi. La maggior parte delle funzioni integrate
sort() in diversi linguaggi di programmazione svolge anch’essa operazioni. Sorge quindi una domanda spontanea: esiste un modo per eseguire l’ordinamento più velocemente?Un algoritmo di base che ordina una sequenza di elementi in tempo lineare, cioè eseguendo operazioni, è l’algoritmo Counting Sort. Counting Sort è un metodo di ordinamento lineare particolarmente adatto per l’ordinamento di collezioni di elementi in cui i valori sono noti e rappresentati da interi di piccola entità.
L’idea di fondo del Counting Sort è utilizzare una struttura simile a un istogramma per contare quanti elementi dell’input presentano un determinato valore, e poi sfruttare queste informazioni per riordinare gli elementi in ordine crescente.
Per esempio, per ordinare un array con i valori
[7, 3, 5, 5, 1, 1, 6, 3, 4, 4, 3, 3, 7, 7, 1, 2, 5, 7, 4, 1, 7, 2, 1, 5, 5, 3, 1, 4, 8, 7], creeremmo un istogramma che indica che ci sono 6 valori pari a 1, 2 valori pari a 2, 5 valori pari a 3, e così via: [6, 2, 5, 4, 5, 1, 6, 1] (come mostrato in figura).
a = ...
bottom, top = min(a), max(a) + 1 # Determina l'intervallo
hist = [0] * (top - bottom) # Riempi l'intervallo con 0 => nessun conteggio
for num in a: # Itera sull'array
hist[num - bottom] += 1 # Incrementa il valore nell'istogramma
res = [] # Inizializza l'array di risultato
for num in range(bottom, top): # Itera sull'intervallo
res += [num] * hist[num - bottom] # Aggiungi tante copie di num quante indicate dall'istogrammaAl termine, il risultato sarà
[1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 7, 7, 7, 7, 7, 7, 8].Notare che questo approccio funziona soltanto con numeri, in particolare numeri di piccola entità, mentre altri algoritmi come Bubble Sort o Merge Sort si applicano invece a qualsiasi tipo di elemento che possa essere confrontato.
L’algoritmo svolge in totale operazioni, dove
n è il numero di elementi dell’array iniziale e r è il numero di valori distinti nel suo intervallo. Questa caratteristica può renderlo particolarmente veloce rispetto ad algoritmi come Merge Sort quando si ordinano numeri con un intervallo di valori relativamente ristretto.🤔
Esistono altri algoritmi di ordinamento in tempo lineare?
Sì, puoi dare un’occhiata a Radix-sort. Tuttavia, funzionano solo con numeri.
Se consideriamo solo algoritmi basati sul confronto, validi per qualsiasi tipo di sequenza (a patto che sia possibile confrontare gli elementi), allora il miglior algoritmo in questo ambito richiede operazioni, e non meno di così.
Input
La prima riga dell’ingresso contiene un singolo intero
n (1 ≤ n ≤ ).La riga successiva contiene
n interi separati da spazi (-100 ≤ ≤ 100).Output
Il programma deve stampare i
n interi forniti, separati da uno spazio, in ordine crescente.Esempi
Input | Output |
5
-3 5 -1 2 10 | -3 -1 2 5 10 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 5 MB