Bubble sort e insertion sort
Codifichi entrambi gli algoritmi di ordinamento quadratici, capisca perché sono O(n²) e riconosca l'unico caso in cui insertion sort supera merge sort
Bubble sort e insertion sort è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 1 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.
Perché studiare gli algoritmi di ordinamento O(n²)?
Bubble sort e insertion sort hanno complessità O(n²) nel caso peggiore, quindi sono impraticabili per input di grandi dimensioni. Tuttavia, ogni colloquio tecnico serio si aspetta che sappia implementarli e analizzarli. Insegnano concetti fondamentali — confronto, scambio, ordinamento stabile e comportamento nel caso migliore — che si applicano ad algoritmi più avanzati. Gli intervistatori li usano per verificare se sa ragionare sugli invarianti dei cicli e sulla notazione asintotica partendo dai primi principi.
# When O(n^2) is acceptable:
# n <= 1000: 10^6 ops, runs in milliseconds
# nearly-sorted data: insertion sort beats merge sort
# constant factor so small (simple ops) that overhead matters
import time
def time_sort(sort_fn, data):
import copy
arr = copy.copy(data)
t = time.perf_counter()
sort_fn(arr)
return time.perf_counter() - t
print('Small n: quadratic sorts are fine')Bubble sort: far risalire il massimo
Bubble sort scorre ripetutamente l'array e scambia gli elementi adiacenti fuori ordine. Dopo ogni scansione completa, l'elemento non ordinato più grande «risale» fino alla sua posizione finale in fondo all'array. Dopo n-1 scansioni, l'intero array è ordinato. Il nome deriva dal modo in cui gli elementi più grandi risalgono, come bolle. È l'algoritmo di ordinamento più semplice da descrivere, ma viene usato raramente nella pratica.
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # n-1 passes
for j in range(n - 1 - i): # inner loop shrinks
if arr[j] > arr[j+1]: # out of order
arr[j], arr[j+1] = arr[j+1], arr[j] # swap
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # [11, 12, 22, 25, 34, 64, 90]Bubble sort con uscita anticipata
Una versione ottimizzata di bubble sort utilizza un flag swapped: se una scansione interna completa non produce alcuno scambio, l'array è già ordinato e si esce anticipatamente. Questo garantisce il caso migliore O(n) per un input già ordinato, l'unico vero vantaggio di bubble sort. Senza questo flag, l'algoritmo esegue sempre confronti O(n²). L'ottimizzazione dell'uscita anticipata è ciò che gli intervistatori verificano quando chiedono come migliorare bubble sort.
def bubble_sort_optimised(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # already sorted!
print(f'Sorted after pass {i+1}')
break
arr1 = [1, 2, 3, 4, 5] # already sorted
bubble_sort_optimised(arr1) # exits after 1 passAnalisi della complessità di bubble sort
Il ciclo esterno di bubble sort viene eseguito n-1 volte. Il ciclo interno viene eseguito n-1-i volte per scansione: (n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 confronti. Ne risulta una complessità O(n²) nel caso medio e nel caso peggiore. Con il flag di uscita anticipata, il caso migliore scende a O(n) per un input ordinato. La complessità spaziale è O(1): solo lo scambio richiede una variabile temporanea. Bubble sort è stabile: gli elementi uguali mantengono il proprio ordine relativo, poiché vengono scambiati solo elementi strettamente maggiori.
def bubble_sort_counted(arr):
n = len(arr)
swaps = comparisons = 0
for i in range(n-1):
for j in range(n-1-i):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swaps += 1
return comparisons, swaps
arr = [5, 4, 3, 2, 1] # worst case: reversed
c, s = bubble_sort_counted(arr)
print(f'Comparisons: {c}, Swaps: {s}') # 10, 10 for n=5Insertion sort: costruire una mano ordinata
Insertion sort simula l'ordinamento di una mano di carte: si prende la carta successiva (l'elemento) e la si inserisce nella posizione corretta tra le carte già ordinate alla sua sinistra. L'invariante è che arr[0:i] sia sempre ordinato. Per ogni nuovo elemento, si spostano a destra gli elementi più grandi per creare spazio. Questo algoritmo in-place e stabile ha complessità O(n²) nel caso peggiore, ma O(n) nel caso migliore per dati quasi ordinati.
def insertion_sort(arr):
for i in range(1, len(arr)): # start from second element
key = arr[i] # element to insert
j = i - 1
# Shift larger elements to the right
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key # insert in correct position
return arr
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr) # [5, 6, 11, 12, 13]Insertion sort passo per passo
Segua insertion sort su [3, 1, 4, 2]: i=1, key=1, spostare 3 a destra → [1, 3, 4, 2]. i=2, key=4, nessuno spostamento → invariato. i=3, key=2, spostare prima 4 e poi 3 a destra → [1, 2, 3, 4]. Ogni elemento viene confrontato con quelli alla sua sinistra finché non si trova la posizione corretta. Il ciclo interno while esegue gli spostamenti tramite assegnazioni (più velocemente degli scambi, poiché ogni spostamento richiede un'assegnazione, mentre uno scambio ne richiede tre).
def insertion_sort_trace(arr):
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] # shift right (1 assignment)
j -= 1
arr[j+1] = key
print(f'After inserting {key}: {arr}')
insertion_sort_trace([3, 1, 4, 2])
# After inserting 1: [1, 3, 4, 2]
# After inserting 4: [1, 3, 4, 2] (no change)
# After inserting 2: [1, 2, 3, 4]Insertion sort su dati quasi ordinati
La caratteristica più importante di insertion sort è la complessità O(n + inversioni). Un'inversione è una coppia (i,j) in cui i < j ma arr[i] > arr[j]. Negli array quasi ordinati con poche inversioni, insertion sort è estremamente veloce, talvolta più veloce di merge sort nella pratica grazie alla sua semplicità e all'accesso alla memoria favorevole alla cache. Il Timsort di Python utilizza insertion sort sui sottoarray piccoli proprio per questo motivo.
# Nearly sorted: only 1 inversion
arr1 = [1, 2, 4, 3, 5] # 4>3 is the only inversion
def count_ops(arr):
arr = arr[:]
ops = 0
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; ops += 1
arr[j+1] = key
return ops
print(count_ops([1,2,4,3,5])) # 1 op (nearly sorted)
print(count_ops([5,4,3,2,1])) # 10 ops (reversed = worst case)Stabilità nell'ordinamento
Un algoritmo di ordinamento è stabile se gli elementi uguali mantengono il proprio ordine relativo originale dopo l'ordinamento. Sia bubble sort sia insertion sort sono stabili: non scambiano mai elementi uguali. La stabilità è importante quando si ordina in sequenza in base a più chiavi: si ordina prima in modo stabile per la chiave secondaria, poi in modo stabile per quella primaria, mantenendo così l'ordine della chiave secondaria tra gli elementi a pari merito. Anche merge sort è stabile; heap sort e quick sort generalmente non lo sono.
# Stable sort preserves order of equal elements
students = [
('Alice', 85),
('Bob', 92),
('Carol', 85),
('Dave', 78),
]
# Sort by score ascending (stable: Alice before Carol for same score)
students.sort(key=lambda x: x[1])
for s in students:
print(s)
# ('Dave',78) ('Alice',85) ('Carol',85) ('Bob',92)
# Alice still comes before Carol => stableInsertion sort con ricerca binaria
Il ciclo interno di insertion sort trova la posizione corretta e sposta gli elementi. È possibile utilizzare la ricerca binaria per trovare la posizione in O(log i) confronti, ma gli spostamenti richiedono comunque O(i) tempo, quindi la complessità complessiva resta O(n²). L'ottimizzazione riduce il numero di confronti (utile per funzioni di confronto costose), ma non il numero totale di operazioni. Questo «binary insertion sort» compare in Timsort per dimensioni ridotte dei blocchi.
import bisect
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
# Find insertion point in O(log i)
pos = bisect.bisect_left(arr, key, 0, i)
# Shift elements to make room: still O(i)
arr[pos+1:i+1] = arr[pos:i]
arr[pos] = key
return arr
print(binary_insertion_sort([5, 2, 4, 6, 1, 3]))
# [1, 2, 3, 4, 5, 6]Bubble sort e insertion sort: quando usare ciascuno
Nei colloqui tecnici, enunci questo confronto con sicurezza: insertion sort è nettamente migliore di bubble sort: entrambi hanno complessità O(n²) nel caso peggiore e usano O(1) di spazio, ma insertion sort effettua meno scritture (O(n+k) per k inversioni rispetto a O(n²) per bubble sort), è più favorevole alla cache ed è la scelta pratica per valori piccoli di n (Timsort lo utilizza). L'unico vero vantaggio di bubble sort è la semplicità didattica. In produzione, utilizzi sempre la funzione di ordinamento integrata nel linguaggio.
# Summary: when to use quadratic sorts
# Use insertion_sort when:
# - n <= 20 (small enough that O(n^2) is fine)
# - data is nearly sorted (few inversions => fast)
# - you need stable sort with O(1) space
# - implementing a hybrid (like Timsort)
# NEVER use bubble_sort in production code
# Python's built-in sort: O(n log n), stable, extremely fast
arr = [5, 2, 8, 1, 9]
print(sorted(arr)) # [1, 2, 5, 8, 9]
arr.sort()
print(arr) # [1, 2, 5, 8, 9]Conteggio delle inversioni come metrica
Il numero di inversioni in un array corrisponde al numero di coppie (i,j) in cui i < j ma arr[i] > arr[j]. Insertion sort esegue esattamente tanti spostamenti quante sono le inversioni: un'osservazione utile. Per contare le inversioni in modo efficiente (O(n log n) ) è necessario un merge sort modificato. Talvolta gli intervistatori chiedono, come approfondimento nelle discussioni sull'ordinamento, «quanto il Suo algoritmo tenga conto delle inversioni?»
# Count inversions: naive O(n^2)
def count_inversions_naive(arr):
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_naive([3, 1, 2])) # 2: (3,1) and (3,2)
print(count_inversions_naive([1, 2, 3])) # 0: already sorted
print(count_inversions_naive([3, 2, 1])) # 3: all pairs invertedVerifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: bubble sort esegue n-1 scansioni, ciascuna delle quali fa risalire il massimo corrente fino alla sua posizione finale, con complessità O(n²) nel caso peggiore ma O(n) nel caso migliore grazie al flag di uscita anticipata; insertion sort sposta gli elementi verso destra per inserire la chiave corrente nella corretta posizione ordinata, con un tempo O(n + inversioni), rendendolo ottimale per i dati quasi ordinati; e entrambi gli algoritmi sono stabili, usano O(1) di spazio e hanno complessità O(n²) nel caso peggiore, ma insertion sort è nettamente preferibile a bubble sort in tutti gli scenari pratici. Prossimamente implementeremo merge sort da zero.
Domande Frequenti
La lezione «Bubble sort e insertion sort» è gratuita?
Sì — il testo completo di «Bubble sort e insertion sort» è 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 «Bubble sort e insertion sort»?
Codifichi entrambi gli algoritmi di ordinamento quadratici, capisca perché sono O(n²) e riconosca l'unico caso in cui insertion sort supera merge 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 1 di 4.
Quanto tempo richiede la lezione «Bubble sort e insertion sort»?
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