Un array di lunghezza N può contenere valori 1,2,3 ... N ^ 2. E 'possibile ordinare in O (n)?

Question

Dato un array di lunghezza N, e può contenere valori da varia da 1 a N ^ 2 (N quadrato) entrambi inclusi, i valori sono solidali. E 'possibile ordinare questo array in O (n)? Se possibile, come?

Modifica:. Questo non è un lavoro

Answer 1

Valuta ogni intero a base di N, cioè ogni x può essere rappresentato come (x1, x2) con x = 1 + x1 + x2 * N. Ora è possibile ordinare due volte con counting sort, una volta in x1 e una volta in x2, con la conseguente array ordinato.

Answer 2

Sì, è possibile, utilizzando radix sort con N secchi e due passaggi. In sostanza, si trattano i numeri come avere 2 cifre in base N .

Answer 3

È possibile ordinare qualsiasi array di interi con un valore massimo ben definito nel tempo O(n) utilizzando un ordinamento digitale . Questo è probabilmente il caso per qualsiasi lista di interi che si incontrano. Per esempio se si stesse ordinamento di un elenco di numeri interi precisione arbitraria, non sarebbe vero. Ma tutti i tipi integrali del C sono ben definiti intervalli fissi.