Pengurutan Cepat dan Penerapannya · Pelajaran 7 dari 10
Merge sort
10 menit baca · BelajarCode
Merge sort memakai strategi divide and conquer (bagi dan taklukkan):
- Bagi data menjadi dua bagian yang sama besar.
- Urutkan masing-masing bagian dengan merge sort juga (rekursif).
- Gabungkan dua bagian yang sudah urut menjadi satu.
Kasus dasarnya: data berisi satu elemen atau kosong sudah pasti urut.
Langkah kunci: menggabungkan
Menggabungkan dua list yang sudah urut itu mudah: bandingkan data paling depan dari keduanya, ambil yang lebih kecil, ulangi.
1def gabung(kiri, kanan):2 hasil = []3 i = j = 04 while i < len(kiri) and j < len(kanan):5 if kiri[i] <= kanan[j]:6 hasil.append(kiri[i])7 i += 18 else:9 hasil.append(kanan[j])10 j += 111 hasil.extend(kiri[i:])12 hasil.extend(kanan[j:])13 return hasil1415print(gabung([3, 27, 38, 43], [9, 10, 82]))[3, 9, 10, 27, 38, 43, 82]
Merge sort lengkap
1def gabung(kiri, kanan):2 hasil = []3 i = j = 04 while i < len(kiri) and j < len(kanan):5 if kiri[i] <= kanan[j]:6 hasil.append(kiri[i])7 i += 18 else:9 hasil.append(kanan[j])10 j += 111 return hasil + kiri[i:] + kanan[j:]1213def merge_sort(data):14 if len(data) <= 1:15 return data16 tengah = len(data) // 217 kiri = merge_sort(data[:tengah])18 kanan = merge_sort(data[tengah:])19 return gabung(kiri, kanan)2021print(merge_sort([38, 27, 43, 3, 9, 82, 10]))[3, 9, 10, 27, 38, 43, 82]
- Langkah 1, Mulai: [38, 27, 43, 3, 9, 82, 10]
- Langkah 2, Proses: Bagi: [38, 27, 43] dan [3, 9, 82, 10]
- Langkah 3, Proses: Bagi lagi sampai tersisa satu-satu: [38] [27] [43] [3] [9] [82] [10]
- Langkah 4, Proses: Gabung: [27, 38] [43] [3, 9] [10, 82]
- Langkah 5, Proses: Gabung: [27, 38, 43] dan [3, 9, 10, 82]
- Langkah 6, Selesai: [3, 9, 10, 27, 38, 43, 82]
Kenapa O(n log n)?
- Data dibagi dua terus sampai tersisa satu-satu, sehingga ada sekitar log n tingkat pembagian.
- Di setiap tingkat, proses penggabungan memeriksa total n data.
- Jadi totalnya sekitar n × log n langkah, untuk kasus terbaik, rata-rata, maupun terburuk.
Merge sort juga stabil, karena saat dua nilai sama, <= mengambil dari bagian kiri lebih dulu. Kekurangannya, merge sort butuh memori tambahan untuk menyimpan hasil penggabungan.
Cek pemahaman
Kenapa merge_sort tidak pernah berjalan tanpa henti?
Latihan
Gabungkan tiga list
Pakai fungsi gabung dua kali untuk menggabungkan tiga list urut berikut menjadi satu list urut: [1, 5, 9], [2, 6], dan [3, 4, 10].
Pembahasan
1def gabung(kiri, kanan):2 hasil = []3 i = j = 04 while i < len(kiri) and j < len(kanan):5 if kiri[i] <= kanan[j]:6 hasil.append(kiri[i])7 i += 18 else:9 hasil.append(kanan[j])10 j += 111 return hasil + kiri[i:] + kanan[j:]1213print(gabung(gabung([1, 5, 9], [2, 6]), [3, 4, 10]))[1, 2, 3, 4, 5, 6, 9, 10]
Hasil penggabungan dua list pertama sudah urut, sehingga bisa langsung digabung dengan list ketiga.
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.