Menggabungkan Dua Urutan Terurut
Menelusuri kedua list dengan satu pointer masing-masing
Menggabungkan Dua Urutan Terurut adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 4 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 Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Langkah Penggabungan
Diberikan dua daftar terurut, gabungkan keduanya menjadi satu daftar terurut. Penggabungan ini adalah inti dari sort gabung dan muncul di berbagai tempat. 🔗
Dua Masukan, Masing-Masing Satu Penunjuk
Berikan setiap daftar satu penunjuk, keduanya dimulai dari indeks 0. Anda akan menggerakkannya maju bersama-sama, tidak pernah mundur.
i = 0
j = 0Selalu Ambil yang Lebih Kecil
Pada setiap langkah, bandingkan kedua elemen terdepan. Tambahkan yang lebih kecil ke hasil karena elemen itu harus muncul berikutnya dalam urutan terurut.
Majukan Pemenang
Setelah mengambil sebuah nilai, lakukan advance hanya pada penunjuk asal nilai tersebut. Daftar lainnya masih memiliki elemen terkecil yang menunggu.
if a[i] <= b[j]:
out.append(a[i])
i += 1
else:
out.append(b[j])
j += 1Perulangan Utama
Teruskan penggabungan selama kedua daftar masih memiliki elemen. Setelah salah satunya habis, perbandingan tidak lagi masuk akal.
while i < len(a) and j < len(b):
# compare and append
passKuras Sisa Elemen
Saat salah satu daftar kosong, daftar lainnya sudah terurut, jadi cukup lakukan append pada sisa bagian belakangnya langsung ke hasil.
out.extend(a[i:])
out.extend(b[j:])Mengapa Bagian Belakang Tidak Perlu Diproses
Sisa bagian belakang sudah terurut, jadi tidak diperlukan perbandingan lagi. Salah satu dari dua pemanggilan extend itu cukup menambahkan elemen, sedangkan yang lainnya tidak menambahkan apa pun.
Total Waktu Linear
Setiap elemen diperiksa satu kali, sehingga penggabungan dua daftar berukuran n dan m memerlukan waktu O(n + m). Itulah waktu tercepat yang dapat dicapai.
Pertahankan Stabilitas
Menggunakan <= saat nilai sama akan mempertahankan elemen-elemen yang sama dalam urutan aslinya. Stabilitas ini penting saat Anda membawa data tambahan.
Gabungkan Juga dari Arah Terbalik
Untuk menggabungkan ke penyangga tanpa ruang kosong tambahan, telusuri dari belakang dan tempatkan elemen terbesar di posisi terakhir. Gagasannya sama, hanya dicerminkan.
Dari Penggabungan ke sort
Pecah, urutkan kedua bagian, lalu gabungkan: rekursi tersebut adalah sort gabung. Penggabungan dengan dua penunjuk yang baru Anda pelajari adalah mesin intinya.
Pemeriksaan Singkat
Anda sedang menggabungkan dua daftar terurut dengan satu penunjuk di masing-masing daftar.
Rangkuman
Telusuri dua daftar terurut dengan masing-masing satu penunjuk, selalu mengambil elemen terdepan yang lebih kecil, lalu kuras sisa bagian belakangnya. Algoritme ini berjalan dalam O(n + m) dan menjadi dasar sort gabung. 🚀
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Menggabungkan Dua Urutan Terurut” gratis?
Ya — teks lengkap “Menggabungkan Dua Urutan Terurut” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Menggabungkan Dua Urutan Terurut”?
Menelusuri kedua list dengan satu pointer masing-masing Kamu berlatih Competitive Programming 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 Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming 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 4 dari 4.
Berapa lama pelajaran “Menggabungkan Dua Urutan Terurut” 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 Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming 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.
Semua pelajaran dalam kursus ini
- Two Pointer pada Array Terurut
- Menemukan Pasangan dengan Jumlah Tertentu
- Menghapus Duplikat di Tempat
- Menggabungkan Dua Urutan Terurut