Ordinamenti non basati sui confronti e sort() di Python
Esplori counting sort e radix sort per gli array di interi e capisca come funziona internamente Timsort di Python nelle chiamate all'ordinamento integrato sort
Ordinamenti non basati sui confronti e sort() di Python è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 4 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 DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Il limite inferiore O(n log n) per i confronti
Qualsiasi algoritmo di ordinamento che determina l'ordine solo tramite confronti tra elementi richiede almeno Ω(n log n) confronti nel caso peggiore. Questo è dimostrato dall'argomento dell'albero decisionale: ordinare n elementi richiede distinguere tra n! possibili ordinamenti. Un albero decisionale binario (ogni nodo è un confronto) necessita di almeno log₂(n!) ≈ n log₂(n) livelli. Per superare questo limite, sono necessarie informazioni aggiuntive sugli elementi, ad esempio che siano interi con intervallo limitato.
import math
for n in [5, 10, 100, 1000]:
lower_bound = n * math.log2(n)
factorial_log = sum(math.log2(i) for i in range(1, n+1))
print(f'n={n}: n*log2(n)={lower_bound:.1f}, log2(n!)={factorial_log:.1f}')
# n log n is a tight bound on comparison-based sortingCounting sort: ordinare per frequenza
Il counting sort funziona contando la frequenza di ogni valore e ricostruendo poi l'array ordinato a partire dai conteggi. Richiede di conoscere in anticipo l'intervallo [0, k) dei valori. Complessità temporale: O(n + k); complessità spaziale: O(k). Per k piccolo rispetto a n (ad esempio per ordinare età comprese tra 0 e 120 o singole cifre), il counting sort è più veloce di tutti gli algoritmi di ordinamento basati sui confronti. Per k grande, il costo in spazio O(k) lo rende poco pratico.
def counting_sort(arr, k=None):
if not arr: return []
if k is None: k = max(arr) + 1
count = [0] * k
for n in arr:
count[n] += 1
result = []
for val, freq in enumerate(count):
result.extend([val] * freq)
return result
arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr)) # [1, 2, 2, 3, 3, 4, 8]
# O(n + k) where k = 9 (max value + 1)Counting sort stabile con conteggi cumulativi
Per un counting sort stabile (importante quando si ordinano oggetti in base a una chiave), calcoli i conteggi cumulativi in modo che cum[v] restituisca la posizione iniziale del valore v nell'output. Scorra l'array di input da destra a sinistra, inserendo ogni elemento nella posizione cum[key] - 1 e decrementando tale posizione. In questo modo si ottiene un ordinamento stabile: gli elementi con la stessa chiave mantengono il loro ordine relativo originale.
def counting_sort_stable(arr, k):
count = [0] * k
for n in arr: count[n] += 1
# Cumulative counts: count[v] = first position for value v
for i in range(1, k): count[i] += count[i-1]
output = [0] * len(arr)
# Fill from right to maintain stability
for n in reversed(arr):
count[n] -= 1
output[count[n]] = n
return output
print(counting_sort_stable([4,2,2,8,3,3,1], 9))
# [1, 2, 2, 3, 3, 4, 8]Radix sort: ordinamento cifra per cifra
Il radix sort ordina gli interi cifra per cifra, dalla cifra meno significativa (LSD) a quella più significativa (MSD), utilizzando un ordinamento stabile (come il counting sort) a ogni posizione. Dopo d passaggi, uno per ogni cifra, l'array è completamente ordinato. Complessità temporale: O(d × (n + k)), dove d = numero di cifre e k = base (di solito 10). Per n interi limitati da W, d = log_k(W), quindi il costo totale è O(n log_k(W)).
def radix_sort(arr):
if not arr: return []
max_val = max(arr)
exp = 1 # current digit position (1, 10, 100, ...)
while max_val // exp > 0:
arr = counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for n_ in arr: count[(n_ // exp) % 10] += 1
for i in range(1, 10): count[i] += count[i-1]
for n_ in reversed(arr):
d = (n_ // exp) % 10
count[d] -= 1
output[count[d]] = n_
return output
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]Bucket sort: distribuzione nei bucket
Il bucket sort distribuisce gli elementi in un numero fisso di bucket in base all'intervallo dei valori, ordina ogni bucket (con l'insertion sort per i bucket piccoli) e concatena i risultati. Per dati distribuiti uniformemente nell'intervallo [0, 1), n bucket garantiscono un tempo medio O(n). Complessità: O(n + k) in media, O(n²) nel caso peggiore (quando tutti gli elementi finiscono nello stesso bucket). È particolarmente utile quando la distribuzione dei dati è nota e approssimativamente uniforme.
def bucket_sort(arr):
if not arr: return []
n = len(arr)
min_v, max_v = min(arr), max(arr)
if min_v == max_v: return arr[:]
buckets = [[] for _ in range(n)]
# Map each value to a bucket index
for v in arr:
idx = int((v - min_v) / (max_v - min_v + 1e-9) * n)
idx = min(idx, n - 1)
buckets[idx].append(v)
result = []
for bucket in buckets:
bucket.sort() # insertion sort for small buckets
result.extend(bucket)
return result
print(bucket_sort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21]))
# sorted listIl Timsort di Python sotto il cofano
sorted() e list.sort() di Python utilizzano il Timsort, progettato da Tim Peters nel 2002. Timsort è un ibrido di merge sort e insertion sort. Cerca le «natural run» (sottosequenze già ordinate) e utilizza l'insertion sort per creare run di massimo 64 elementi. Successivamente fonde le run tramite merge sort, con diverse ottimizzazioni: il galloping (che salta gruppi di elementi quando una run è dominante) e l'impilamento delle run.
# Timsort properties:
# - Stable
# - O(n log n) worst case
# - O(n) best case (data already sorted)
# - O(n) auxiliary space
# - Highly optimised for real-world data with runs
import time
# Nearly sorted data: Timsort is extremely fast
nearly_sorted = list(range(10000))
nearly_sorted[-1] = 0 # one mis-placed element
t = time.perf_counter()
not_used = sorted(nearly_sorted)
elapsed = time.perf_counter() - t
print(f'Timsort on nearly-sorted n=10000: {elapsed*1000:.3f} ms')Python: sort() vs sorted(): differenze principali
list.sort() ordina direttamente la lista, restituisce None e funziona solo sulle liste. sorted(iterable) funziona con qualsiasi iterabile (tuple, generatori, dizionari) e restituisce una nuova lista. Entrambi accettano i parametri key e reverse. Un errore comune consiste nell'assegnare il valore restituito da lst.sort() a una variabile e chiedersi perché sia None. Utilizzi sempre sorted() quando le serve la versione ordinata e vuole conservare l'originale.
nums = [3, 1, 4, 1, 5, 9]
# in-place: returns None
result = nums.sort()
print(result) # None (common bug!)
print(nums) # [1, 1, 3, 4, 5, 9] (modified)
nums2 = [3, 1, 4, 1, 5, 9]
# out-of-place: returns new list
result2 = sorted(nums2)
print(result2) # [1, 1, 3, 4, 5, 9]
print(nums2) # [3, 1, 4, 1, 5, 9] (unchanged)Chiavi di ordinamento personalizzate nei colloqui
L'ordinamento di Python accetta una funzione key valutata una sola volta per elemento (a differenza del comparatore di C, chiamato per ogni coppia). Chiavi di ordinamento comuni nei colloqui: len per la lunghezza delle stringhe, lambda x: -x per l'ordine decrescente, lambda x: (x[1], x[0]) per un ordinamento con più chiavi e str.lower per ignorare la distinzione tra maiuscole e minuscole. L'ordinamento di Python è garantito stabile, quindi gli ordinamenti con più chiavi funzionano correttamente.
# Sort by length, then alphabetically
words = ['banana', 'fig', 'apple', 'date', 'kiwi']
print(sorted(words, key=lambda w: (len(w), w)))
# ['fig', 'date', 'kiwi', 'apple', 'banana']
# Sort integers as strings (largest concatenation first)
nums = [3, 30, 34, 5, 9]
print(sorted(map(str, nums), key=lambda a: a*10, reverse=True))
# ['9', '5', '34', '3', '30'] => '9534330'
# Descending sort
print(sorted([3,1,4,1,5], reverse=True)) # [5,4,3,1,1]Quando usare ciascun algoritmo di ordinamento nei colloqui
Scelga l'algoritmo di ordinamento adatto al contesto:
- utilizzi Python's sorted()/list.sort(): è la scelta predefinita per tutti i problemi da colloquio; Timsort è ottimale
- counting sort: quando i valori sono interi piccoli e limitati (da 0 a k, con k piccolo)
- radix sort: quando deve ordinare molti interi con una larghezza in bit o un numero di cifre noto
- bucket sort: quando i dati sono numeri in virgola mobile distribuiti uniformemente in un intervallo noto
- implementi il merge sort: quando le viene chiesto di scrivere da zero un ordinamento stabile O(n log n)
# Problem: sort array of 0s, 1s, 2s efficiently
# Counting sort: O(n), O(1) space (k=3 is tiny)
def sort_012(arr):
count = [0, 0, 0]
for n in arr:
count[n] += 1
i = 0
for val in range(3):
for _ in range(count[val]):
arr[i] = val; i += 1
arr = [2, 0, 2, 1, 1, 0]
sort_012(arr)
print(arr) # [0, 0, 1, 1, 2, 2]Ordinare senza ordinare: top-k con un heap
Molti problemi da colloquio richiedono risultati simili a quelli di un ordinamento senza eseguire un ordinamento completo. Per trovare i k elementi più grandi, un min-heap di dimensione k richiede O(n log k), un tempo migliore di O(n log n) quando k << n. Per trovare il k-esimo elemento più grande, quickselect richiede O(n) in media. Per trovare la mediana, l'approccio con due heap richiede O(log n) per inserimento. È utile conoscere questi approcci di ordinamento parziale come alternative più rapide all'ordinamento completo.
import heapq
# Top-k with heap: O(n log k)
def top_k(nums, k):
return heapq.nlargest(k, nums) # uses heap of size k internally
print(top_k([3,2,1,5,6,4], 2)) # [6, 5]
# kth largest: quickselect O(n) average
import random
def kth_largest(nums, k):
def _select(lo, hi, target):
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]
nums[i+1],nums[hi]=nums[hi],nums[i+1]
p = i + 1
if p == target: return nums[p]
return _select(lo, p-1, target) if target < p else _select(p+1, hi, target)
return _select(0, len(nums)-1, k-1)
print(kth_largest([3,2,1,5,6,4], 2)) # 5Stabilità dell'ordinamento con più chiavi
La stabilità consente di eseguire correttamente ordinamenti con più chiavi: ordini prima in modo stabile per la chiave secondaria, poi in modo stabile per quella primaria. L'ordine secondario viene preservato quando si verificano parità nella chiave primaria. Questa tecnica viene utilizzata nei database (ORDER BY col1, col2) e nel radix sort (ogni passaggio sulle cifre deve essere stabile affinché l'algoritmo complessivo sia corretto). L'ordinamento di Python è sempre stabile, quindi questo schema funziona in modo affidabile.
data = [
('Alice', 'Math', 90),
('Bob', 'Science', 85),
('Carol', 'Math', 90),
('Dave', 'Science', 90),
]
# Sort by score DESC, then by subject ASC (for ties)
# Step 1: sort by subject (secondary)
data.sort(key=lambda x: x[1])
# Step 2: sort by score DESC (primary, stable)
data.sort(key=lambda x: x[2], reverse=True)
for row in data:
print(row)
# All score=90 rows: Math before Science (preserved from step 1)Verifica rapida
Verifichi la comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: gli ordinamenti basati sui confronti hanno un limite inferiore pari a O(n log n); per superare questo limite servono informazioni non basate sui confronti, come interi con intervallo limitato; il counting sort raggiunge O(n + k) contando le frequenze, il radix sort elabora le cifre con un costo totale O(d × (n + k)) e il bucket sort sfrutta una distribuzione uniforme per ottenere O(n) in media; infine, il Timsort di Python è la scelta predefinita nella pratica: è stabile, ha un costo O(n log n) nel caso peggiore, O(n) nel caso migliore ed è più veloce di qualsiasi alternativa scritta manualmente sui dati reali. Nella prossima lezione approfondiremo la ricerca binaria classica.
Domande Frequenti
La lezione «Ordinamenti non basati sui confronti e sort() di Python» è gratuita?
Sì — il testo completo di «Ordinamenti non basati sui confronti e sort() di Python» è 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 DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Ordinamenti non basati sui confronti e sort() di Python»?
Esplori counting sort e radix sort per gli array di interi e capisca come funziona internamente Timsort di Python nelle chiamate all'ordinamento integrato sort Eserciti DSA 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 DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA 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 4 di 4.
Quanto tempo richiede la lezione «Ordinamenti non basati sui confronti e sort() di Python»?
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 DSA Interview Prep?
Sì. Ogni lezione DSA 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