Quicksort
Divide et impera
Quicksort è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento C Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C Academy include 4 lezioni in totale.
Divide et impera
Quicksort è un algoritmo di ordinamento divide et impera. Sceglie un pivot, partiziona l'array in modo che gli elementi più piccoli vadano a sinistra e quelli più grandi a destra, quindi ordina ricorsivamente le due parti.
Il tempo medio è O(n log n).
Il passaggio di partizionamento
L'idea fondamentale è il partizionamento: riorganizzare l'array intorno a un pivot, in modo che tutto ciò che si trova a sinistra del pivot sia più piccolo e tutto ciò che si trova a destra sia più grande. Il pivot si trova quindi nella posizione finale corretta.
Schema di partizionamento di Lomuto
Lo schema di Lomuto usa l'ultimo elemento come pivot. Mantiene un indice i che indica il confine degli elementi più piccoli ed esegue scambi durante la scansione.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) {
i++;
int t = a[i]; a[i] = a[j]; a[j] = t;
}
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
int p = partition(a, 0, 4);
printf("pivot index = %d\n", p);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}L'ordinamento ricorsivo
Quicksort chiama il partizionamento, poi ricorre sui due sottoarray ai lati del pivot. Il caso base è un sottoarray di dimensione 0 o 1.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t;
return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) {
int p = partition(a, lo, hi);
quicksort(a, lo, p - 1);
quicksort(a, p + 1, hi);
}
}
int main(void) {
int a[] = {9, 3, 7, 1, 8, 2, 5};
quicksort(a, 0, 6);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Scegliere un buon pivot
Un pivot poco adatto (ad esempio sempre l'ultimo elemento con un input ordinato) causa un comportamento O(n al quadrato). Scelte migliori distribuiscono le partizioni in modo più uniforme.
- Mediana di tre
- Pivot casuale
Mediana di tre
La mediana di tre sceglie come pivot la mediana del primo, dell'elemento centrale e dell'ultimo elemento, evitando il comportamento del caso peggiore con dati già ordinati.
#include <stdio.h>
int median_of_three(int a[], int lo, int hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < a[lo]) { int t=a[mid];a[mid]=a[lo];a[lo]=t; }
if (a[hi] < a[lo]) { int t=a[hi];a[hi]=a[lo];a[lo]=t; }
if (a[hi] < a[mid]) { int t=a[hi];a[hi]=a[mid];a[mid]=t; }
return mid;
}
int main(void) {
int a[] = {7, 1, 5, 3, 9};
int m = median_of_three(a, 0, 4);
printf("median value = %d\n", a[m]);
return 0;
}Analisi del caso peggiore
Se ogni partizione separa un solo elemento, la profondità della ricorsione diventa n e il costo è O(n al quadrato). Questo accade con un pivot fisso su input ordinati o ordinati al contrario.
La casualizzazione rende estremamente improbabile il caso peggiore.
Pivot casuale
Scambiare un elemento casuale nella posizione del pivot prima del partizionamento protegge dagli input creati appositamente per causare prestazioni scadenti.
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int a[] = {1, 2, 3, 4, 5};
int lo = 0, hi = 4;
srand(42);
int r = lo + rand() % (hi - lo + 1);
int t = a[r]; a[r] = a[hi]; a[hi] = t; /* move random to pivot slot */
printf("chosen pivot = %d\n", a[hi]);
return 0;
}In loco e non stabile
Quicksort ordina in loco usando in media solo O(log n) spazio nello stack. Tuttavia, non è stabile: gli elementi uguali possono cambiare ordine a causa degli scambi eseguiti durante il partizionamento.
Ottimizzazione delle chiamate di coda
Richiamare ricorsivamente prima la metà più piccola e usare un ciclo per la metà più grande limita la profondità dello stack a O(log n), evitando l'overflow dello stack con array di grandi dimensioni.
Ordinamento di stringhe
La stessa struttura consente di ordinare qualsiasi tipo confrontabile. Qui quicksort ordina un array di interi, ma modificando il confronto è possibile gestire anche altri tipi.
#include <stdio.h>
int partition(int a[], int lo, int hi) {
int pivot = a[hi], i = lo - 1;
for (int j = lo; j < hi; j++)
if (a[j] < pivot) { i++; int t=a[i];a[i]=a[j];a[j]=t; }
int t = a[i+1]; a[i+1] = a[hi]; a[hi] = t; return i + 1;
}
void quicksort(int a[], int lo, int hi) {
if (lo < hi) { int p = partition(a, lo, hi); quicksort(a, lo, p-1); quicksort(a, p+1, hi); }
}
int main(void) {
int a[] = {42, -7, 0, 100, 13, 13};
quicksort(a, 0, 5);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Verifica rapida
Verifichi la Sua comprensione di quicksort.
Riepilogo
Ha imparato quicksort.
- Partizionare intorno a un pivot, poi ricorrere su ciascun lato
- O(n log n) in media, O(n al quadrato) nel caso peggiore
- La mediana di tre o i pivot casuali evitano il caso peggiore
- In loco, ma non stabile
Impara C con un tutor IA — gratis
Scrivi ed esegui vero codice nel tuo browser, ricevi aiuto istantaneo da un tutor IA disponibile 24/7, e riprendi da dove hai lasciato sul web o nell'app.
- Corsi
- 39
- Lezioni
- 144
Domande Frequenti
La lezione «Quicksort» è gratuita?
Sì — il testo completo di «Quicksort» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso C Academy, passa a CoddyKit PRO. Il corso C Academy include 4 lezioni in totale.
Cosa imparerò in «Quicksort»?
Divide et impera Eserciti C Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare C Academy?
Non è richiesta alcuna esperienza precedente. C Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Quicksort»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione C Academy?
Sì. Ogni lezione C Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.