Salah satu algoritma pengurutan yang paling efisien adalah algoritma pengurutan gabungan. Merge sort memiliki dua fase. fase pemisahan dan fase penggabungan. Kami tidak akan mendalami algoritme lanjutan ini di buku ini. Namun, kita dapat menulis kode untuk babak kedua. menggabungkan dua daftar bilangan bulat yang telah diurutkan sebelumnya ke dalam satu daftar yang diurutkan
Deskripsi Latihan
Tulis fungsi mergeTwoLists() dengan dua parameter list1 dan list2. Daftar angka yang diteruskan untuk parameter ini sudah diurutkan dari angka terkecil hingga terbesar. Fungsi mengembalikan satu daftar terurut dari semua angka dari dua daftar ini
Anda dapat menulis fungsi ini dalam satu baris kode dengan menggunakan fungsi sorted() Python
kembali diurutkan (daftar1 + daftar2)
Tapi ini akan menggagalkan tujuan latihan, jadi jangan gunakan fungsi sorted() atau metode sort() sebagai bagian dari solusi Anda
Pernyataan assert Python ini menghentikan program jika kondisinya adalah False. Salin ke bagian bawah program solusi Anda. Solusi Anda benar jika kondisi pernyataan assert berikut semuanya Benar
menegaskan mergeTwoLists([1, 3, 6], [5, 7, 8, 9]) == [1, 3, 5, 6, 7, 8, 9]
menegaskan mergeTwoLists([1, 2, 3], [4, 5]) == [1, 2, 3, 4, 5]
menegaskan mergeTwoLists([4, 5], [1, 2, 3]) == [1, 2, 3, 4, 5]
menegaskan mergeTwoLists([2, 2, 2], [2, 2, 2]) == [2, 2, 2, 2, 2, 2]
menegaskan mergeTwoLists([1, 2, 3], []) == [1, 2, 3]
menegaskan mergeTwoLists([], [1, 2, 3]) == [1, 2, 3]
Cobalah untuk menulis solusi berdasarkan informasi dalam uraian ini. Jika Anda masih kesulitan menyelesaikan latihan ini, bacalah bagian Desain Solusi dan Kasus Khusus serta Gotcha untuk petunjuk tambahan
Konsep prasyarat. daftar, while loop, operator Boolean, list10, untuk loop, list11 dengan dua argumen, list12
Desain Solusi
Daftar bilangan bulat, sudah dalam urutan terurut, diteruskan ke fungsi sebagai parameter list1 dan daftar2. Algoritme dimulai dengan dua variabel, i1 dan list14, yang keduanya dimulai pada indeks list15 dari daftar masing-masing. Kami juga membuat daftar kosong dalam variabel bernama list16 yang menyimpan hasil gabungan dari dua daftar
Di dalam while loop, kode melakukan hal berikut
· Lihat angka yang list18 dan i2 menunjuk ke
· Tambahkan angka yang lebih kecil ke list16
· Jika nomor list18 ditambahkan, tingkatkan list18 untuk menunjuk ke nomor berikutnya dalam daftar1. Jika tidak, tingkatkan list1_4 untuk menunjuk ke nomor berikutnya di list2
· Ulangi hingga list18 atau i2 melewati akhir daftarnya
Misalnya, Gambar 40-1 menunjukkan tiga iterasi pertama dari loop saat menggabungkan daftar list25 dan [5, 7, 8, 9]
Gambar 40-1. Tiga iterasi pertama dari loop yang menggabungkan dua daftar
Pikirkan kode ini seperti ritsleting asimetris. variabel i1 dan list14 terus bergerak di sepanjang daftar masing-masing, menambahkan nilainya ke hasil. Ketika list18 atau list14 mencapai akhir dari daftar mereka, daftar lainnya ditambahkan ke hasil. Daftar list16 ini berisi semua angka di list1 dan daftar2 dalam urutan terurut, sehingga fungsi mengembalikannya
Kasus Khusus dan Gotcha
Perlu diingat bahwa meskipun parameter list1_ dan list2 harus diurutkan, mereka tidak harus memiliki panjang yang sama
Jika salah satu dari argumen daftar ini ke mergeTwoLists() tidak diurutkan, fungsi akan mengembalikan daftar gabungan yang juga tidak dalam urutan terurut. Namun, untuk latihan ini, kami akan menganggap bahwa mergeTwoLists() selalu dipanggil dengan argumen yang valid
Sekarang coba tulis solusi berdasarkan informasi di bagian sebelumnya. Jika Anda masih kesulitan menyelesaikan latihan ini, bacalah bagian Template Solusi untuk petunjuk tambahan
Templat Solusi
Cobalah untuk menulis solusi dari awal. Namun jika Anda mengalami kesulitan, Anda dapat menggunakan sebagian program berikut sebagai tempat awal. Salin kode berikut dari https. //invpy. com/mergetwolists-template. py dan rekatkan ke editor kode Anda. Ganti garis bawah dengan kode untuk membuat program yang berfungsi
def menggabungkanDuaDaftar(daftar1, daftar2)
hasil = ____
i1 = ____
i2 = ____
sementara i1 < len(____) dan ____ < len(list2)
jika daftar1[____] < daftar2[____]
hasil. tambahkan(____[i1])
i1 += ____
kalau tidak
hasil. tambahkan(____[i2])
i2 += ____
jika i1 < len(____)
untuk j dalam rentang(i1, len(list1))
hasil. tambahkan(____[j])
jika i2 < len(____)
untuk j dalam rentang(i2, len(list2))
hasil. tambahkan(____[j])
hasil pengembalian
Solusi lengkap untuk latihan ini diberikan dalam Lampiran A dan https. //invpy. com/mergetwolists. py. Anda dapat melihat setiap langkah dari program ini saat berjalan di bawah debugger di https. //invpy. com/mergetwolists-debug/
Bacaan lebih lanjut
Merge sort menggunakan perilaku "menggabungkan dua daftar yang diurutkan menjadi satu daftar yang diurutkan" ini sebagai langkah dalam algoritmenya. Anda dapat mempelajari lebih lanjut tentang pengurutan gabungan dan algoritme rekursif lainnya dari buku saya, “The Recursive Book of Recursion. ” Buku lengkap tersedia secara gratis di bawah lisensi Creative Commons di https. // ciptakan dengan python. com/rekursi/