Quick Sort

1. Spiegazione dell’algoritmo Quick Sort:

Quick Sort è uno degli algoritmi di ordinamento più potenti e usati in informatica, famoso per la sua efficienza e semplicità. Si basa sul principio del "divide et impera", dividendo l’array in sottosequenze più piccole da ordinare. L'idea principale è scegliere un pivot (di solito l’ultimo elemento), e poi riordinare gli altri elementi in modo che quelli minori del pivot vadano a sinistra e quelli maggiori a destra. Dopo questa suddivisione, Quick Sort viene applicato ricorsivamente a ciascuna delle due parti.

Questo metodo è particolarmente efficace perché riduce drasticamente il numero di confronti richiesti rispetto ad altri algoritmi come il Bubble Sort o Selection Sort. Inoltre, è un algoritmo in-place, cioè non richiede memoria aggiuntiva significativa.

Grazie a queste qualità, Quick Sort è spesso la scelta ideale per l’ordinamento di grandi volumi di dati.

2. Codice in linguaggio C:

Ecco una classica implementazione in C di Quick Sort. Questo esempio mostra sia la funzione di ordinamento ricorsiva che la funzione di partizionamento:


void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

La funzione partition è fondamentale: organizza i valori attorno al pivot e restituisce l’indice corretto del pivot. Questo indice è poi usato per applicare il quickSort alle due metà dell’array.

3. Esempio pratico:

Supponiamo di voler ordinare questo array: [8, 4, 7, 3, 10, 2, 6]

- Primo pivot: 6
- Dopo partizionamento: [4, 3, 2] | 6 | [8, 7, 10]
- Ricorsione su sinistra: pivot = 2 → [ ] | 2 | [4, 3]
- Su [4, 3]: pivot = 3 → [ ] | 3 | [4]
- Ricorsione su destra: [8, 7, 10] → pivot = 10 → [8, 7] | 10 | [] → [7, 8]

Risultato finale: [2, 3, 4, 6, 7, 8, 10]

Questo esempio dimostra come l'algoritmo riduca progressivamente il problema in sotto-array ordinati, ottenendo il risultato in modo rapido.

4. Analisi dell’algoritmo:

- Complessità media: O(n log n), ottima per la maggior parte dei dati reali.
- Complessità peggiore: O(n²), solo in casi sfortunati (es. array già ordinato senza pivot casuale).
- Complessità spaziale: O(log n) grazie all’uso di ricorsione.
- Stabilità: Non è stabile, cioè elementi uguali possono cambiare posizione.
- Uso pratico: Quick Sort è usato in molte librerie standard grazie alla sua velocità, come in C++, Java e Python.

In sintesi, è uno degli algoritmi più importanti da conoscere e comprendere nella programmazione e nell’informatica.

Algoritmo Quick Sort