Quick sort e selezione del pivot
Costruisca quick sort con gli schemi di partizionamento di Lomuto e Hoare, analizzi il caso peggiore O(n²) e scopra come la scelta casuale del pivot lo limiti
Quick sort e selezione del pivot è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Quick sort: divide et impera in-place
Il quick sort è l'algoritmo di ordinamento più usato nella pratica. A differenza del merge sort, ordina in-place senza allocare array aggiuntivi. L'idea fondamentale è scegliere un elemento pivot, partizionare l'array in modo che tutti gli elementi minori del pivot lo precedano e tutti quelli maggiori lo seguano, poi ordinare ricorsivamente ciascuna partizione. Il passaggio di partizionamento richiede tempo O(n) e, con un buon pivot, la profondità della ricorsione è O(log n).
def quick_sort(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
pivot_idx = partition(arr, lo, hi)
quick_sort(arr, lo, pivot_idx - 1) # sort left
quick_sort(arr, pivot_idx + 1, hi) # sort right
def partition(arr, lo, hi):
pivot = arr[hi] # Lomuto: choose last element as pivot
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Schema di partizionamento di Lomuto
Il partizionamento di Lomuto usa l'ultimo elemento come pivot. Un puntatore lento i tiene traccia del confine della regione degli elementi 'minori del pivot'; un puntatore veloce j esegue la scansione in avanti. Quando arr[j] <= pivot, si incrementa i e si scambiano arr[i] e arr[j], estendendo la regione degli elementi minori. Al termine della scansione, si colloca il pivot in i+1 scambiandolo con arr[hi]. È semplice da implementare, ma esegue 3× più scambi rispetto allo schema di Hoare.
def lomuto_partition_traced(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
print(f'Pivot: {pivot}, array: {arr[lo:hi+1]}')
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
print(f'After partition: {arr[lo:hi+1]}')
return i + 1
arr = [3, 1, 4, 1, 5, 9, 2, 6]
lomuto_partition_traced(arr, 0, len(arr)-1)Schema di partizionamento di Hoare
Il partizionamento di Hoare usa due puntatori che partono dalle due estremità e avanzano verso il centro finché non si incrociano. Sceglie il pivot (di solito il primo elemento) e sposta a sinistra gli elementi minori del pivot e a destra quelli maggiori. Lo schema di Hoare esegue 3× meno scambi di Lomuto e funziona meglio con elementi uguali, ma dopo il partizionamento il pivot non si trova nella sua posizione finale: sono quindi necessarie chiamate ricorsive leggermente diverse.
def hoare_partition(arr, lo, hi):
pivot = arr[lo] # first element as pivot
i, j = lo - 1, hi + 1
while True:
i += 1
while arr[i] < pivot: i += 1
j -= 1
while arr[j] > pivot: j -= 1
if i >= j: return j
arr[i], arr[j] = arr[j], arr[i]
def quick_sort_hoare(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
p = hoare_partition(arr, lo, hi)
quick_sort_hoare(arr, lo, p) # note: p not p-1
quick_sort_hoare(arr, p+1, hi)
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_hoare(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Caso peggiore O(n²): input già ordinato
Il caso peggiore del quick sort si verifica quando il pivot è costantemente l'elemento più piccolo o più grande della partizione. Con il pivot sull'ultimo elemento del partizionamento di Lomuto e un array già ordinato, il partizionamento colloca sempre 0 elementi a sinistra e n-1 a destra: l'albero di ricorsione degenera in una catena di profondità n, producendo O(n²) confronti. Per questo la scelta del pivot è fondamentale e le implementazioni di produzione scelgono il pivot in modo casuale.
import sys
sys.setrecursionlimit(5000)
def quick_sort_naive(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
comparisons = [0]
def _qs(lo, hi):
if lo >= hi: return
pivot = arr[hi] # last element pivot
i = lo - 1
for j in range(lo, hi):
comparisons[0] += 1
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
_qs(lo, p-1); _qs(p+1, hi)
_qs(lo, hi)
return comparisons[0]
import math
n = 100
sorted_arr = list(range(n))
ops = quick_sort_naive(sorted_arr)
print(f'n={n}, ops={ops}, n^2={n**2}') # ops close to n*(n-1)/2Pivot casuale: O(n log n) atteso
Scegliendo il pivot uniformemente a caso (si scambia un elemento casuale con arr[hi] prima del partizionamento), la probabilità di scegliere costantemente pivot sfavorevoli diminuisce esponenzialmente. Il numero atteso di confronti è 2n ln(n) ≈ 1.39 n log₂(n), con un tempo atteso O(n log n) con probabilità schiacciante. Per questo il quick sort randomizzato viene usato nella pratica: evita i casi peggiori patologici che un avversario potrebbe creare per strategie con pivot fisso.
import random
def quick_sort_random(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
# Randomise pivot
rand_i = random.randint(lo, hi)
arr[rand_i], arr[hi] = arr[hi], arr[rand_i]
# Lomuto partition with last element as pivot
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
quick_sort_random(arr, lo, p - 1)
quick_sort_random(arr, p + 1, hi)
arr = list(range(100, 0, -1)) # worst case for naive
quick_sort_random(arr)
print(arr[:10]) # [1,2,3,4,5,6,7,8,9,10]Pivot mediano di tre
Un'altra strategia per il pivot consiste nello scegliere la mediana tra il primo elemento, quello centrale e l'ultimo elemento. Questo evita il comportamento del caso peggiore con input ordinati o ordinati al contrario (gli input avversari più comuni), evitando al contempo il costo della generazione di numeri casuali. Molte implementazioni di produzione usano la mediana di tre o il ninther (mediana di tre mediane) per gli array grandi e passano all'insertion sort per i sottoarray piccoli, al di sotto di una soglia di ~10 elementi.
def median_of_three(arr, lo, hi):
mid = (lo + hi) // 2
# Sort lo, mid, hi values in place
if arr[lo] > arr[mid]: arr[lo], arr[mid] = arr[mid], arr[lo]
if arr[lo] > arr[hi]: arr[lo], arr[hi] = arr[hi], arr[lo]
if arr[mid] > arr[hi]: arr[mid], arr[hi] = arr[hi], arr[mid]
# Median is now at arr[mid]; swap to arr[hi-1] as pivot
arr[mid], arr[hi] = arr[hi], arr[mid]
return arr[hi] # pivot value
arr = [3, 9, 1]
print(median_of_three(arr, 0, 2), arr) # 3, [1,3,9] (sorted)Bandiera nazionale olandese: partizionamento a tre vie
Il partizionamento standard colloca a sinistra del pivot gli elementi minori e a destra quelli maggiori, ma gli elementi uguali al pivot rimangono sparsi. Il partizionamento a tre vie (bandiera nazionale olandese) crea tre regioni: <pivot, ==pivot, >pivot. È fondamentale per gli array con molti duplicati: il quick sort standard degrada a O(n²), mentre il quick sort a tre vie raggiunge O(n) per input costituiti da valori tutti uguali.
def three_way_partition(arr, lo, hi):
pivot = arr[lo]
lt = lo # arr[lo..lt-1] < pivot
gt = hi # arr[gt+1..hi] > pivot
i = lo # current
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1; i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1 # don't advance i
else:
i += 1
return lt, gt # pivot occupies arr[lt..gt]
arr = [3, 1, 4, 1, 5, 9, 2, 6, 3, 3]
lt, gt = three_way_partition(arr, 0, len(arr)-1)
print(arr, '| pivot region:', lt, 'to', gt)Quickselect: k-esimo elemento più piccolo in O(n)
Quickselect usa il passaggio di partizionamento del quick sort per trovare il k-esimo elemento più piccolo in tempo medio O(n), senza ordinare completamente. Dopo il partizionamento, il pivot si trova nella posizione finale p. Se p == k, si restituisce arr[p]. Se k < p, si ricorre sulla partizione sinistra; se k > p, su quella destra. In media, ogni ricorsione dimezza il problema: O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n).
import random
def quickselect(nums, k):
'''Find kth smallest (0-indexed) in O(n) average.'''
def _select(lo, hi):
if lo == hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]
i = lo - 1
for j in range(lo, hi):
if nums[j] <= pivot:
i += 1; nums[i], nums[j] = nums[j], nums[i]
p = i + 1
nums[p], nums[hi] = nums[hi], nums[p]
if p == k: return nums[p]
elif k < p: return _select(lo, p - 1)
else: return _select(p + 1, hi)
return _select(0, len(nums) - 1)
print(quickselect([3,2,1,5,6,4], 1)) # 2 (2nd smallest)Complessità spaziale del quick sort
Il quick sort viene definito 'in-place', ma usa in media spazio dello stack O(log n) per la ricorsione (un frame per livello dell'albero di ricorsione). Nel caso peggiore, la profondità dello stack è O(n). Per garantire uno spazio dello stack O(log n) nel caso peggiore, si ricorre sempre prima sulla partizione più piccola e si usa l'ottimizzazione delle chiamate in coda per quella più grande. Il limite di ricorsione di Python rende rischiose le ricorsioni molto profonde del quick sort: vale la pena menzionarlo nei colloqui.
def quick_sort_optimised(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
while lo < hi:
p = lomuto_partition_qs(arr, lo, hi)
# Recurse on smaller partition; iterate on larger
if p - lo < hi - p:
quick_sort_optimised(arr, lo, p - 1)
lo = p + 1 # tail-call elimination
else:
quick_sort_optimised(arr, p + 1, hi)
hi = p - 1
def lomuto_partition_qs(arr, lo, hi):
pivot = arr[hi]; i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot: i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1Confronto tra algoritmi di ordinamento
Riunisca le sue conoscenze:
- Quick sort: O(n log n) atteso, O(n²) nel caso peggiore, spazio O(log n), non stabile, più veloce nella pratica con dati casuali
- Merge sort: O(n log n) garantito, spazio O(n), stabile, migliore per liste concatenate e ordinamento esterno
- Heap sort: O(n log n) garantito, spazio O(1), non stabile, più lento nella pratica a causa dei cache miss
- Insertion sort: caso migliore O(n), ideale per n piccolo o dati quasi ordinati
# Python's sorted() uses Timsort:
# - Hybrid: merge sort for large runs, insertion sort for small (< 64 elements)
# - Stable, O(n log n) worst case
# - O(n) best case for sorted/reverse-sorted/nearly-sorted
# - O(n) extra space
import random
arr = random.sample(range(10000), 1000)
sorted_arr = sorted(arr) # Timsort
print(sorted_arr[:5], '...') # first 5 elementsIntrosort: combinare tutti e tre
Introsort (usato in C++ STL std::sort) combina quick sort, heap sort e insertion sort: inizia con il quick sort randomizzato; se la profondità della ricorsione supera 2 log n (segno di una sequenza di pivot sfavorevoli), passa all'heap sort per garantire O(n log n); usa l'insertion sort per i sottoarray più piccoli di 16 elementi. In questo modo si ottiene un caso peggiore O(n log n), con la velocità media del quick sort e l'efficienza dell'insertion sort per i sottoarray piccoli.
# Introsort hybrid (simplified)
def introsort(arr, depth_limit=None):
if depth_limit is None:
import math
depth_limit = 2 * int(math.log2(len(arr) + 1)) if arr else 0
if len(arr) <= 16:
# insertion sort for small arrays
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1
arr[j+1] = key
return arr
if depth_limit == 0:
arr.sort() # fall back to heapsort equivalent
return arr
# Otherwise quick sort
pivot = arr[-1]
small = [x for x in arr[:-1] if x <= pivot]
large = [x for x in arr[:-1] if x > pivot]
return introsort(small, depth_limit-1) + [pivot] + introsort(large, depth_limit-1)
print(introsort([5,3,8,1,9,2,7]))Verifica rapida
Metta alla prova la sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato: il quick sort partiziona l'array in-place attorno a un pivot e ricorre su entrambi i lati, ottenendo in media un tempo O(n log n) con spazio dello stack O(log n), ed è più veloce nella pratica del merge sort con dati casuali, il caso peggiore O(n²) si verifica con input ordinato e pivot fisso e si evita scegliendo il pivot in modo casuale o usando la mediana di tre e il partizionamento a tre vie gestisce in modo efficiente gli elementi duplicati, mentre quickselect estende l'idea del partizionamento per trovare il k-esimo elemento più piccolo in tempo medio O(n) senza un ordinamento completo. Ora esploreremo gli algoritmi di ordinamento non basati sui confronti e l'ordinamento integrato di Python.
Domande Frequenti
La lezione «Quick sort e selezione del pivot» è gratuita?
Sì — il testo completo di «Quick sort e selezione del pivot» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Quick sort e selezione del pivot»?
Costruisca quick sort con gli schemi di partizionamento di Lomuto e Hoare, analizzi il caso peggiore O(n²) e scopra come la scelta casuale del pivot lo limiti Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Quick sort e selezione del pivot»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Bubble sort e insertion sort
- Merge sort: dividere, ordinare, unire
- Quick sort e selezione del pivot
- Ordinamenti non basati sui confronti e sort() di Python