L’algoritmo di ordinamento rapido (Quick Sort).

Gli algoritmi più famosi
PageRank, Algoritmo di PageRank, Gli algoritmi più famosi, Algoritmo di ordinamento rapido, Algoritmo di Dijkstra, Algoritmo di RSA, Algoritmo di ricerca binaria, Algoritmo di backpropagation, Algoritmo di clustering k-means, Algoritmo di ordinamento a bolle (Bubble Sort),

di Sergio Mauri

L’algoritmo di ordinamento rapido, noto anche come QuickSort, è un efficiente algoritmo di ordinamento basato sul principio della divisione e conquista. È ampiamente utilizzato in pratica a causa della sua velocità e della sua implementazione relativamente semplice.

Ecco una descrizione dell’algoritmo di ordinamento rapido:

  1. Scelta del Pivot: l’algoritmo seleziona un elemento dell’array da ordinare chiamato “pivot”. La scelta del pivot può variare, ma comunemente si utilizza il primo elemento, l’ultimo elemento o un elemento centrale dell’array.
  2. Partizione dell’Array: l’array viene quindi riorganizzato in modo che gli elementi più piccoli del pivot siano posizionati prima del pivot stesso, mentre gli elementi più grandi vengono posizionati dopo di esso. Dopo questa fase, il pivot è nella sua posizione finale e non verrà mai mosso di nuovo.
  3. Ricorsione: l’algoritmo viene applicato ricorsivamente alle due sotto-liste generate dalla fase di partizione, ovvero la parte dell’array che contiene elementi minori del pivot e quella che contiene elementi maggiori del pivot. Questo processo continua fino a quando non si raggiungono delle sotto-liste di dimensione uno o zero, che sono per definizione già ordinate.
  4. Combinazione delle Sub-Arrays Ordinate: una volta che tutte le ricorsioni sono state completate, le sotto-liste ordinate vengono combinate per formare l’array finale ordinato.

Il punto chiave dell’efficienza del QuickSort risiede nella fase di partizione, che viene realizzata in tempo lineare rispetto alla dimensione dell’array. Se la partizione è bilanciata, ovvero suddivide l’array in due parti quasi uguali, l’algoritmo di ordinamento rapido ha una complessità temporale media di O(n log n), dove “n” è la dimensione dell’array da ordinare. Tuttavia, se la partizione non è bilanciata, la complessità temporale potrebbe degradare fino a O(n^2), anche se questo è raro in pratica.

In generale, il QuickSort è un algoritmo molto efficiente e viene spesso preferito per ordinare grandi insiemi di dati in quanto è più veloce rispetto ad altri algoritmi di ordinamento come il MergeSort o l’InsertionSort in molte situazioni.

Ecco un esempio di implementazione dell’algoritmo di ordinamento rapido (QuickSort) in Python:

def quicksort(arr):
if len(arr) <= 1: return arr else: pivot = arr[0] less_than_pivot = [x for x in arr[1:] if x <= pivot] greater_than_pivot = [x for x in arr[1:] if x > pivot]
return quicksort(less_than_pivot) + [pivot] + quicksort(greater_than_pivot)

Esempio di utilizzo

arr = [3, 6, 8, 10, 1, 2, 1]
print(“Array originale:”, arr)
sorted_arr = quicksort(arr)
print(“Array ordinato:”, sorted_arr)

Sergio Mauri
Autore Sergio Mauri Blogger. Premio speciale al Concorso Claudia Ruggeri nel 2007; terzo posto al Premio Igor Slavich nel 2020. Ha pubblicato con Terra d’Ulivi nel 2007 e nel 2011, con Hammerle Editori nel 2013 e 2014 e con Historica Edizioni e Alcova Letteraria nel 2022 e Silele Edizioni (La Tela Nera) nel 2023.
** Se puoi sostenere il mio lavoro, comprami un libro | Buy me a book! **
** ISCRIVITI ALLA NEWSLETTER ! **

About the Author

Sergio Mauri
Blogger, autore. Perito in Sistemi Informativi Aziendali, musicista e compositore, Laurea in Discipline storiche e filosofiche. Premio speciale al Concorso Claudia Ruggeri nel 2007; terzo posto al Premio Igor Slavich nel 2020. Ha pubblicato con Terra d'Ulivi nel 2007 e nel 2011, con Hammerle Editori nel 2013 e 2014, con PGreco nel 2015 con Historica Edizioni e Alcova Letteraria nel 2022 con Silele Edizioni (La Tela Nera) nel 2023 e con Amazon Kdp nel 2024.