Perché la scelta ottimale per un pivot nell'algoritmo quicksort è l'elemento mediano?

0

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.

    
posta Sujal Mandal 25.09.2017 - 12:00
fonte

1 risposta

8

Sembra che tu stia confondendo il valore mediano e l'elemento intermedio.

L'elemento centrale della matrice non ordinata potrebbe effettivamente rivelarsi vicino al valore più basso o più alto.
Il valore mediano d'altra parte è il valore che ha la metà dei valori confronta come più piccolo e la metà dei valori è più grande.

Il vantaggio dell'utilizzo del valore mediano come pivot in quicksort è che garantisce che le due partizioni siano il più vicino possibile alla dimensione uguale.
Il problema di usare il valore mediano è che è necessario conoscere i valori di tutti gli elementi per sapere quale è la mediana. Ciò rende difficile l'utilizzo del valore mediano nella pratica, nonostante sia in teoria il valore ottimale.

    
risposta data 25.09.2017 - 12:29
fonte

Leggi altre domande sui tag