Come ordinare una lista con un intervallo dato in O (n) - algoritmo, ordinamento

Se ho un elenco di dimensioni n e so che i numeri nell'elenco saranno compresi tra 1 e 2n, come potrei fare per risolverlo dove il caso peggiore sarebbe O (n)?

Stavo pensando che se fosse compreso tra 1 e n potrei semplicemente prendere il numero e scambiarlo con il valore dell'array con quel numero - 1, ma poi non sarebbe in ordine se ci fossero duplicati.

Stavo pensando a un approccio simile per l'elenco con un numero compreso tra 1 e 2n ma non riesco a capirlo. Qualche aiuto per favore?

risposte:

4 per risposta № 1

In genere è necessario un ordinamento senza confrontoordina in O (n) tempo, ma questo è se ti sono già state fornite determinate informazioni. Esistono tre algoritmi di ordinamento "principali" senza confronto tra cui scegliere: conteggio ordinamento, ordinamento radix e ordinamento bucket.

Usa l'ordinamento di conteggio se sai che l'input èpiccoli numeri interi. Secondo Wikipedia, "contare l'ordinamento è adatto solo per l'uso in situazioni in cui la variazione delle chiavi non è significativamente maggiore del numero di elementi". http://en.wikipedia.org/wiki/Counting_sort

Puoi usare l'ordinamento radix se tutti i numeri che stai ordinando hanno lo stesso numero di numeri interi. Es .: 211, 311, 122.

L'ordinamento della benna può sembrare l'opzione migliore per te. L'approccio suona bene, ma non è necessario un array da 1 a 2n con un indice per ciascun numero. Nell'ordinamento bucket, puoi avere un array da 1 a 20 e avere qualcosa come un elenco collegato all'interno di ciascun elemento. Quindi, se si posizionasse il numero 109, potrebbe corrispondere all'indice 10.

---

6 per risposta № 2

Conteggio Sort può operare dentro Sopra) nel tuo caso. Dai un'occhiata alla definizione di wikipedia

counting sort è un algoritmo per ordinare araccolta di oggetti secondo chiavi che sono numeri interi piccoli; cioè è un numero intero algoritmo di ordinamento. Funziona contando il numero di oggetti che hanno ogni valore chiave distinto, e usando l'aritmetica su questi aspetti determinare le posizioni di ciascun valore chiave nella sequenza di output. Suo il tempo di esecuzione è lineare nel numero di articoli e nella differenza tra i valori chiave massimo e minimo, quindi è adatto solo per uso diretto in situazioni in cui la variazione dei tasti non è significativamente maggiore del numero di articoli

http://en.wikipedia.org/wiki/Counting_sort

---

0 per risposta № 3

Puoi usare l'ordinamento radix qui. Quando hai delle restrizioni sull'input, come nel tuo caso, funziona bene. Dai un'occhiata all'algoritmo qui - http://en.wikipedia.org/wiki/Radix_sort

---

0 per risposta № 4

Puoi usare l'ordinamento radix, contando l'ordinamento, ci sono molti tipi O (n).

Ma la domanda ti sta rendendo davvero facile ...

In Java:

int [n] input = {your list of n numbers}; int [2*n] listinorder; int [n] output;

for (int i=0, i<2n, i++) listinorder[i] = -1; // set all values of listinorder to -1

for (int i=0, i < n, i++) listinorder[input[i]] = input[i]; // set the ith value of listinorder to i

int j=0;

for (int i=0, i<2n, i++) if (listinorder(i)  != -1) {output[j] = i; j++};

In inglese:

1. Stabilire un array (diciamo listinorder) di lunghezza 2n.
2. Imposta ogni valore su -1. Scorri l'elenco di input.
3. Per ciascun valore i nell'elenco di input, impostare il valore corrispondente di listinorder a i (es listinorder[i]=i). Quindi scorrere attraverso valori di listinorder che non sono "t -1 per produrre l'elenco ordinato.

Tutti O (n).

---