Guida all'algoritmo Python Quicksort
Esplora l'algoritmo Quicksort in Python. Scopri la selezione del pivot, il partizionamento e la ricorsione in questo esempio di codice interattivo.
Panoramica
Quicksort è un algoritmo di ordinamento estremamente veloce e ampiamente utilizzato. Come il merge sort, utilizza un approccio divide et impera. Tuttavia, Quicksort ordina gli elementi "sul posto", rendendolo efficiente in termini di memoria.
L'algoritmo funziona selezionando un elemento 'pivot' dall'elenco. Quindi suddivide gli altri elementi in due sottoarray: quelli minori del pivot e quelli maggiori del pivot. Questo processo viene applicato ricorsivamente ai sottoarray.
Sebbene Quicksort abbia una complessità nel caso peggiore pari a O(n²), il suo tempo di esecuzione nel caso medio è O(n log n) e in genere supera il merge sort nella pratica a causa di minori errori di cache e zero spese generali di creazione di array temporanei.
Codice e output di esecuzione
Uno script di ordinamento rapido ricorsivo conciso che utilizza la comprensione degli elenchi per un'elevata leggibilità.
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# Test list
data = [12, 4, 5, 6, 7, 3, 1, 15]
print("Original List:", data)
sorted_data = quicksort(data)
print("Sorted List: ", sorted_data)Original List: [12, 4, 5, 6, 7, 3, 1, 15]
Sorted List: [1, 3, 4, 5, 6, 7, 12, 15]Implementazione passo dopo passo
- Routine di ordinamento del sistema in cui l'ingombro della memoria deve essere mantenuto al minimo
- Ordinamento di uso generale nei framework delle librerie di linguaggi standard
- Insegnamento accademico della meccanica delle partizioni e del divide et impera ricorsivo
Domande frequenti
Come possiamo evitare la complessità del caso peggiore di O(n²) in Quicksort?
Il caso peggiore si verifica quando il perno selezionato è ripetutamente l'elemento più piccolo o più grande. Per mitigare questo problema, gli sviluppatori utilizzano strategie come la scelta di un pivot casuale o dei valori "mediani di tre".
Quicksort è stabile?
No, Quicksort standard è instabile. Durante il partizionamento, gli elementi vengono scambiati su lunghi intervalli, il che può alterare l'ordine relativo degli elementi duplicati.
Argomenti correlati
Scopri come implementare Merge Sort in Python. Un esempio interattivo passo dopo passo della strategia di ordinamento Divide and Conquer.
Algoritmi di ordinamento PythonEsplora gli algoritmi di ordinamento di Python. Visualizza l'ordinamento a bolle e unisci l'ordinamento in modo nativo all'interno del contesto IDE del browser.
Algoritmo di ricerca binaria PythonCerca elenchi ordinati in tempo logaritmico O(log n). Esegui e comprendi la ricerca binaria in Python, inclusa la logica passo passo, i casi limite e le ottimizzazioni.