Quicksort: scelta del perno

StackOverflow https://stackoverflow.com/questions/164163

Domanda

Quando si implementa Quicksort, una delle cose che devi fare è scegliere un perno. 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 scenari diversi richiedono o meno strategie diverse.

È stato utile?

Soluzione

La scelta di un perno casuale riduce al minimo la possibilità di riscontrare prestazioni O (n 2 ) nel peggiore dei casi (scegliere sempre il primo o l'ultimo comporterebbe prestazioni nel peggiore dei casi quasi ordinate o quasi inverse dati assortiti). Anche la scelta dell'elemento intermedio sarebbe accettabile nella maggior parte dei casi.

Inoltre, se lo stai implementando tu stesso, ci sono versioni dell'algoritmo che funzionano sul posto (cioè senza creare due nuovi elenchi e poi concatenarli).

Altri suggerimenti

Dipende dalle tue esigenze. La scelta casuale di un perno rende più difficile la creazione di un set di dati che genera prestazioni O (N ^ 2). Anche la "mediana dei tre" (primo, ultimo, medio) è un modo per evitare problemi. Attenzione alle prestazioni relative dei confronti, tuttavia; se i tuoi confronti sono costosi, Mo3 fa più confronti che scegliere (un singolo valore pivot) a caso. I record del database possono essere costosi da confrontare.

Aggiornamento: inserimento dei commenti in risposta.

mdkess affermato:

  

'Median of 3' NON è il primo ultimo medio. Scegli tre indici casuali e prendi il valore medio di questo. Il punto è assicurarsi che la scelta dei perni non sia deterministica, in caso contrario, i dati del caso peggiore possono essere generati abbastanza facilmente.

A cui ho risposto:

  • Analisi dell'algoritmo di ricerca di Hoare con Median-Of -Tre Partition (1997) di P Kirschenhofer, H Prodinger, C Mart e # 237; nez supporta la tua tesi (che "median-of-three" è tre elementi casuali).

  • C'è un articolo descritto nel portale .acm.org parla di "The Peorst Case Permutation for Median-of-Three Quicksort" di Hannu Erki & # 246; pubblicato su The Computer Journal, Vol 27, No 3, 1984. [Aggiornamento 2012-02 -26: ho ricevuto il testo per articolo . La sezione 2 "L'algoritmo" inizia: " Usando la mediana del primo, medio e ultimo elemento di A [L: R], è possibile ottenere partizioni efficienti in parti di dimensioni abbastanza uguali nella maggior parte delle situazioni pratiche. 'Pertanto, sta discutendo l'approccio Mo3 primo-ultimo-ultimo.]

  • Un altro breve articolo interessante è di MD McIlroy, " A Killer Adversary for Quicksort " , pubblicato in Software-Practice and Experience, Vol. 29 (0), 1 & # 8211; 4 (0 1999). Spiega come far quadrare quasi tutti i Quicksort.

  • AT & amp; T Bell Labs Tech Journal, ottobre 1984 "Teoria e pratica nella costruzione di una routine di ordinamento funzionante" stati " Hoare ha suggerito il partizionamento attorno alla mediana di diverse linee selezionate casualmente. Sedgewick [...] ha raccomandato di scegliere la mediana del primo [...] ultimo [...] e medio ". Ciò indica che entrambe le tecniche per la "mediana dei tre" sono note in letteratura. (Aggiornamento 23/11/2014: l'articolo sembra essere disponibile all'indirizzo IEEE Xplore o da Wiley & # 8212; se disponi di un abbonamento o sei disposto a pagare una tassa.)

  • 'Engineering a Sort Function' di JL Bentley e MD McIlroy, pubblicato in Software Practice and Experience, Vol 23 (11), novembre 1993, entra in una discussione approfondita dei problemi e scelgono un algoritmo di partizionamento adattivo basato in parte sulla dimensione dei dati impostato. Si discute molto di compromessi per vari approcci.

  • Una ricerca su Google di "mediana dei tre" funziona abbastanza bene per un ulteriore monitoraggio.

Grazie per l'informazione; In precedenza avevo incontrato solo la "mediana dei tre" deterministica.

Heh, ho appena insegnato questa lezione.

Esistono diverse opzioni.
Semplice: scegli il primo o l'ultimo elemento dell'intervallo. (non valido su input parzialmente ordinati) Migliore: scegli l'elemento al centro dell'intervallo. (meglio su input parzialmente ordinato)

Tuttavia, la selezione di qualsiasi elemento arbitrario comporta il rischio di partizionare male l'array di dimensioni n in due array di dimensioni 1 e n-1. Se lo fai abbastanza spesso, il tuo quicksort corre il rischio di diventare O (n ^ 2).

Un miglioramento che ho visto è quello di scegliere la mediana (primo, ultimo, metà); Nel peggiore dei casi, può ancora andare su O (n ^ 2), ma probabilmente, questo è un caso raro.

Per la maggior parte dei dati, è sufficiente selezionare il primo o l'ultimo. Ma, se ti accorgi spesso di imbatterti in scenari peggiori (input parzialmente ordinato), la prima opzione sarebbe quella di scegliere il valore centrale (che è un perno statisticamente buono per i dati parzialmente ordinati).

Se i problemi persistono, seguire la via mediana.

Mai e poi mai scegliere un perno fisso: questo può essere attaccato per sfruttare il runtime O (n ^ 2) peggiore dell'algoritmo, che richiede solo problemi. Il peggior runtime di Quicksort si verifica quando il partizionamento produce un array di 1 elemento e un array di n-1 elementi. Supponiamo di scegliere il primo elemento come partizione. Se qualcuno alimenta un array nel tuo algoritmo in ordine decrescente, il tuo primo perno sarà il più grande, quindi tutto il resto dell'array si sposterà a sinistra di esso. Quindi quando ricorri, il primo elemento sarà di nuovo il più grande, quindi ancora una volta metti tutto alla sua sinistra e così via.

Una tecnica migliore è il metodo della mediana di 3, in cui scegli tre elementi a caso e scegli il centro. Sai che l'elemento che scegli non sarà il primo o l'ultimo, ma anche, secondo il 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 desidera assolutamente garantire il runtime O (nlgn) per l'algoritmo, il metodo colonne-di-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 il caso peggiore sarà T (n) = O (n) (trova la mediana) + O (n) (partizione) + 2T (n / 2) (recitazione sinistra e destra.) Secondo il Teorema del Maestro, questo è O (n lg n). Tuttavia, il fattore costante sarà enorme, e se la peggiore delle prestazioni è la tua preoccupazione principale, usa invece un tipo di unione, che è solo un po 'più lento di quicksort in media e garantisce il tempo O (nlgn) (e sarà molto più veloce rispetto a questo insulso quicksort mediano).

Spiegazione dell'algoritmo della mediana dei mediani

Non cercare di diventare troppo intelligente e combinare strategie pivotanti. Se hai combinato la mediana di 3 con il perno casuale selezionando la mediana del primo, l'ultimo e un indice casuale nel mezzo, sarai comunque vulnerabile a molte delle distribuzioni che inviano una mediana di 3 quadratico (quindi è effettivamente peggio di semplice perno casuale)

Ad esempio una distribuzione di organo a canne (1,2,3 ... N / 2..3,2,1) prima e ultima saranno entrambe 1 e l'indice casuale sarà un numero maggiore di 1, prendendo la mediana dà 1 ( primo o ultimo) e ottieni un partizionamento estremamente squilibrato.

Dipende interamente dal modo in cui i tuoi dati sono ordinati per cominciare. Se pensi che sarà pseudo-casuale, la tua scommessa migliore è scegliere una selezione casuale o scegliere il centro.

Se stai ordinando una raccolta accessibile in modo casuale (come una matrice), è generalmente meglio scegliere l'elemento fisico medio. Con questo, se l'array è tutto pronto (o quasi ordinato), le due partizioni saranno quasi pari e otterrai la migliore velocità.

Se stai ordinando qualcosa con solo accesso lineare (come un elenco collegato), allora è meglio scegliere il primo elemento, perché è l'elemento più veloce a cui accedere. Qui, tuttavia, se l'elenco è già ordinato, sei fregato: una partizione sarà sempre nulla e l'altra avrà tutto, producendo il momento peggiore.

Tuttavia, per un elenco collegato, scegliere qualsiasi cosa oltre alla prima, peggiorerà le cose. Seleziona l'elemento intermedio in un elenco elencato, dovresti passarlo attraverso ogni passaggio della partizione - aggiungendo un'operazione O (N / 2) che viene eseguita logN volte rendendo il tempo totale O (1.5 N * log N) e questo è se sappiamo quanto è lungo l'elenco prima di iniziare - di solito non lo facciamo, quindi dovremmo fare tutto il passo per contarli, quindi fare un passo a metà per trovare il centro, quindi passare attraverso un terza volta per eseguire la partizione effettiva: O (2.5N * log N)

È più semplice suddividere il quicksort in tre sezioni facendo questo

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

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

Segue il codice: 

/* 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 perno 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. ad 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. scegli il primo, metà, ultimo elemento dell'array. 2. confronta questi tre numeri e trova il numero maggiore di uno e più piccolo dell'altro, ad esempio mediana. 3. rendere questo elemento come elemento pivot.

la scelta del pivot con questo metodo divide l'array in quasi due metà e quindi la complessità riduce a O (nlog (n)).

In media, la mediana di 3 è buona per i piccoli n. La mediana di 5 è leggermente migliore per i n più grandi. Il secondo, che è la "mediana di tre mediane di tre" è ancora meglio per n. molto grandi

Più si va avanti con il campionamento, meglio si ottiene all'aumentare di n, ma il miglioramento diminuisce notevolmente all'aumentare dei campioni. E si incorre nell'overhead del campionamento e dell'ordinamento dei campioni.

Consiglio di utilizzare l'indice centrale, poiché può essere calcolato facilmente.

Puoi calcolarlo arrotondando (array.length / 2).

In un'implementazione veramente ottimizzata, il metodo per scegliere il pivot dovrebbe dipendere dalle dimensioni dell'array: per un array di grandi dimensioni, vale la pena dedicare più tempo alla scelta di un buon pivot. Senza fare un'analisi completa, immagino "mezzo di O (log (n)) elementi" è un buon inizio e questo ha l'ulteriore vantaggio di non richiedere memoria aggiuntiva: utilizzando la coda di chiamata sulla partizione più grande e il partizionamento sul posto, utilizziamo la stessa memoria aggiuntiva O (log (n)) in quasi ogni fase di l'algoritmo.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top