promotion image of download ymail app
Promoted

Implementazione più sicura del QuickSort ?

Quale criterio posso utilizzare per la scelta del pivot nel QuickSort per avere maggiore probabilità di non degenerare ad una esecuzione O(n²) ?

VINCOLO : Allo stesso tempo voglio assicurarmi un comportamento discretamente veloce sia nel caso di Array già ordinato o ordinato in senso contrario.La scelta di un elemento casuale, dell'elemento iniziale, finale o della cosiddetta "mediana a tre" della partizione porta ad una esecuzione in tempo quadratico nei casi espressi nel VINCOLO.

La scelta dell'elemento con indice mediano rispetto alla partizione sembra essere quella vincente a tale scopo...

È realmente così o si può fare di meglio scegliendo un altro elemento ? Se si, cosa mi consigliate ?

Ancora nessuna risposta.
Rispondi prima di tutti a questa domanda.