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 del quick sort, 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] = {4, 6, 12, 8, 3, 2, 5, 20, 1, 9};
	
    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 8 9 12 20