Ordinamento veloce

9.1 Definizione di Quick Sort

Quick Sort — è un algoritmo di ordinamento efficace che utilizza l'approccio "divide et impera". Funziona scegliendo un elemento pivot, dividendo l'array in due sottoarray — elementi minori del pivot e elementi maggiori del pivot, e poi applicando ricorsivamente lo stesso processo a ciascun sottoarray.

L'algoritmo di Quick Sort è nato come un tentativo di risolvere il problema di "come trasferire rapidamente a sinistra gli elementi piccoli e a destra quelli grandi". Supponiamo che abbiamo l'elemento più piccolo all'estremità destra, è possibile trasferirlo rapidamente, se non alla sua posizione finale, almeno vicino ad essa? Questo ridurrebbe notevolmente il numero di confronti inutili.

Il principio di funzionamento:

1. Scelta del pivot:

Si sceglie un elemento dall'array come pivot. Questo può essere il primo elemento, l'ultimo elemento, l'elemento medio o un elemento casuale. A volte è la media aritmetica di tre elementi casuali.

2. Divisione (partitioning):

Si spostano tutti gli elementi minori del pivot nella parte sinistra dell'array e tutti gli elementi maggiori del pivot nella parte destra. Di conseguenza, il pivot si trova nella sua posizione finale nell'array ordinato.

3. Applicazione ricorsiva:

Si applica ricorsivamente il processo ai sottoarray di sinistra e di destra, escludendo il pivot.

Processo passo-passo

1. Si sceglie il pivot.
2. Si spostano gli elementi minori del pivot a sinistra e gli elementi maggiori a destra.
3. Si applica ricorsivamente il processo ai sottoarray.

Complessità temporale e spaziale di Quick Sort

Complessità temporale:

• Nella peggiore delle ipotesi: O(n^2) — succede quando ogni volta si sceglie il peggior pivot possibile (ad esempio, quando l'array è già ordinato).
• In media: O(n log n) — per dati distribuiti casualmente.
• Nella migliore delle ipotesi: O(n log n) — quando l'array si divide ogni volta in parti uguali.

Complessità spaziale:

O(log n) — è necessario per memorizzare lo stack di chiamate ricorsive, se si utilizza la ricorsione in coda e i pivot vengono scelti in modo appropriato.

9.2 Implementazione dell'algoritmo Quick Sort

Implementazione in Python:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr  # Caso base: un array con 0 o 1 elemento è già ordinato
    
    pivot = arr[len(arr) // 2]  # Si sceglie il pivot
    left = [x for x in arr if x < pivot]  # Elementi minori del pivot
    middle = [x for x in arr if x == pivot]  # Elementi uguali al pivot
    right = [x for x in arr if x > pivot]  # Elementi maggiori del pivot
    
    return quick_sort(left) + middle + quick_sort(right)

# Esempio di utilizzo:
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("Array ordinato:", sorted_arr)
# Output: Array ordinato: [1, 1, 2, 3, 6, 8, 10]

Esempio di funzionamento dell'algoritmo

Prendiamo un array di esempio: [3, 6, 8, 10, 1, 2, 1]

Primo passaggio:

• Pivot: 8
• Elementi di sinistra: [3, 6, 1, 2, 1]
• Elementi medi: [8]
• Elementi di destra: [10]

Ordinamento ricorsivo della parte sinistra [3, 6, 1, 2, 1]:

• Pivot: 1
• Elementi di sinistra: []
• Elementi medi: [1, 1]
• Elementi di destra: [3, 6, 2]

Ordinamento ricorsivo della parte destra [3, 6, 2]:

• Pivot: 6
• Elementi di sinistra: [3, 2]
• Elementi medi: [6]
• Elementi di destra: []

Ordinamento ricorsivo della parte sinistra [3, 2]:

• Pivot: 2
• Elementi di sinistra: []
• Elementi medi: [2]
• Elementi di destra: [3]

Risultato della fusione: [1, 1, 2, 3, 6] per la parte sinistra, [10] per la parte destra, e [8] per la parte centrale.

Array finale ordinato: [1, 1, 2, 3, 6, 8, 10]