Algoritmo di ordinamento Quick sort in C

Il quick sort è un algoritmo di ordinamento ricorsivo in loco (o in place), in particolare utilizza il metodo divide et impera per ordinare i dati di un vettore. La procedura ricorsiva avviene nel seguente modo: viene scelto un elemento dall’array, detto pivot, si posizionano gli elementi minori a sinistra del pivot, mentre gli elementi più grandi a destra.

In questo modo ci saranno due sottogruppi divisi dal pivot, il quale si troverà nella posizione finale. Il processo verrà ripetuto in ciascun sottogruppo fino a che il vettore non sarà completamente ordinato.

Fonte gif: Wikipedia

Il quick sort è un algoritmo di ordinamento comparativo, cioè che ordina gli elementi di una lista svolgendo una singola operazione di comparazione (minore o maggiore).

Per quanto riguarda la performance, analisi matematiche mostrano che:

• nel caso peggiore presenta una complessità computazionale O(n²), questo avviene quando la dimensione di un sottoinsieme è n-1, cioè un sottogruppo contiene un unico elemento, mentre tutti gli altri sono nell’altro sottogruppo, e questo processo continua fino a che la lista non è completamente ordinata

• nel caso medio la complessità dell’algoritmo è pari a O(nlogn)

• nel caso migliore, cioè quando i due sottoinsiemi sono già ordinati e possiedono la stessa dimensione (n/2), la complessità è O(nlog₂n)

Implementazione quick sort in C

Una volta riempito o definito un array contenente dei numeri, passiamo all’ordinamento di tali elementi con l’algoritmo di ordinamento quick sort, chiamando la funzione quicksort che richiede come input: l’array contenente i numeri, il primo e l’ultimo indice del vettore. All’interno della funzione quicksort controlliamo che il parametro low sia effettivamente minore del parametro high e assegnamo alla variabile pivot l’indice del numero più a sinistra.

A questo punto utilizzando vari cicli while controlliamo se il valore contenuto nell’array nella posizione i sia minore o uguale al valore nella posizione del pivot, se si incrementiamo la variabile i. Analogamente, controlliamo se il valore nella posizione j è maggiore del valore nella posizione pivot, se si decrementano la variabile j. 

Se questi due cicli while non sono più verificati e se la variabile i è ancora minore di j, invertiamo i due valori che si trovano in tali posizioni. Quando la variabile i diventa maggiore o uguale alla variabile j, termina il ciclo while esterno e invertiamo tra loro i valori che si trovano nella posizione j e pivot. Quindi ripetiamo tutto questo procedimento chiamando in maniera ricorsiva la funzione quicksort in modo da ordinare i sottogruppi generati.

#include <stdio.h>
#define N 10

void quicksort(int l[], int low, int high){
    int i, j, pivot, temp;
   
    if(low < high){
        pivot = low;
        i = low;
        j = high;
        
        while(i < j){
            while(l[i] <= l[pivot] && i < high)
                i++;
            while(l[j] > l[pivot])
                j--;
            if(i < j){
                temp = l[i];
                l[i] = l[j];
                l[j] = temp;
            }
        }
        
        temp = l[pivot];
        l[pivot] = l[j];
        l[j] = temp;
        quicksort(l, low, j - 1);
        quicksort(l, j + 1, high);
    }
}

int main(){
    int lista[N] = {6, 2, 4, 7, 5, 1, 9, 3, 15, 22};

    quicksort(lista, 0, N - 1);

    printf("Array ordinato: ");

    for(int i = 0; i < N; i++){
        printf("%d ", lista[i]);
    }

    return 0;
}
// Output: Array ordinato: 1 2 3 4 5 6 7 9 15 22