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(n2), 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(nlog2n)
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
Indice pagine linguaggio C: