[Algoritmi] Quicksort e complessità algoritmica
Salve, volevo chiedervi alcune cose come da titolo per le quali sto uscendo pazzo 
.
Mi sto studiando il celebre quicksort, e sto cercando di capirlo un po' in tutte le siuazioni. La versione randomizzata, in cui scegliamo come pivot l elemento mediano, è ok. LA versione non randomizzata ( in cui il pivot è v[1] o v[n]) mi sta facendo un po' confondere. Una volta completato il primo passaggio cioè in cui i>j, non so come spezzare il vettore visto che il pivot non funge + da "elemento mediano divisore"...!!!!
Se ad esempio, alla fine del primo passaggio, mi ritrovo con:
e, se il pivot fosse centrale non ci sarebbero problemi ( tutti gli elementi da v[1] a v[pivot] e da v[pivot] a v[n] sarebbero i 2 sottovettori e procederei ricorsivamente.)
Ma visto che 21 è il pivot come faccio?
Quando ho risolto questo problema , vi chiederò alcune cose riguardo alla sua complessità
.Mi sto studiando il celebre quicksort, e sto cercando di capirlo un po' in tutte le siuazioni. La versione randomizzata, in cui scegliamo come pivot l elemento mediano, è ok. LA versione non randomizzata ( in cui il pivot è v[1] o v[n]) mi sta facendo un po' confondere. Una volta completato il primo passaggio cioè in cui i>j, non so come spezzare il vettore visto che il pivot non funge + da "elemento mediano divisore"...!!!!
Se ad esempio, alla fine del primo passaggio, mi ritrovo con:
21(p) 18 5 15 11 3 22 88 63 37 45 59 71 51 30
e, se il pivot fosse centrale non ci sarebbero problemi ( tutti gli elementi da v[1] a v[pivot] e da v[pivot] a v[n] sarebbero i 2 sottovettori e procederei ricorsivamente.)
Ma visto che 21 è il pivot come faccio?
Quando ho risolto questo problema , vi chiederò alcune cose riguardo alla sua complessità
Risposte
no aspetta un attimo credo di non aver capito bene cosa vuoi dire...
allora in soldoni il quicksort prende l'arrey, sceglie un valore, lo usa come perno, e divide in base a quello a metà l'arrey stesso, fra i maggiori ed i minori di quel valore.
in particolare se prendo il primo elemento ho(faccio un esempio con molti meno elementi dei tuoi)
21 18 5 11 3 23 perno 21
scambio 21 con 3 -> 3 18 5 11 21 23
ora il "puntatore"(l'indice) che partiva dalla posizione del 21 si troverà in posizione del nuovo 21 mentre l'altro in posizione dell'11
verrà dunque richiamato quicksort sulla porzione da 3 a 11 prima e da 21 a 23 poi
3 18 5 11 perno 3
nessuno scambio
ho il puntatore destro su 3 ed il puntatore sinistro su 18
richiamo dunque solo per la porzione da 18 a 11:
18 5 11 perno 18
e così via....
spero di essere stato esaustivo, e se non lo sono stato ti prego di specificare meglio cosa non ti torna
allora in soldoni il quicksort prende l'arrey, sceglie un valore, lo usa come perno, e divide in base a quello a metà l'arrey stesso, fra i maggiori ed i minori di quel valore.
in particolare se prendo il primo elemento ho(faccio un esempio con molti meno elementi dei tuoi)
21 18 5 11 3 23 perno 21
scambio 21 con 3 -> 3 18 5 11 21 23
ora il "puntatore"(l'indice) che partiva dalla posizione del 21 si troverà in posizione del nuovo 21 mentre l'altro in posizione dell'11
verrà dunque richiamato quicksort sulla porzione da 3 a 11 prima e da 21 a 23 poi
3 18 5 11 perno 3
nessuno scambio
ho il puntatore destro su 3 ed il puntatore sinistro su 18
richiamo dunque solo per la porzione da 18 a 11:
18 5 11 perno 18
e così via....
spero di essere stato esaustivo, e se non lo sono stato ti prego di specificare meglio cosa non ti torna
Ok mi sono spiegato male.
SUpponiamo di voler ordinare
6 9 1 80 26 15 elemento pivot 6
la i parte da 9 e la j da 15.
i si ferma subito su 9 poiche i>=pivot. j si decrementa finhcè non arriva a 1.
Come procedo poi?
SUpponiamo di voler ordinare
6 9 1 80 26 15 elemento pivot 6
la i parte da 9 e la j da 15.
i si ferma subito su 9 poiche i>=pivot. j si decrementa finhcè non arriva a 1.
Come procedo poi?
scambi 6 ed 1(incrementi i e decrementi j)
poi hai 1 9 6 80 26 15
a questo punto sia i che j stanno su 9, per i va bene, per j no.
decrementi e arrivi sull'uno che va bene.
non scambi però poichè i e j hanno "scavallato"
allora richiami ricorsivamente la funzione su [9 6 80 26 15]
su 1 no poichè è inutile farlo(c'è un controllo che non te lo fa fare se è di un solo elemento)
se vuoi anche il nuovo ciclo il pivot è 9
i va bene j arriva fino a 6
scambi 9 e 6(incrementi i decrementi j)
hanno scavallato dunque arrivi alla richiamata e di nuovo il 9 non ha senso di essere chiamato, richiami allora da 6 a 15
capito?
poi hai 1 9 6 80 26 15
a questo punto sia i che j stanno su 9, per i va bene, per j no.
decrementi e arrivi sull'uno che va bene.
non scambi però poichè i e j hanno "scavallato"
allora richiami ricorsivamente la funzione su [9 6 80 26 15]
su 1 no poichè è inutile farlo(c'è un controllo che non te lo fa fare se è di un solo elemento)
se vuoi anche il nuovo ciclo il pivot è 9
i va bene j arriva fino a 6
scambi 9 e 6(incrementi i decrementi j)
hanno scavallato dunque arrivi alla richiamata e di nuovo il 9 non ha senso di essere chiamato, richiami allora da 6 a 15
capito?
Scusami, ma ancora non mi entra in testa...
Una volta che ho
6 9 1 80 26 15
i j
A quanto dici scambio pivot con j. ok. e incremento i e decremento j.
1 9 6 80 26 15
j i
A me torna cosi... come fanno a stare entrambi su 9?:(
Una volta che ho
6 9 1 80 26 15
i j
A quanto dici scambio pivot con j. ok. e incremento i e decremento j.
1 9 6 80 26 15
j i
A me torna cosi... come fanno a stare entrambi su 9?:(
no allora mi pare tu stia facendo una certa confusione
partiamo dunque da capo, illustrami in modo breve e più chiaro possibile qual'è il punto che non ti torna
poichè quello che mi hai appena scritto se lo hai preso dalla fine del mio esempio presenta un po' di errori, se invece te lo sei invetato lì per lì gradirei me lo contestualizzassi
partiamo dunque da capo, illustrami in modo breve e più chiaro possibile qual'è il punto che non ti torna
poichè quello che mi hai appena scritto se lo hai preso dalla fine del mio esempio presenta un po' di errori, se invece te lo sei invetato lì per lì gradirei me lo contestualizzassi
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo