Dato un elenco di interi la cui lunghezza è sconosciuta, e ognuno dei suoi elementi è compreso tra 1 e 1000, come si ordina questo elenco in tempo lineare?
Dato un elenco di interi la cui lunghezza è sconosciuta, e ognuno dei suoi elementi è compreso tra 1 e 1000, come si ordina questo elenco in tempo lineare?
Sai che ogni elemento del tuo int arr[]; è in [1;1000] .
Quindi disponi di una matrice di contatori, int cnt[1001]; nel linguaggio di C. Cancellalo (tutti gli zeri).
Quindi, leggi l'array arr[] in sequenza. Supponiamo di aver letto il valore x all'indice i (quindi x==arr[i] ). Quindi incrementa il suo contatore, quindi cnt[x]++;
Quando hai raggiunto la fine della matrice di input arr , esegui iterazione su cnt così for (int i=0; i<=1000; i++) e restituisci il numero i esattamente cnt[i] volte.
Questo è O (n) (perché il limite 1000 è una costante).
Questo tipo è spesso noto come conteggio degli ordinamenti .