Problema con algoritmo

[SteveVai222]

Salve a tutti..
dovrei implementare un algoritmo che ordini n numeri compresi tra 0 e n^2 -1 in tempo O(n) combinando il counting e il radix sort..come posso fare?!?
non mi serve in nessun linguaggio di programmazione specifico, basta in pseudocodifica..poi per "trasporlo" ci penso io..
Grazie..

[:.Blizzard.:]

Argh ... ho visto questo esercizio qualche settimana fà ma non lo ricordo. Comunque devi utilizzare il cambiamento di base. Che libro utilizzi per studiare? Se hai il Cormen c'è scritto proprio come risolvere questo problema.

[SteveVai222]

utilizzo introduzione agli algoritmi di thomas h. cormen

[WarDuck]

Io conosco l'integer sort...

in pratica per numeri sufficiente piccoli riesce ad ordinarti la cosa in ordine lineare.

Praticamente crei un array A con lunghezza pari al massimo dei tuoi numeri (trovare il massimo è lineare), ed inizializzi tutte le celle a 0.

Supponedo che gli indici dell'array vadano da 1..N, per ogni elemento X del tuo array disordinato incrementi di 1 A[X].

Esempio:

Array disordinato:

D [4, 3, 2, 6, 8, 5, 3]

Il massimo è 8 per cui creo un array con 8 posizioni:

A [0, 0, 0, 0, 0, 0, 0, 0]

Comincio la scansione...

D[1] = 4
A[4] = A[4] + 1

A [0, 0, 0, 1, 0, 0, 0, 0]

D[2] = 3
A[3] = A[3] + 1

A [0, 0, 1, 1, 0, 0, 0, 0]

E così via fino a raggiungere questa posizione:

D[6] = 5
A[5] = A[5]+1

A [0, 1, 1, 1, 1, 1, 0, 1]

A questo punto l'ultimo numero è:
D[7] = 3
A[3] = A[3]+1

Per cui:

A [0, 1, 2, 1, 1, 1, 0, 1]

A questo punto si fa la scansione dell'array A e si scrivono gli indici fino a quando la casella A[X] non diventa nulla:

2, 3, 3, 4, 5, 6, 8

Ribadisco, questo algoritmo è buono per numeri sufficientemente piccoli.

[Kenger]

Tieni, la risposta che ho dato ad un mio amico quando mi ha chiesto una cosa molto simile, solo che i numeri arrivavano a n^3.

Allora, vediamo se riesco a spiegarmi.
Diciamo che n=100. Quindi i numeri saranno da 0 a n^3-1=999999.
Il trucco consiste nell'applicare il radix sort non prendendo ogni singola cifra come colonna ma come gruppi di cifre. Visto che è n^3 dividiamo ogni numero in 3 e applichiamo il counting sort prima sulla colonna più a destra, poi quella centrale e infine a quella sulla sinistra. E così abbiamo ordinato i numeri da 0 a n^3. Ora il costo...

Il counting sort su ogni singola colonna costa theta(n+k) dove k è il numero più grande contenibile nella colonna (nel nostro caso 99). Visto che n^3 ha 3 volte il numero di cifre di n e che abbiamo diviso n^3 in 3 numeri lunghi uguali otteniamo che k=n, quindi il singolo counting sort costa theta(n). Eseguiamo 3 counting sort e otteniamo 3*theta(n) che è uguale a theta(n).
Lo stesso giochino si può ripetere con un qualsiasi n^m dove m è una costante intera.

Dubito sia tutto chiaro leggendo una mail scritta di getto, quindi chiedi pure. ^^

[SteveVai222]

@ WarDuck ma l'integer sort è tipo il counting sort un po più semplice..il problema è che i numeri non sono relativamente piccoli e poi devo risolvere il problema unendo il radix e il counting sort..comunque grazie lo stesso..

@ Kenger No direi che dovrei aver capito,facciamo la prova del 9..
Praticamente il counting sort è all'interno del radix sort giusto?!?!
quindi parte il radix sort (nel nostro caso sulle ultime 3 cifre) poi parte il counting sort..e cosi per le altre due volte..è cosi??! se mi facessi anche un piccolo tabulato in pseudocodice te ne sarei molto grato!!
comunque grazie..