Quicksort e pivot centrale

1

Sto avendo un mal di testa che comprende quicksort con pivot centrale. Ho trovato molte spiegazioni sull'utilizzo di più a sinistra o più a destra, ma non molte a metà.

Posso tranquillamente assumerli?:

  1. Se i puntatori sinistro e destro si incontrano nella stessa posizione, significa che il l'elemento in quella posizione è nella sua posizione ordinata finale, quindi posso dividere la lista in due senza includere quell'elemento (lista1 lunghezza + lista2 lunghezza = lista lunghezza -1).

  2. Se la sinistra e la destra si incrociano (così a sinistra > a destra), significa che no l'elemento è ancora nella sua posizione ordinata, quindi devo dividere la lista in due usando sinistra e destra come limiti (lunghezza lista1 + lunghezza lista2 = lunghezza lista).

È giusto?

Grazie.

Aggiornamento : il motivo per cui voglio utilizzare un pivot intermedio è implementare l'algoritmo mediano che aumenta la velocità di QS. In questa tecnica, il pivot viene selezionato approssimando il valore medio dell'elenco: link

    
posta NullOrEmpty 02.05.2013 - 14:06
fonte

1 risposta

0

Se la matrice viene mescolata in modo casuale, in teoria, un elemento nell'elenco è buono come un altro, il che significa che possiamo scegliere in base a ciò che è più conveniente per noi. Tuttavia, va detto che un elemento centrale sarebbe più adatto quando l'array è quasi ordinato (o altrimenti quicksort richiederebbe O (n ^ 2) tempo). La ragione per cui prendiamo l'oggetto centrale è perché è probabilmente rappresentativo di un oggetto in cui metà è meno e metà è più in questo caso, e se fosse casuale, non farebbe molta differenza altrimenti, vero? / p>

Per il gusto di questo esempio, supponiamo che l'array sia mescolato casualmente e quindi chiamiamo arbitrariamente l'elemento più a destra nella lista come pivot. Partendo da sinistra, confronta quel numero con il pivot. Se il numero è inferiore al pivot, vai al numero successivo. Se il numero è maggiore del pivot, procedi come segue:

Se il pivot non è adiacente al numero corrente, il pivot cambia con il suo vicino di sinistra. Il numero corrente viene quindi scambiato con il nuovo slot creato a destra del nuovo pivot. Se il pivot è adiacente al numero corrente, passa semplicemente alla posizione con il numero corrente.

Continua questi passaggi finché l'indice del numero corrente non è uguale o maggiore dell'indice del pivot. Una volta eseguita questa operazione, eseguire una chiamata ricorsiva a una sottolista di tutto sul lato sinistro del perno e un'altra chiamata a una sottolista di tutto sul lato destro del pivot (supponendo che la lunghezza di Sottolista sia 2 o superiore).

Guarda un esempio:

1 4 8 9 2 3 5

5 è il nostro perno. A partire dall'indice 0, otteniamo le seguenti operazioni:

1 4 8 9 2 3 5
^           *
1 4 8 9 2 3 5
  ^         *
1 4 3 9 2 5 8
    ^     *
1 4 3 9 2 5 8
    ^     *
1 4 3 2 5 9 8
      ^ * 
1 4 3 2 5 9 8
      ^ * 

Fine del primo passaggio: chiamata ricorsiva a sottolista a sinistra:

1 4 3 2 
^     *
1 3 2 4 
  ^ *  
1 2 3 4 
  ^ *  

E chiamata ricorsiva alla sottolista di destra:

9 8  
^ *
8 9  
* ^

Spero che chiarisca le cose. Notare come se il numero corrente fosse maggiore del pivot, il numero corrente non aumentava. Questo perché viene sostituito con un altro numero che non è ancora stato gestito, quindi deve essere controllato. So che non è esattamente quello che stavi facendo con il pivot centrale, ma funziona altrettanto bene.

    
risposta data 02.05.2013 - 14:55
fonte

Leggi altre domande sui tag