Cosa significa ordinare?
Ordinare un array significa disporre i suoi elementi secondo un criterio — di solito crescente o decrescente. È uno dei problemi fondamentali dell'informatica: quasi ogni applicazione reale (motori di ricerca, banche dati, giochi) ordina dati in continuazione.
In questo modulo studieremo i tre algoritmi elementari di ordinamento: tutti hanno complessità O(n²) nel caso peggiore, ma differiscono nel numero di confronti, scambi e nel comportamento con array già parzialmente ordinati.
for annidati, funzione swap().
Bubble Sort
Il Bubble Sort confronta ogni coppia di elementi adiacenti e li scambia se sono nell'ordine sbagliato. Ogni passata completa porta l'elemento più grande in fondo all'array — come una bolla che sale in superficie.
Idea visiva
Con array [5, 3, 8, 1, 2], la prima passata confronta 5↔3 (scambia), 5↔8 (no), 8↔1 (scambia), 8↔2 (scambia). Dopo la prima passata l'8 è in posizione finale. Si ripete finché tutto è ordinato.
swapped permette di uscire prima se l'array è già ordinato.
Codice C++ commentato
#include <iostream> #include <algorithm> // per std::swap using namespace std; // Ordina l'array in senso crescente con Bubble Sort void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { bool swapped = false; // ottimizzazione: uscita anticipata for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { swap(arr[j], arr[j + 1]); swapped = true; } } if (!swapped) break; // nessuno scambio → già ordinato } } int main() { int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, n); cout << "Array ordinato: "; for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; return 0; }
Visualizzatore
Selection Sort
Il Selection Sort divide l'array in due parti: quella già ordinata (a sinistra) e quella non ancora ordinata (a destra). Ad ogni iterazione trova il minimo nella parte non ordinata e lo porta in testa, espandendo la parte ordinata di un elemento.
Idea visiva
Con [5, 3, 8, 1, 2]: scansiona tutta la lista, trova il minimo (1), lo porta in posizione 0 → [1, 3, 8, 5, 2]. Poi scansiona dal secondo elemento, trova il minimo (2), porta in posizione 1 → [1, 2, 8, 5, 3]. E così via.
Codice C++ commentato
#include <iostream> #include <algorithm> using namespace std; // Ordina trovando il minimo e portandolo in testa a ogni passata void selectionSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int minIdx = i; // assume che il minimo sia il primo della parte non ordinata for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIdx]) minIdx = j; // aggiorna l'indice del minimo } if (minIdx != i) swap(arr[minIdx], arr[i]); // porta il minimo in posizione i } } int main() { int arr[] = {64, 25, 12, 22, 11}; int n = sizeof(arr) / sizeof(arr[0]); selectionSort(arr, n); cout << "Array ordinato: "; for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; return 0; }
Visualizzatore
Insertion Sort
L'Insertion Sort costruisce l'array ordinato un elemento alla volta, inserendo ogni nuovo elemento nella posizione corretta tra quelli già ordinati. È il metodo che usiamo istintivamente quando ordiniamo le carte da gioco in mano.
Idea visiva
Prendi il secondo elemento, confrontalo con il primo e inseriscilo al posto giusto. Poi prendi il terzo e inseriscilo nella posizione corretta tra i primi due. Ogni elemento "scivola" verso sinistra finché trova il suo posto.
Codice C++ commentato
#include <iostream> using namespace std; // Inserisce ogni elemento nella posizione corretta tra quelli già ordinati void insertionSort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; // elemento da inserire int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; // scorrimento verso destra j--; } arr[j + 1] = key; // inserisce nella posizione libera } } int main() { int arr[] = {12, 11, 13, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); insertionSort(arr, n); cout << "Array ordinato: "; for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl; return 0; }
Visualizzatore
Confronto tra algoritmi
| Algoritmo | Caso migliore | Caso medio | Caso peggiore | Scambi | Stabile? |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(n²) | ✅ Sì |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(n) | ❌ No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(n²)* | ✅ Sì |
Esempio: immagina di ordinare un elenco di studenti per voto medio. Se gli studenti con lo stesso voto erano elencati originariamente in ordine alfabetico, un algoritmo stabile manterrà questo sotto-ordine alfabetico anche dopo aver riordinato per voto.
La stabilità è osservabile solo con record che hanno una chiave distinta dal resto del dato (come nell'esempio sopra). Con un array di numeri semplici — il caso più comune negli esercizi — due valori uguali sono indistinguibili tra loro, quindi il concetto di stabilità non si può osservare.