Bagaimana cara menggabungkan dua array yang diurutkan dengan python?

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 + 1

Kompleksitas 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

Bagaimana cara menggabungkan dua array dalam urutan terurut dengan Python?

Bagaimana cara menggabungkan 2 array dengan Python?

Bagaimana Anda menggabungkan dua array yang diurutkan menjadi satu array yang diurutkan?

Bagaimana Anda menggabungkan dua algoritma array yang diurutkan?