Edizione didattica italiana
Quicksort in C: esempio commentato
Ordina un array con partizionamento e ricorsione, verificando limiti e casi peggiori.
Quicksort sceglie un pivot, separa i valori minori dai maggiori e ordina ricorsivamente le parti. Nel partizionamento di Lomuto di questo esempio, l’ultimo elemento è il pivot e un indice delimita la regione già elaborata.
La ricorsione termina quando l’intervallo contiene meno di due elementi. Il tempo medio è O(N log N), ma partizioni molto sbilanciate possono portare a O(N²). Conta anche lo stack delle chiamate, pur senza un secondo array.
Prova duplicati, array ordinati e ordine inverso. Controlla i limiti di ogni chiamata. Questa versione non garantisce di mantenere l’ordine iniziale degli elementi uguali.
Codice sorgente
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
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);
}
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 main() {
int arr[] = {10, 80, 30, 90, 40, 50, 70};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array:\n");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
return 0;
}Risultato atteso
Sorted array: 10 30 40 50 70 80 90
Domande frequenti
Perché il codice e alcuni risultati restano in inglese?
Parole chiave C, identificatori, commenti del programma e output attesi restano quelli originali per preservare codice eseguibile e test coerenti. Spiegazioni e istruzioni sono tradotte.