Mergesort
Sortowanie stabilne
Mergesort to bezpłatna lekcja C Academy na CoddyKit. To lekcja 3 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.
Sortowanie stabilne
Mergesort to algorytm sortowania oparty na zasadzie dziel i zwyciężaj: dzieli tablicę na połowy, sortuje każdą z nich, a następnie scala je z powrotem. W każdym przypadku ma złożoność O(n log n) i jest stabilny.
Etap dzielenia
Rekurencyjnie dziel tablicę w punkcie środkowym, aż każda część będzie zawierać jeden element. Pojedynczy element jest trywialnie posortowany, więc stanowi przypadek bazowy.
Etap scalania
Główna operacja polega na scaleniu dwóch już posortowanych ciągów w jeden. Przechodź po obu za pomocą wskaźników indeksowych, za każdym razem kopiując następny mniejszy element z początku ciągu.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi)
tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
for (int t = lo; t <= hi; t++) a[t] = tmp[t];
}
int main(void) {
int a[] = {1, 4, 6, 2, 3, 5}; /* two sorted runs */
int tmp[6];
merge(a, 0, 2, 5, tmp);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Dlaczego algorytm jest stabilny
Scalanie używa a[i] <= a[j], więc gdy dwa elementy są równe, najpierw wybierany jest element z lewego ciągu. Ponieważ lewy ciąg zawierał wcześniejsze elementy, ich kolejność początkowa zostaje zachowana.
Rekurencyjny sterownik
Mergesort wywołuje się rekurencyjnie dla każdej połowy, a następnie scala wyniki. Przekazujemy wspólny bufor pomocniczy, aby uniknąć alokowania pamięci przy każdym wywołaniu.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo, j=mid+1, k=lo;
while (i<=mid && j<=hi) tmp[k++] = (a[i]<=a[j]) ? a[i++] : a[j++];
while (i<=mid) tmp[k++]=a[i++];
while (j<=hi) tmp[k++]=a[j++];
for (int t=lo;t<=hi;t++) a[t]=tmp[t];
}
void msort(int a[], int lo, int hi, int tmp[]) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
msort(a, lo, mid, tmp);
msort(a, mid + 1, hi, tmp);
merge(a, lo, mid, hi, tmp);
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8, 4};
int tmp[7];
msort(a, 0, 6, tmp);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Zużycie pamięci
W przeciwieństwie do quicksort algorytm mergesort potrzebuje O(n) dodatkowej pamięci na bufor scalania. Jest to jego główna wada w przypadku bardzo dużych tablic i ograniczonej pamięci.
Gwarantowane O(n log n)
Rekurencja zawsze dzieli tablicę na połowy, co daje log n poziomów, a na każdym poziomie scalanych jest n elementów. Dlatego mergesort ma złożoność O(n log n) w najlepszym, średnim i najgorszym przypadku, w przeciwieństwie do quicksort.
Zliczanie poziomów scalania
Liczba poziomów rekurencji wynosi ceil(log2 n). Obliczmy ją dla kilku rozmiarów.
#include <stdio.h>
int levels(int n) {
int L = 0;
while (n > 1) { n = (n + 1) / 2; L++; }
return L;
}
int main(void) {
int sizes[] = {1, 2, 8, 100, 1000};
for (int i = 0; i < 5; i++)
printf("n=%d levels=%d\n", sizes[i], levels(sizes[i]));
return 0;
}Mergesort oddolny
Wariant iteracyjny scala ciągi o rozmiarze 1, następnie 2, potem 4, podwajając rozmiar przy każdym przebiegu. Całkowicie eliminuje rekurencję i dobrze sprawdza się w przypadku list wiązanych.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo,j=mid+1,k=lo;
while(i<=mid&&j<=hi) tmp[k++]=(a[i]<=a[j])?a[i++]:a[j++];
while(i<=mid) tmp[k++]=a[i++];
while(j<=hi) tmp[k++]=a[j++];
for(int t=lo;t<=hi;t++) a[t]=tmp[t];
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8}, n = 6, tmp[6];
for (int width = 1; width < n; width *= 2)
for (int lo = 0; lo < n - width; lo += 2 * width) {
int mid = lo + width - 1;
int hi = (lo + 2*width - 1 < n-1) ? lo + 2*width - 1 : n-1;
merge(a, lo, mid, hi, tmp);
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Kiedy wybrać mergesort
Proszę wybrać mergesort, gdy potrzebują Państwo:
- Gwarantowanego O(n log n), bez pesymistycznych przypadków
- Stabilności
- Sortowania list wiązanych (bez konieczności dostępu swobodnego)
- Sortowania zewnętrznego danych, które nie mieszczą się w pamięci RAM
Mergesort a quicksort
Quicksort jest zwykle szybszy w praktyce i sortuje w miejscu, ale nie jest stabilny i może mieć niekorzystną złożoność w najgorszym przypadku. Mergesort jest stabilny i ma gwarantowane ograniczenie złożoności, ale używa dodatkowej pamięci. Proszę dokonać wyboru na podstawie swoich ograniczeń.
Szybkie sprawdzenie
Sprawdź swoją wiedzę na temat mergesort.
Podsumowanie
Ukończyli Państwo naukę algorytmu mergesort.
- Podziel tablicę na połowy, posortuj każdą z nich, a następnie scal
- Scalanie zachowuje kolejność „najpierw z lewej” dla równych kluczy, zapewniając stabilność
- Gwarantowane O(n log n) we wszystkich przypadkach
- Wymaga O(n) dodatkowej pamięci; świetnie nadaje się do list wiązanych i sortowania zewnętrznego
Często zadawane pytania
Czy lekcja „Mergesort” jest bezpłatna?
Tak — pełny tekst „Mergesort” 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 „Mergesort”?
Sortowanie stabilne Ć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 3 z 4.
Ile czasu zajmuje lekcja „Mergesort”?
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.