Quicksort: scelta del pivot

Quando si implementa Quicksort, una delle cose che devi fare è scegliere un pivot. Ma quando guardo lo pseudocodice come quello qui sotto, non è chiaro come dovrei scegliere il perno. Primo elemento dell’elenco? Qualcos’altro?

function quicksort(array) var list less, greater if length(array) ≤ 1 return array select and remove a pivot value pivot from array for each x in array if x ≤ pivot then append x to less else append x to greater return concatenate(quicksort(less), pivot, quicksort(greater)) 

Qualcuno può aiutarmi a comprendere il concetto di scegliere un perno e se diversi scenari richiedono strategie diverse.

La scelta di un pivot casuale minimizza le probabilità che si verifichino le peggiori prestazioni O (n 2 ) (scegliere sempre prima o l’ultima causerebbe le prestazioni nel caso peggiore per dati quasi ordinati o quasi invertiti). La scelta dell’elemento centrale sarebbe accettabile nella maggior parte dei casi.

Inoltre, se si sta implementando questo da soli, ci sono versioni dell’algoritmo che funzionano sul posto (cioè senza creare due nuovi elenchi e quindi concatenandoli).

Dipende dalle tue esigenze La scelta di un pivot a caso rende più difficile la creazione di un set di dati che genera prestazioni O (N ^ 2). “Median-of-three” (primo, ultimo, medio) è anche un modo per evitare problemi. State attenti alle prestazioni relative dei confronti, però; se i tuoi confronti sono costosi, allora Mo3 fa più confronti che scegliere (un singolo valore di pivot) a caso. I record del database possono essere costosi da confrontare.


Aggiornamento: tirando i commenti in risposta.

mdkess ha affermato:

‘Median of 3’ NON è il primo penultimo. Scegli tre indici casuali e prendi il valore medio di questo. Il punto è assicurarsi che la scelta dei pivot non sia deterministica: se lo è, i dati peggiori possono essere generati abbastanza facilmente.

A cui ho risposto:

  • Analisi dell’algoritmo di ricerca di Hoare con la partizione mediana di tre (1997) di P Kirschenhofer, H Prodinger, C Martínez sostiene la tua tesi (che “mediana di tre” è composta da tre elementi casuali).

  • C’è un articolo descritto su portal.acm.org che parla di “The Worst Case Permutation for Median-of-Three Quicksort” di Hannu Erkiö, pubblicato su The Computer Journal, Vol 27, No 3, 1984. [Aggiornamento 2012-02- 26: Hai il testo per l’ articolo . La Sezione 2 “Algoritmo” inizia: ” Utilizzando la mediana del primo, del secondo e dell’ultimo elemento di A [L: R], è ansible ottenere partizioni efficienti in parti di dimensioni abbastanza uguali nella maggior parte delle situazioni pratiche. “Pertanto, si discute dell’approccio Mo3 del primo-medio-ultimo.]

  • Un altro breve articolo interessante è quello di MD McIlroy, “A Killer Adversary for Quicksort” , pubblicato su Software-Practice and Experience, vol. 29 (0), 1-4 (0 1999). Spiega come far quadrare quasi tutti i Quicksort.

  • AT & T Bell Labs Tech Journal, ottobre 1984 “Teoria e pratica nella costruzione di una routine di ordinamento di lavoro” afferma “Hoare ha suggerito il partizionamento intorno alla mediana di diverse linee selezionate casualmente. […] Sedgewick raccomandò di scegliere la mediana del primo [. ..] ultimo […] e medio “. Ciò indica che entrambe le tecniche per “la mediana di tre” sono note in letteratura. (Aggiornamento 2014-11-23: l’articolo sembra essere disponibile presso IEEE Xplore o da Wiley – se sei iscritto o sei disposto a pagare una commissione.)

  • “Engineering a Sort Function” di JL Bentley e MD McIlroy, pubblicato su Software Practice and Experience, Vol 23 (11), novembre 1993, entra in un’approfondita discussione sui problemi e scelgono un algoritmo di partizionamento adattivo basato in parte sul dimensione del set di dati. Vi è molta discussione sui trade-off per vari approcci.

  • Una ricerca su Google per “median-of-three” funziona piuttosto bene per ulteriori tracciamenti.

Grazie per l’informazione; Prima avevo solo incontrato la “mediana dei tre” deterministica.

Heh, ho appena insegnato questa lezione.

Ci sono diverse opzioni
Semplice: scegli il primo o l’ultimo elemento dell’intervallo. (non valido per l’input parzialmente ordinato) Migliore: selezionare l’elemento nel mezzo dell’intervallo. (meglio su input parzialmente ordinati)

Tuttavia, la selezione di qualsiasi elemento arbitrario rischia di scomporre in modo non corretto l’array di dimensione n in due array di dimensioni 1 e n-1. Se lo fai abbastanza spesso, il tuo quicksort rischia di diventare O (n ^ 2).

Un miglioramento che ho visto è il pick median (first, last, mid); Nel peggiore dei casi, può ancora andare a O (n ^ 2), ma probabilisticamente, questo è un caso raro.

Per la maggior parte dei dati, è sufficiente scegliere il primo o l’ultimo. Tuttavia, se si scopre spesso che si imbattono spesso in scenari peggiori (input parzialmente ordinati), la prima opzione consiste nel selezionare il valore centrale (che è un pivot statisticamente valido per dati parzialmente ordinati).

Se i problemi persistono, segui la via mediana.

Mai e poi mai scegliere un pivot fisso – questo può essere attaccato per sfruttare il peggiore runtime O (n ^ 2) del tuo algoritmo, che richiede solo guai. Il runtime peggiore di Quicksort si verifica quando il partizionamento produce un array di 1 elemento e un array di elementi n-1. Supponi di scegliere il primo elemento come partizione. Se qualcuno alimenta un array al tuo algoritmo in ordine decrescente, il tuo primo pivot sarà il più grande, quindi tutto il resto dell’array si sposterà a sinistra di esso. Poi, quando ricerchi, il primo elemento sarà di nuovo il più grande, quindi ancora una volta metti tutto a sinistra e così via.

Una tecnica migliore è il metodo della mediana di 3, in cui scegli tre elementi a caso e scegli la metà. Sai che l’elemento che scegli non sarà il primo o l’ultimo, ma anche, dal teorema del limite centrale, la distribuzione dell’elemento centrale sarà normale, il che significa che tenderai verso il centro (e quindi , n lg n time).

Se si vuole assolutamente garantire il runtime O (nlgn) per l’algoritmo, il metodo colonne-of-5 per trovare la mediana di un array viene eseguito nel tempo O (n), il che significa che l’equazione di ricorrenza per quicksort nel caso peggiore sarà be T (n) = O (n) (trova la mediana) + O (n) (partizione) + 2T (n / 2) (recurse sinistra e destra.) Dal Teorema Master, questo è O (n lg n) . Tuttavia, il fattore costante sarà enorme, e se la prestazione peggiore è la tua preoccupazione principale, usa invece un ordinamento di fusione, che è solo un po ‘più lento di quicksort in media, e garantisce il tempo O (nlgn) (e sarà molto più veloce di questo quicksort mediocre).

Spiegazione dell’algoritmo della mediana della mediana

Non cercare di diventare troppo intelligente e combinare strategie pivotanti. Se hai combinato la mediana di 3 con il pivot casuale selezionando la mediana del primo, dell’ultimo e di un indice casuale nel mezzo, allora sarai comunque vulnerabile a molte delle distribuzioni che inviano una mediana di 3 quadratici (quindi è in realtà peggiore di semplice perno casuale)

Per esempio una distribuzione di organo a canne (1,2,3 … N / 2, 3, 2, 2) prima e l’ultima saranno entrambe 1 e l’indice casuale sarà un numero maggiore di 1, prendendo la mediana da 1 ( o il primo o l’ultimo) e si ottiene un partizionamento estremamente squilibrato.

Dipende interamente da come vengono ordinati i dati per iniziare. Se pensi che sia pseudo-casuale, la soluzione migliore è scegliere una selezione casuale o scegliere la metà.

Se stai ordinando una raccolta accessibile a caso (come un array), è generalmente meglio scegliere l’elemento centrale fisico. Con questo, se l’array è tutto pronto ordinato (o quasi ordinato), le due partizioni saranno quasi uguali e otterrai la migliore velocità.

Se stai ordinando qualcosa con accesso solo lineare (come una lista collegata), allora è meglio scegliere il primo object, perché è l’object più veloce ad accedere. Qui, tuttavia, se la lista è già in ordine, sei fregato: una partizione sarà sempre nullo e l’altra avrà tutto, producendo il momento peggiore.

Tuttavia, per una lista concatenata, scegliere qualcosa oltre al primo, peggiorerà le cose. Scegli l’object intermedio in una lista, dovresti passare attraverso ogni fase della partizione – aggiungendo un’operazione O (N / 2) che viene eseguita logN volte facendo O tempo totale (1.5 N * log N) e questo è se sappiamo quanto è lunga la lista prima di iniziare – di solito non è così che dovremmo fare un passo fino in fondo per contarli, quindi fare un passo a metà per trovare la parte centrale, quindi attraversare un terza volta per fare la partizione effettiva: O (2.5 N * log N)

È più facile suddividere il quicksort in tre sezioni facendo ciò

  1. Scambia o scambia la funzione dell’elemento di dati
  2. La funzione di partizione
  3. Elaborazione delle partizioni

È solo leggermente più inefficace di una funzione lunga, ma è molto più facile da capire.

Il codice segue:

 /* This selects what the data type in the array to be sorted is */ #define DATATYPE long /* This is the swap function .. your job is to swap data in x & y .. how depends on data type .. the example works for normal numerical data types .. like long I chose above */ void swap (DATATYPE *x, DATATYPE *y){ DATATYPE Temp; Temp = *x; // Hold current x value *x = *y; // Transfer y to x *y = Temp; // Set y to the held old x value }; /* This is the partition code */ int partition (DATATYPE list[], int l, int h){ int i; int p; // pivot element index int firsthigh; // divider position for pivot element // Random pivot example shown for median p = (l+h)/2 would be used p = l + (short)(rand() % (int)(h - l + 1)); // Random partition point swap(&list[p], &list[h]); // Swap the values firsthigh = l; // Hold first high value for (i = l; i < h; i++) if(list[i] < list[h]) { // Value at i is less than h swap(&list[i], &list[firsthigh]); // So swap the value firsthigh++; // Incement first high } swap(&list[h], &list[firsthigh]); // Swap h and first high values return(firsthigh); // Return first high }; /* Finally the body sort */ void quicksort(DATATYPE list[], int l, int h){ int p; // index of partition if ((h - l) > 0) { p = partition(list, l, h); // Partition list quicksort(list, l, p - 1); // Sort lower partion quicksort(list, p + 1, h); // Sort upper partition }; }; 

Idealmente il pivot dovrebbe essere il valore medio nell’intero array. Ciò ridurrà le possibilità di ottenere prestazioni nel caso peggiore.

La complessità dell’ordinamento rapido varia notevolmente con la selezione del valore pivot. per esempio se si sceglie sempre il primo elemento come pivot, la complessità dell’algoritmo diventa peggiore di O (n ^ 2). ecco un metodo intelligente per scegliere l’elemento pivot: 1. scegliere il primo, medio, ultimo elemento dell’array. 2. confronta questi tre numeri e trova il numero che è maggiore di uno e più piccolo rispetto ad altri, ad esempio la mediana. 3. rendere questo elemento come elemento di pivot.

scegliendo il pivot con questo metodo si divide l’array in quasi la metà e quindi la complessità si riduce a O (nlog (n)).

In media, la mediana di 3 va bene per la piccola n. La mediana di 5 è un po ‘meglio per il più grande n. Il ninther, che è la “mediana di tre mediane su tre” è ancora meglio per n molto grandi.

Più si va con il campionamento, più si aumenta con n, ma il miglioramento rallenta notevolmente man mano che si aumentano i campioni. E tu incoraggi il sovraccarico di campionare e ordinare i campioni.

Raccomando di usare l’indice medio, in quanto può essere calcolato facilmente.

Puoi calcolarlo arrotondando (array.length / 2).

In un’implementazione veramente ottimizzata, il metodo di scelta di pivot deve dipendere dalla dimensione dell’array: per un array di grandi dimensioni, si paga per dedicare più tempo alla scelta di un buon pivot. Senza fare un’analisi completa, direi che “middle of O (log (n)) elements” è un buon inizio, e questo ha il vantaggio di non richiedere alcuna memoria extra: usando tail-call sulla partizione più grande e in- posiziona il partizionamento, usiamo la stessa memoria aggiuntiva O (log (n)) in quasi tutte le fasi dell’algoritmo.