Mergesort
Pengurutan stabil.
Mergesort adalah pelajaran C Academy gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar C Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus C Academy mencakup 4 pelajaran total.
Pengurutan Stabil
Mergesort adalah algoritme pengurutan dengan strategi bagi-dan-takluk yang membagi larik menjadi dua, mengurutkan setiap bagian, lalu menggabungkan keduanya kembali. Kompleksitasnya O(n log n) dalam semua kasus dan bersifat stabil.
Langkah Membagi
Bagilah larik secara rekursif pada titik tengah hingga setiap bagian hanya memiliki satu elemen. Satu elemen sudah pasti terurut, sehingga menjadi kasus dasar.
Langkah Menggabungkan
Operasi inti menggabungkan dua rangkaian yang sudah terurut menjadi satu. Telusuri keduanya dengan penunjuk indeks, dan selalu salin elemen terdepan yang lebih kecil berikutnya.
#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;
}Mengapa Bersifat Stabil
Penggabungan menggunakan a[i] <= a[j], sehingga ketika dua elemen sama, elemen dari rangkaian kiri diambil terlebih dahulu. Karena rangkaian kiri berisi elemen yang muncul lebih awal, urutan aslinya tetap terjaga.
Pengendali Rekursif
Mergesort melakukan rekursi pada setiap bagian, lalu menggabungkannya. Kami meneruskan buffer kerja sementara yang digunakan bersama untuk menghindari alokasi pada setiap pemanggilan.
#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;
}Penggunaan Memori
Berbeda dari quicksort, mergesort memerlukan memori tambahan O(n) untuk buffer penggabungan. Ini merupakan kelemahan utamanya untuk larik yang sangat besar ketika memori terbatas.
O(n log n) yang Terjamin
Rekursi selalu membagi larik menjadi dua, menghasilkan tingkat sebanyak log n, dan setiap tingkat menggabungkan n elemen. Jadi, mergesort memiliki kompleksitas O(n log n) pada kasus terbaik, rata-rata, dan terburuk, berbeda dari quicksort.
Menghitung Tingkat Penggabungan
Jumlah tingkat rekursi adalah ceil(log2 n). Mari kita menghitungnya untuk beberapa ukuran.
#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 dari Bawah ke Atas
Variasi iteratif ini menggabungkan rangkaian berukuran 1, lalu 2, kemudian 4, dengan menggandakan ukurannya pada setiap lintasan. Variasi ini sepenuhnya menghindari rekursi dan cocok untuk daftar berantai.
#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;
}Kapan Memilih Mergesort
Pilih mergesort ketika Anda memerlukan:
- O(n log n) yang terjamin, tanpa kasus buruk
- Stabilitas
- Pengurutan daftar berantai (tidak memerlukan akses acak)
- Pengurutan eksternal untuk data yang terlalu besar untuk RAM
Mergesort vs Quicksort
Quicksort biasanya lebih cepat dalam praktik dan mengurutkan langsung di tempat, tetapi tidak stabil dan memiliki kasus terburuk yang buruk. Mergesort stabil dengan batas kompleksitas yang terjamin, tetapi menggunakan memori tambahan. Pilih berdasarkan batasan Anda.
Uji Singkat
Uji pemahaman Anda tentang mergesort.
Rangkuman
Anda telah mempelajari mergesort.
- Membagi menjadi dua, mengurutkan setiap bagian, lalu menggabungkannya
- Penggabungan selalu mendahulukan bagian kiri untuk kunci yang sama, sehingga menghasilkan stabilitas
- O(n log n) terjamin dalam semua kasus
- Memerlukan memori tambahan O(n); sangat baik untuk daftar berantai dan pengurutan eksternal
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Mergesort” gratis?
Ya — teks lengkap “Mergesort” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus C Academy, upgrade ke CoddyKit PRO. Kursus C Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Mergesort”?
Pengurutan stabil. Kamu berlatih C Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai C Academy?
Tidak diperlukan pengalaman sebelumnya. C Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “Mergesort” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran C Academy ini?
Ya. Setiap pelajaran C Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.