Coursera Learner working on a presentation with Coursera logo and
Coursera Learner working on a presentation with Coursera logo and

L’ordinamento rapido è abbastanza simile all’ordinamento misto, nel senso che questo algoritmo aiuta i programmatori a dividere e conquistare. Sceglie gli elementi come perno, dopodiché crea partizioni nell’array. Quick sort ha numerose versioni e ognuna di esse sceglie il perno in modo diverso.

Il comando partition() è probabilmente la parte più importante di quick sort. Gli obiettivi della partizione ricevono un array con un elemento dell’array x come perno. È necessario posizionare la x nella posizione giusta, ovvero nell’array ordinato, seguito da elementi più piccoli di x. Infine, è necessario posizionare gli elementi più grandi di x. Infine, bisogna posizionare gli elementi più grandi di x dopo di esso. Assicuratevi di fare tutto questo in tempo lineare.

Vale anche la pena di ricordare che quick sort crea partizioni negli array, dopodiché richiama se stesso in ripetizione due volte per ordinare i sottoarray risultanti. Un algoritmo come questo è incredibilmente utile per gli insiemi di dati di grandi dimensioni. Questo perché O(n2) è la sua complessità nel caso peggiore. I due termini iniziali servono per le chiamate ricorsive, mentre il termine finale è utile nel processo di partizione. Gli elementi più piccoli del pivot sono rappresentati da k.

Il tempo impiegato dall’ordinamento rapido dipende dalla strategia di partizione e dall’array di input.

I tre casi di ordinamento rapido

Come altri algoritmi di ordinamento, anche il quick sort presenta dei casi. Discutiamoli qui di seguito:

Caso peggiore

Questo tipo di caso si verifica quando il processo di partizione sceglie l’elemento più piccolo o più grande come perno. Considerando la strategia di partizione discussa in precedenza, in cui l’elemento finale viene scelto ogni volta come perno, lo scenario peggiore si verificherà una volta che l’array viene ordinato in ordine decrescente o crescente. La ricorrenza per il caso peggiore è la seguente:

T(n) = T(0) + T(n-1) + (n)che è equivalente a T(n) = T(n-1) + (n)

Caso migliore

Il caso migliore si verifica quando il processo di partizione sceglie l’elemento centrale come perno. La ricorrenza per il caso migliore è la seguente:

T(n) = 2T(n/2) + (n)

Caso medio

È necessario considerare ogni permutazione dell’array e calcolare il tempo impiegato da ogni permutazione per eseguire l’analisi dei casi. Naturalmente questo processo può essere piuttosto complicato, anche per i programmatori più esperti. Detto questo, prendendo in considerazione il caso in cui la partizione pone O(n/9) insieme a O(9n/10) elementi si può ottenere una stima del caso medio. La ricorrenza di questo caso è la seguente.

T(n) = T(n/9) + T(9n/10) + (n)

Domande comuni sull’ordinamento rapido

Sebbene siano molte le domande poste sul quick sort, quelle citate di seguito sono probabilmente le più comuni:

Quick sort è un algoritmo stabile?

L’implementazione predefinita di quick sort non è stabile. Detto questo, è possibile aggiungere stabilità agli algoritmi di ordinamento considerando l’indice come parametro di confronto.

Che cos’è l’ordinamento rapido a tre vie?

Quando si tratta di un normale algoritmo di ordinamento rapido, si sceglie un elemento che funge da perno e si crea una partizione nell’array. Dopodiché si ricorre per le matrici secondarie presenti sui lati destro e sinistro del perno.

Quick Sort è un algoritmo in-place?

Secondo l’ampia definizione di algoritmo in-place, Quick Sort si qualifica effettivamente come questo tipo di algoritmo di ordinamento. Questo perché utilizza uno spazio extra per memorizzare le chiamate alle funzioni ricorsive. Tuttavia, non manipola in alcun modo l’input.

Più veloce della maggior parte degli algoritmi di ordinamento

Sebbene sia innegabile che la complessità temporale del quick sort nel caso peggiore sia O(n2), più di heap sort, merge sort e numerosi altri algoritmi di ordinamento, quick sort è incredibilmente veloce. Uno dei motivi è che è possibile implementare in modo efficiente il suo ciclo interno in diversi tipi di dati e architetture del mondo reale.
Inoltre, è possibile implementare l’ordinamento rapido in diversi modi, semplicemente cambiando la scelta del pivot. In questo modo si riduce al minimo il verificarsi del caso peggiore per qualsiasi tipo di dati. Detto questo, i programmatori in genere preferiscono usare il merge sort quando ci sono troppi dati, soprattutto se si trovano in una memoria esterna.

Che dire dell’uso dell’ordinamento rapido negli elenchi collegati

Quando si tratta di elenchi collegati, le cose sono molto diverse a causa delle differenze presenti nell’allocazione della memoria dell’array. I nodi degli elenchi collegati sono molto diversi dagli array e spesso non sono adiacenti nella memoria. Inoltre, gli elenchi collegati consentono di inserire elementi al centro, cosa che non è possibile negli array. In questi scenari, i programmatori preferiscono usare il merge sort, che si rivela un’opzione più valida rispetto al quick sort.

Perché i programmatori preferiscono l’ordinamento rapido per ordinare gli array

L’ordinamento rapido è un semplice ordinamento in-place, il che significa che non ha bisogno di memoria aggiuntiva. D’altra parte, il merge sort ha bisogno di O(N) memoria aggiuntiva. Per chi se lo stesse chiedendo, N indica la dimensione dell’array, che potrebbe essere incredibilmente ampia. La disallocazione e l’allocazione dello spazio extra richiesto per il merge sort aumenta il tempo di esecuzione dell’algoritmo.

Una volta confrontata la complessità media, è facile vedere che la complessità media di entrambi i tipi di ordinamento è O(NlogN). Tuttavia, le loro costanti tendono a differire. Quando si tratta di array, il merge sort non ha successo perché utilizza uno spazio di archiviazione aggiuntivo di O(N). Le implementazioni più pratiche di ordinamento rapido utilizzano la versione randomizzata. La complessità temporale media di questa versione è O(nLogn). Vale la pena di tenere presente che la versione randomizzata può presentare un caso peggiore. Tuttavia, ciò non si verifica per modelli specifici, come ad esempio gli array ordinati.

L’algoritmo di ordinamento rapido è abbastanza facile da memorizzare nella cache grazie alla sua eccellente località di riferimento, in particolare quando lo si utilizza per gli array. Inoltre, si dà il caso che quick sort sia anche ricorsivo in coda, il che significa che è necessario eseguire ottimizzazioni per le chiamate in coda.