2015-01-21 16 views
5

Sto leggendo su quicksort, guardando diverse implementazioni e sto cercando di avvolgere la mia mente attorno a qualcosa.Quicksort: posizione di rotazione dopo una partizione

In this attuazione (che di opere corso), il perno viene scelto come elemento centrale e quindi il puntatore di spostamento destra e sinistra a destra e sinistra di conseguenza, scambiando elementi di partizionare attorno al perno.

Stavo provando l'array [4, 3, 2, 6, 8, 1, 0].

Sulla prima partizione, pivot è 6 e tutti gli elementi di sinistra sono già più piccoli di 6, quindi il puntatore a sinistra si fermerà al pivot. Sul lato destro, scambiamo 0 con 6, quindi 1 e 8, quindi alla fine della prima iterazione, la matrice sarà simile a:

[4, 3, 2, 0, 1, 8, 6].

Tuttavia, avevo l'impressione che dopo ogni iterazione in quicksort, il pivot finisse nella sua giusta posizione, quindi qui dovrebbe finire nella posizione 5 dell'array.

Quindi, è possibile (e ok) che il pivot non finisca nella sua iterazione corretta o è qualcosa di ovvio che mi manca?

risposta

3

Esistono numerose varianti dell'algoritmo quicksort. In questo caso, è corretto che il perno non si trovi nella posizione corretta nella sua iterazione.

La caratteristica di definizione di ogni variazione dell'algoritmo quicksort è che dopo la fase di partizione, abbiamo una parte nell'array, dove tutti gli elementi sono inferiori o uguali a pivot e una parte non sovrapposta in la fine dell'array dove tutti gli elementi sono maggiori o uguali a pivot. Potrebbe esserci anche una parte tra di loro, in cui ogni elemento è uguale a pivot. Questo layout garantisce che dopo aver ordinato la parte sinistra e la parte destra con le chiamate ricorsive e aver lasciato intatta la parte centrale, l'intero array verrà ordinato.

Si noti che, in generale, gli elementi uguali a pivot possono passare a qualsiasi parte dell'array. Una buona implementazione di quicksort, che evita il tempo quadratico per il caso più ovvio, cioè tutti gli elementi uguali, deve distribuire elementi uguali a ruotare tra le parti razionalmente.

possibili varianti includono:

  • La parte centrale comprende solo 1 elemento: il perno. In questo caso, pivot occupa la posizione finale nell'array dopo la partizione e non verrà utilizzato nelle chiamate ricorsive. Questo è ciò che intendevi per perno che prende il suo posto nella sua iterazione. Per questo approccio la buona implementazione deve spostare circa metà degli elementi pari a pivot alla parte sinistra e l'altra metà alla parte destra, altrimenti avremmo il tempo quadratico per una matrice con tutti gli elementi uguali.
  • Non c'è una parte centrale. Il pivot e tutti gli elementi uguali sono distribuiti tra la parte sinistra e quella destra. Questo è ciò che fa l'implementazione che hai collegato. Ancora una volta, in questo approccio circa metà degli elementi uguali al perno dovrebbe andare alla parte sinistra e l'altra metà alla parte destra. Questo può anche essere mescolato con la prima variazione, a seconda che stiamo ordinando una matrice con un numero pari o dispari di elementi.
  • Ogni elemento uguale a pivot passa alla parte centrale. Non ci sono elementi uguali a pivot nella parte sinistra o destra. Questo è abbastanza efficiente e questo è l'esempio Wikipedia per risolvere il problema di tutti gli elementi. Array con tutti gli elementi uguali tra loro sono ordinati in tempo lineare in quel caso.

Pertanto, l'attuazione corretta ed efficace di quicksort è abbastanza difficile (c'è anche un problema di scegliere un buon perno, per cui esistono diversi approcci con differenti compromessi pure; o un'ottimizzazione di commutazione ad un altro non algoritmo di ordinamento ricorsivo per dimensioni di sotto-array più piccoli).

Inoltre, sembra che l'attuazione si è collegato al, può fare chiamate ricorsive a sottoarray sovrapposti:

if (i <= j) { 
    exchange(i, j); 
    i++; 
    j--; 
} 

Ad esempio, quando i è uguale a j, questi elementi verranno scambiati, e i diventeranno superiore a j di 2. Dopo che 3 elementi si sovrappongono tra gli intervalli delle seguenti chiamate ricorsive. Il codice sembra funzionare comunque correttamente.

+0

Grazie per l'approfondita redazione, ha reso molto più chiaro. – kenny

Problemi correlati