Terkadang kami perlu menggabungkan dua daftar yang diurutkan. Jenis penyortiran ini dikenal sebagai penyortiran gabungan. Ada berbagai cara untuk menggabungkan dua daftar yang diurutkan dengan python. Dalam seluruh tutorial ini, Anda akan mengetahui cara menggabungkan dua daftar yang diurutkan dengan python dengan berbagai contoh
Metode untuk Menggabungkan dua daftar yang diurutkan dengan Python
Di bagian ini, Anda akan mengetahui semua metode yang dapat Anda gunakan untuk menggabungkan dua daftar yang sudah diurutkan dengan python. Mari kenali masing-masing
Metode 1. Menggunakan fungsi sortir()
Anda dapat menggunakan fungsi python bawaan diurutkan () untuk menyortir dua daftar gabungan. Di sini Anda harus terlebih dahulu menambahkan daftar dan kemudian meneruskan daftar gabungan sebagai argumen dari fungsi sortir(). Jalankan baris kode di bawah ini dan lihat hasilnya
Diberikan dua larik terurut A[] dan B[] dengan ukuran N dan M. Tugasnya adalah menggabungkan kedua array menjadi satu array dalam urutan yang tidak menurun
Contoh
Memasukkan. A[] =[3, 9, 10, 18, 23], B[] = [5, 12, 15, 20, 21, 25]
Keluaran. [3, 5, 9, 10, 12, 15, 18, 20, 21, 23, 25]
Penjelasan. Array gabungan berisi semua elemen dari kedua array dalam urutan terurut
Bingung tentang pekerjaan Anda selanjutnya?
Dalam 3 langkah sederhana, Anda dapat menemukan peta jalan karier yang dipersonalisasi dalam pengembangan Perangkat Lunak secara GRATIS
Perluas di Tab Baru
Memasukkan. A[] = [1, 5], B[] = [4, 6, 7]
Keluaran. [1, 4, 5, 6, 7]
Sisipkan dan Sortir Pendekatan
Pendekatan yang paling naif adalah menggabungkan elemen dari satu larik ke larik lain dan mengurutkan larik yang dihasilkan
Kode C++
void merge(int nums1[], int m, int nums2[], int n) { for (int i = 0; i < n; i++) { nums1[i + m] = nums2[i]; } sort(nums1, nums1 + n + m); }Kode Jawa
public void merge(int[] nums1, int m, int[] nums2, int n) { for (int i = 0; i < n; i++) { nums1[i + m] = nums2[i]; } Arrays.sort(nums1); }_Kode Piton
def merge(nums1, m, nums2, n) for i in range(n): nums1[i + m] = nums2[i] nums1.sort()Kompleksitas Waktu. O((N + M)log(N+M)), di mana N dan M adalah ukuran array A[] dan B[]
Kompleksitas Ruang. O(N), pengurutan bawaan membutuhkan ruang
Gabungkan Metode Sortir
Ide kunci untuk dicatat di sini adalah bahwa kedua array diurutkan. Oleh karena itu, dengan memanfaatkan fakta ini, kita dapat menerapkan metode yang mirip dengan teknik pengurutan gabungan
Buat array bantu ukuran N + M dan masukkan elemen gabungan dalam array ini
Mari kita pahami pendekatan ini dengan sebuah contoh
Algoritma
- Buat array tambahan ukuran N + M
- Letakkan dua pointer i dan j dan inisialisasi ke 0.
- Pointer i menunjuk ke array pertama, sedangkan pointer j menunjuk ke array kedua
- Lintasi kedua larik secara bersamaan menggunakan penunjuk, dan pilih elemen terkecil di antara kedua larik dan masukkan ke dalam larik tambahan
- Tingkatkan pointer
- Setelah traversal, kembalikan array yang digabungkan
Implementasi C++
void mergeArrays(int arr1[], int arr2[], int n1, int n2, int arr3[]) { int i = 0, j = 0, k = 0; while (i < n1 && j < n2) { if (arr1[i] < arr2[j]) arr3[k++] = arr1[i++]; else arr3[k++] = arr2[j++]; } while (i < n1) arr3[k++] = arr1[i++]; while (j < n2) arr3[k++] = arr2[j++]; }Implementasi Jawa
public static void mergeArrays(int[] arr1, int[] arr2, int n1, int n2, int[] arr3) { int i = 0, j = 0, k = 0; while (i < n1 && j < n2) { if (arr1[i] < arr2[j]) arr3[k++] = arr1[i++]; else arr3[k++] = arr2[j++]; } while (i < n1) arr3[k++] = arr1[i++]; while (j < n2) arr3[k++] = arr2[j++]; }_Implementasi Python
def mergeArrays(arr1, arr2, n1, n2): arr3 = [None] * (n1 + n2) i = 0 j = 0 k = 0 while i < n1 and j < n2: if arr1[i] < arr2[j]: arr3[k] = arr1[i] k = k + 1 i = i + 1 else: arr3[k] = arr2[j] k = k + 1 j = j + 1 while i < n1: arr3[k] = arr1[i] k = k + 1 i = i + 1 while j < n2: arr3[k] = arr2[j] k = k + 1 j = j + 1Kompleksitas Waktu. O(N + M), di mana N dan M adalah ukuran larik A[] dan B[]
Kompleksitas Ruang. O(N + M), karena larik bantu digunakan
FAQ
Bagaimana kompleksitas ruang O(1) untuk pendekatan dua petunjuk?
Karena, kami menempatkan penggabungan semua elemen ke dalam larik pertama, tanpa membuat ruang bantu lainnya, kompleksitas ruangnya adalah O(1)
Bagaimana pendekatan dua pointer berbeda dari pendekatan sortir gabungan?
Pendekatan sortir gabungan mempertimbangkan larik tambahan untuk mengurutkan dan menyimpan dua penunjuk dan awal larik dan menggabungkannya
Sedangkan, pendekatan dua titik, mulai mengulang dari belakang dan terus menggabungkan elemen pada tempatnya