Cos'è un Quicksort deterministico?

Question

Ho letto di Quicksort e ho scoperto che a volte viene chiamato "Quicksort deterministico".

È questa una versione alternativa del normale Quicksort?Qual è la differenza tra un Quicksort normale e un Quicksort deterministico?

Answer 1

L'ordinario ( "deterministico") Quicksort può avere un comportamento molto scarsa su particolari gruppi di dati (ad esempio, un'implementazione che preleva il primo elemento non ordinata ha O (n ^ 2) complessità temporale su dati già filtrate).

randomizzato Quicksort (che seleziona un perno casuale, invece di scegliere in modo deterministico) viene talvolta usato per dare migliori prestazioni attese per tutti set di dati.

Answer 2

Quicksort viene eseguito in O(n log n) / tempo medio previsto, ma O(n^2) caso peggiore. Ciò si verifica se il perno scelto è costantemente minimo o massimo.

Idealmente, si desidera selezionare la mediana come perno. Se trovare la mediana direttamente è troppo costoso (di solito questo è il caso, se si sta cercando di usare quicksort), ciò che è comunemente fatto invece è quello di prendere la mediana di tre potenziali elementi pivot, oppure basta scegliere un elemento casuale come perno .

Il secondo metodo rende quicksort non deterministico causa della casualità inerente al processo di selezione del perno.

Answer 3

In generale, un algoritmo di ordinamento è "deterministico" se ordina in modo coerente gli elementi in esattamente lo stesso ordine ogni volta. Dato un insieme di record da ordinare su id (crescente):

  1 Censu
  11 Marju
  4  Cikku
  11 Lonzu

quindi un algoritmo di ordinamento potrebbe tornare entrambi Censu, Cikk, Marju, Lonzu o Censu, Cikku, Lonzu, Marju, cernite come corrette. Una sorta deterministico è uno che restituisce sempre lo stesso ordine. Questo non deve essere sempre il caso. Nel caso di quicksort, si può ottenere performance media più veloce se i perni sono scelti a caso (idealmente si dovrebbe scegliere la mediana, ma questo può essere costoso). Tuttavia, questo ha un costo:. La ricerca non è più deterministica

Answer 4

La fonte può (e dovrebbe) dare una propria definizione, ma generalmente un Quicksort deterministico è quella in cui il perno viene scelto attraverso una formula che non dipende da numeri casuali. Ad esempio, scegliere sempre l'elemento centrale o sempre il primo, o qualcosa di simile. Ciò significa che le sue prestazioni sarà sempre lo stesso (almeno in teoria, anche se in pratica la differenza non dovrebbe essere troppo grande), non importa quante volte lo si esegue sullo stesso ingresso. Un quicksort randomizzato significa che si sta utilizzando numeri casuali al momento di scegliere il perno, il che significa la prestazione non può essere (facilmente) previsto per sedute diverse sullo stesso ingresso.

Answer 5

Ha a che fare con il partizionamento (o la fase di divisione del famoso Divide and Conquer utilizzato nell'ordinamento rapido).Se ogni volta che l'ultimo (o il primo elemento o elemento in qualsiasi posizione, solo che deve essere la stessa posizione ogni volta che il set di dati viene diviso) viene utilizzato come perno per la partizione, allora si tratta di un ordinamento rapido deterministico.Se il pivot viene scelto in modo casuale, si tratta di un ordinamento rapido casuale.

Ecco un nota della lezione che lo mette in comunicazione.

spero possa essere d'aiuto

saluti

Answer 6

aggettivi comuni di fronte a Quicksort sono deterministici e randomizzati. Deterministico significa che il quicksort sempre ordinare lo stesso insieme di dati nello stesso modo, mentre un quicksort randomizzato utilizza randomizzazione e raramente ordinare gli stessi dati nello stesso modo esatto (a meno che il set di dati è molto piccola -, allora è più comune) .

deterministici

Si tratta di come vengono scelti i perni. In un Quicksort deterministico, i perni sono scelti da uno scegliendo sempre il perno Allo stesso indice relativo come primo elemento, ultimo, o centrale oppure utilizzando la mediana di un qualsiasi numero di scelte elementi predeterminati. Ad esempio, un metodo comune è quello di scegliere la mediana di primi elementi, ultimi, e medi come il perno. Anche con il metodo della mediana-di-3 appena descritto, alcuni dati possono facilmente dare O (N ^ 2) tempo complessità. Un esempio di dati è il cosiddetto organo tubi set di dati:

array = [1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,3,2,1]

randomizzato

quicksorts Randomizated possono scegliere solo un perno casuale o utilizzare la mediana di un numero di perni scelti a caso. C'è ancora la possibilità di O (N ^ 2) la complessità di tempo, ma la probabilità è molto, molto più piccolo e diventa più piccolo con l'aumentare della dimensione del set di dati.

Answer 7

Oltre a ciò che molti altri hanno già detto di come una sorta rapido deterministico è implementato e uno non deterministico è, credo uno, molto più importante aspetto di tale tipo, è che, con il deterministica quicksort, si ha sempre lo stesso ordine dei record quando i tasti si scontrano, mentre con non deterministici quicksorts, l'ordine di tali documenti può essere diverso ogni volta che si esegue il genere.

Credo che non si dovrebbe usare quicksorting non deterministica quando si dispone di chiavi non univoche.