Quick Sort in C

Implementiamo il Quick Sort in C, un algoritmo di ordinamento che così come il merge sort segue il metodo divide et impera. Il Quick Sort è un efficiente algoritmo di ordinamento che utilizza la tecnica “divide et impera”.

Il Quick Sort, inventato da Sir Tony Hoare nel 1960, è noto per la sua efficienza ed è ampiamente utilizzato nella pratica. L’idea principale è suddividere l’array in base a un elemento chiamato “pivot”, in modo che gli elementi minori del pivot siano a sinistra e quelli maggiori a destra. Quindi, si ricorsivamente ordina le due parti.

Il Quick Sort si basa sulla strategia “Divide et Impera”, che consiste nelle seguenti fasi:

1. Divide: L’array viene suddiviso in sotto-array più piccoli, generalmente utilizzando un elemento chiamato “pivot”.
2. Impera: I sotto-array vengono ordinati in maniera ricorsiva. Questo significa che l’algoritmo si richiama su se stesso per ordinare i sotto-array.
3. Combina: Una volta ordinati i sotto-array, i risultati vengono combinati per ottenere l’array ordinato finale.

Il Quick Sort è rinomato per le sue prestazioni superiori rispetto ad altri algoritmi di ordinamento basati su confronti. Ciò è dovuto alla sua strategia di suddivisione dell’array non basata sugli indici, ma sul contenuto effettivo dell’array stesso.

In altre parole, l’algoritmo non divide l’array in parti uguali in base agli indici, bensì sceglie un elemento chiamato “pivot” e divide l’array in modo che tutti gli elementi più piccoli del pivot siano posizionati a sinistra e tutti quelli più grandi a destra. Questo processo di suddivisione e selezione del pivot viene eseguito in modo ricorsivo fino a quando l’intero array è ordinato.

Funzionamento del Quick Sort in C

Prima di affrontare l’implementazione dell’algoritmo Quick Sort in C, è fondamentale comprendere l’idea di base che guida il suo funzionamento:

1. Selezione del Pivot: Si sceglie un elemento centrale dal vettore, noto come “pivot”, e lo si memorizza in una variabile.
2. Suddivisione dell’Array: Gli elementi maggiori o uguali al pivot vengono posizionati a sinistra, mentre quelli minori vengono posizionati a destra. Questo processo di suddivisione crea due sotto-array separati.
3. Ordinamento Ricorsivo: Si applica ricorsivamente l’algoritmo Quick Sort ai sotto-array sinistro e destro.

La procedura che si occupa della suddivisione dell’array in due parti, posizionando correttamente gli elementi rispetto al pivot, è comunemente chiamata “partition”.

Chiaramente la scelta del pivot non è legata necessariamente al primo elemento, potrebbe anche essere l’ultimo o il mediano oppure essere un elemento random.

Esempio del quick sort in C

Scegliamo come Pivot il primo elemento, dunque Pivot = 4.

Dobbiamo avere a sinistra gli elementi minori di Pivot, a destra gli elementi maggiori.

Facciamo partire l’indice i da sinistra ovvero dal primo elemento e l’indice j da destra ovvero dall’ultimo elemento.

Per comodità ci riferiremo a primo e ultimo per vedere in dettaglio tutti i passaggi.

Dapprima avremo:

Pivot = 4 (si trova in posizione i)

primo = 4

ultimo = 8

Ci chiediamo Pivot è minore di ultimo? Cioè 4 è minore di 8?

Si, allora procedo e sposto l’indice j (perchè a destra devo avere gli elementi maggiori, quindi non devo scambiarli!)

Quindi avremo:

Pivot=4   (si trova in posizione i)

primo=4

ultimo=3

Ci poniamo allora la domanda  Pivot è minore di ultimo?

No, allora sposto Pivot in posizione j, cioè in ultimo.

Quindi avrò il terzo passaggio:

Pivot=4 (si trova in posizione j)

primo=3

ultimo=4

Adesso Pivot è in posizione indicata dall’indice j, dunque sposto l’indice i.

Mi chiedo Pivot è maggiore di primo?

Si, allora sposto l’indice i. E continuo spostando l’indice i fino all’elemento 5.

Quindi avrò:

Pivot = 4 (si trova in posizione j)

primo = 5

ultimo = 4

Mi chiedo ancora Pivot è maggiore di primo?

No, allora sostituisco Pivot nella posizione di primo.

Quindi avrò:

Pivot = 4 (si trova in posizione i)

primo = 4

ultimo = 5

Come in figura sotto:

Adesso Pivot si trova in posizione i, facciamo muovere j.

Cioè Pivot è minore di ultimo? Si allora sposto l’indice j e avrò:

Pivot=4 (si trova in posizione i)

primo=4

ultimo=0

Pivot è minore di ultimo?

No allora li scambiamo. Avremo:

Pivot = 4 (si trova in posizione j)

primo = 0

ultimo = 4

Quindi ci chiediamo Pivot è maggiore di primo?

Si, allora spostiamo l’indice i e avremo la situazione:

Pivot = 4 (si trova in posizione i)

primo = 4

ultimo = 2

Adesso chiediamo: Pivot è minore di primo?

Si allora l’indice i coinciderà con j.

Adesso che abbiamo a destra gli elementi maggiori del Pivot e a sinistra gli elementi minori dobbiamo procedere con l’ordinamento dei due sotto-array procedendo allo stesso modo.

Sviluppo dell’algoritmo Quick Sort in C

Ecco dunque il codice completo:

#include <stdio.h>

#define MAX 100

// Funzione per l'inserimento degli elementi nell'array
int inserisciElementi(int array[]) {
    int dimensione, i;
    printf("Inserisci il numero di elementi: ");
    scanf("%d", &dimensione);

    for (i = 0; i < dimensione; i++) {
        printf("Elemento %d: ", i + 1);
        scanf("%d", &array[i]);
    }
    return dimensione;
}

// Funzione per stampare gli elementi dell'array
void stampaArray(int array[], int dimensione) {
    printf("Array: ");
    for (int i = 0; i < dimensione; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

// Funzione per eseguire il partitioning e trovare il pivot
int partition(int array[], int basso, int alto) {
    int pivot = array[alto];
    int i = (basso - 1);

    for (int j = basso; j <= alto - 1; j++) {
        if (array[j] < pivot) {
            i++;
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    int temp = array[i + 1];
    array[i + 1] = array[alto];
    array[alto] = temp;
    return (i + 1);
}

// Funzione principale per eseguire l'ordinamento quick sort
void quickSort(int array[], int basso, int alto) {
    if (basso < alto) {
        int pivot = partition(array, basso, alto);

        quickSort(array, basso, pivot - 1);
        quickSort(array, pivot + 1, alto);
    }
}

int main() {
    int array[MAX];
    int dimensione = inserisciElementi(array);

    printf("Array non ordinato: ");
    stampaArray(array, dimensione);

    quickSort(array, 0, dimensione - 1);

    printf("Array ordinato: ");
    stampaArray(array, dimensione);

    return 0;
}

Questo codice implementa il Quick Sort in C. La funzione partition viene utilizzata per trovare il pivot e dividere l’array in due parti. Quindi, la funzione quickSort ordina ricorsivamente le due parti. Infine, nella funzione main, gli elementi dell’array vengono inseriti, l’array viene ordinato e quindi stampato.

Prestazioni del Quick Sort

Le prestazioni del Quick Sort sono notevoli per vari motivi:

1. Efficienza: Il Quick Sort è noto per la sua efficienza. Nel caso medio, ha un tempo di esecuzione di O(n log n), dove “n” rappresenta la dimensione dell’array da ordinare. Questo lo rende uno degli algoritmi di ordinamento più veloci disponibili.
2. Adattabilità: Il Quick Sort è in grado di adattarsi dinamicamente alla struttura dei dati. Ciò significa che la sua complessità temporale non dipende solo dalla dimensione dell’input, ma anche dalla sua disposizione. In particolare, funziona molto bene su array con dati casuali o parzialmente ordinati.
3. Metodo di Suddivisione Pivot: La scelta del pivot nel Quick Sort contribuisce notevolmente alle sue prestazioni. Se il pivot è scelto in modo efficace, l’array viene diviso in parti di dimensioni approssimativamente uguali, riducendo il numero di confronti e scambi necessari per ordinare l’array.
4. Implementazione efficiente: Il Quick Sort è relativamente semplice da implementare e richiede meno memoria rispetto ad altri algoritmi di ordinamento come il Merge Sort.
5. Utilizzo della Cache: Il Quick Sort tende ad avere un buon utilizzo della cache del computer a causa della sua struttura ricorsiva e dell’accesso lineare ai dati, contribuendo ulteriormente alle sue prestazioni.

Ma dobbiamo notare che nel caso peggiore, quando il pivot è scelto in modo subottimale (ad esempio, se l’array è già ordinato o inversamente ordinato), il Quick Sort può degenerare in un tempo di esecuzione quadrato (O(n^2)). Questo scenario può essere mitigato utilizzando tecniche come la scelta casuale del pivot o la mediana delle tre tecniche di pivot.

Conclusioni

Il Quick Sort è un algoritmo di ordinamento efficiente e ampiamente utilizzato. La sua implementazione in C è relativamente semplice e offre prestazioni eccellenti per una vasta gamma di dimensioni dell’array. Spero che questo articolo vi abbia aiutato a capire meglio il funzionamento del Quick Sort e come implementarlo in C.

Alcuni link utili

Corso linguaggio C

Indice tutorial linguaggio C

Array o vettori

Merge sort in linguaggio C

Insertion Sort in lingaggio C