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.