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:
- 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.
- 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.
- 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.
- 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)
