Ultimamente ho seguito un corso su brilliant.org, stavo esplorando una lezione sull'algoritmo QuickSort, ho trovato una domanda.
Quale delle seguenti opzioni fornirebbe la selezione di pivot ottimale in ogni fase di quicksort?
- A. L'elemento nella prima posizione
- B. L'elemento con il valore più piccolo
- C. Un elemento selezionato casualmente
- D. La mediana degli elementi
la risposta elencata era "D"
ma negli array di vita reale come sarà una delle opzioni sopra?
Giustificazione elencata era
"il valore mediano, consentirà all'algoritmo di suddividere l'elenco in parti approssimativamente uguali, in modo che il runtime aumenti rapidamente."
Non conosciamo mai il valore di un elemento, se scegliamo una mediana come è garantito che la matrice divida in 2 parti? Per quanto ne sappiamo, potrebbe essere il più alto o il più basso o molto vicino al più alto o al più basso numero. Ciò renderebbe quasi vuoto l'array di sinistra o l'array di destra.