miles

User info:

Registered: Aug 2005
Posts: 18 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 7:36:46 [...]
Status: Offline

Post actions:

qualcuno mi può spiegare come modificare quicksort' per avere una pronfondità della stack di O(lgn) nel caso peggiore e come funziona bucketsort per gli interi?

mapenzi81

User info:

Registered: Feb 2005
Posts: 233 (0.03 al dì)
Location: Milano
Corso: Informatica
Anno: 3.....456789....
Time Online: 6 Days, 1:18:40 [...]
Status: Offline

Post actions:

Allora....
l ordinamento con quicksort lo puoi risolvere ricorsivamente 2 volte o gestire una delle due chiamate in "locale" e solamente nell'altra usi la ricorsione (ovvero butti nello stack uno dei due array).
Se provi il caso peggiore per le velocita di qs ti ritrovi due array uno d dimensione 1 e l'altro di dimensione n-1.
Mandando nello stack l'array piu grande ti ritrovi a risolvere subito la soluzione piccola (banale ha un solo elemento) mentre nello stack metti la soluzione piu grande....(n-1)...(n-2)......
In realta ci sta per poco tempo perchè la riprendi subito e quindi lo stack si riempie e si svuota immediatamente...
cmq sia..se provi con soluzioni intermedie mettendo l'array piu grande hai una ricorsione che al piu è lg(n)

Per bucketsort devi creare una funzione che trasformi il tuo input da intero a 0<=k<1
Una possibile puo essere

h(k)=(k-min)/(max-min+1)
min e max sono i minimi e i massimi input

provala perchè sto andando a memoria....

__________________
Sto cercando disperatamente di capire perché i piloti kamikaze si mettessero i caschi in testa.

Dave Edison

miles

User info:

Registered: Aug 2005
Posts: 18 (0.00 al dì)
Location:
Corso:
Anno:
Time Online: 7:36:46 [...]
Status: Offline

Post actions:

grazie mille