Quicksort
Dziel i zwyciężaj
Quicksort to bezpłatna lekcja C Academy na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.
Dziel i zwyciężaj
Quicksort to algorytm sortowania oparty na metodzie dziel i zwyciężaj. Wybiera element osiowy, dzieli tablicę tak, aby mniejsze elementy znalazły się po lewej, a większe po prawej, a następnie rekurencyjnie sortuje obie części.
Średnia złożoność czasowa wynosi O(n log n).
Etap podziału
Kluczowym pomysłem jest podział: przestawienie elementów tablicy względem elementu osiowego tak, aby wszystko po jego lewej stronie było mniejsze, a wszystko po prawej większe. Element osiowy zajmuje wtedy swoją ostateczną pozycję w posortowanej tablicy.
Schemat podziału Lomuto
Schemat Lomuto używa ostatniego elementu jako elementu osiowego. Zachowuje indeks i oznaczający granicę mniejszych elementów i wykonuje zamiany podczas przechodzenia przez tablicę.
#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;
}Sortowanie rekurencyjne
Quicksort wywołuje funkcję podziału, a następnie rekurencyjnie sortuje dwa podzbiory znajdujące się po obu stronach elementu osiowego. Przypadkiem bazowym jest podzbiór o rozmiarze 0 lub 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;
}Wybór dobrego elementu osiowego
Nieodpowiedni element osiowy (na przykład zawsze ostatni element w posortowanych danych) prowadzi do złożoności O(n kwadrat). Lepsze wybory zapewniają bardziej równomierne podziały.
- Mediana z trzech
- Losowy element osiowy
Mediana z trzech
Metoda mediany z trzech wybiera jako element osiowy medianę pierwszego, środkowego i ostatniego elementu, unikając najgorszego przypadku dla już posortowanych danych.
#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;
}Analiza najgorszego przypadku
Jeśli każdy podział wydziela tylko jeden element, głębokość rekurencji osiąga n, a koszt wynosi O(n kwadrat). Dzieje się tak przy stałym elemencie osiowym dla danych posortowanych lub posortowanych odwrotnie.
Losowanie sprawia, że najgorszy przypadek jest niezwykle mało prawdopodobny.
Losowy element osiowy
Zamiana losowego elementu na pozycję elementu osiowego przed podziałem chroni przed złośliwie przygotowanymi danymi wejściowymi.
#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;
}Sortowanie w miejscu i brak stabilności
Quicksort sortuje w miejscu, używając średnio tylko O(log n) pamięci stosu. Nie jest jednak stabilny: równe elementy mogą zmienić kolejność względną wskutek zamian wykonywanych podczas podziału.
Optymalizacja wywołań ogonowych
Rekurencyjne sortowanie najpierw mniejszej połowy i iteracyjne przetwarzanie większej ogranicza głębokość stosu do O(log n), zapobiegając przepełnieniu stosu dla dużych tablic.
Sortowanie napisów
Ta sama struktura pozwala sortować dowolny typ, dla którego można zdefiniować porządek. Tutaj quicksort porządkuje tablicę liczb całkowitych, ale zamiana funkcji porównującej umożliwia obsługę innych typów.
#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;
}Szybkie sprawdzenie
Sprawdź swoje rozumienie algorytmu quicksort.
Podsumowanie
Nauczyłeś(-aś) się algorytmu quicksort.
- Podziel tablicę względem elementu osiowego, a następnie rekurencyjnie sortuj obie części
- Średnia złożoność O(n log n), najgorszy przypadek O(n kwadrat)
- Mediana z trzech lub losowe elementy osiowe pozwalają uniknąć najgorszego przypadku
- Sortowanie w miejscu, ale niestabilne
Często zadawane pytania
Czy lekcja „Quicksort” jest bezpłatna?
Tak — pełny tekst „Quicksort” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Quicksort”?
Dziel i zwyciężaj Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć C Academy?
Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Quicksort”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?
Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.