Cara Menggabungkan Dua Array Berurut di Jawa

1. Perkenalan

Dalam tutorial ini, kita akan belajar bagaimana menggabungkan dua array yang diurutkan menjadi satu array yang diurutkan.

2. Masalah

Mari kita pahami masalahnya. Kami memiliki dua larik yang diurutkan dan kami ingin menggabungkannya menjadi satu.

3. Algoritma

Saat kami menganalisis masalah, cukup mudah untuk mengamati bahwa kami dapat menyelesaikan masalah ini dengan menggunakan operasi penggabungan dari Merge Sort.

Katakanlah kita memiliki dua array yang diurutkan foo dan bar dengan panjang fooLength dan barLength , masing-masing. Selanjutnya, kita dapat mendeklarasikan array lain yang digabungkan dengan ukuran fooLength + barLength .

Kemudian kita harus melintasi kedua array dalam loop yang sama. Kami akan mempertahankan nilai indeks saat ini untuk masing-masing, fooPosition dan barPosition . Pada iterasi tertentu dari loop kami, kami mengambil array mana pun yang memiliki elemen bernilai lebih kecil di indeksnya dan memajukan indeks itu. Elemen ini akan menempati posisi berikutnya dalam array yang digabungkan .

Terakhir, setelah kita mentransfer semua elemen dari satu larik, kita akan menyalin sisanya dari larik lainnya ke dalam larik gabungan .

Sekarang mari kita lihat prosesnya dalam gambar untuk lebih memahami algoritme.

Langkah 1:

Kami mulai dengan membandingkan elemen di kedua larik, dan kami memilih yang lebih kecil.

Kemudian kami menaikkan posisi di larik pertama .

Langkah 2:

Di sini kita menaikkan posisi di array kedua dan beralih ke elemen berikutnya yaitu 8.

Langkah 3:

Di akhir iterasi ini, kita telah menjelajahi semua elemen dari larik pertama .

Langkah 4:

Pada langkah ini, kami hanya menyalin semua elemen yang tersisa dari array kedua ke hasil .

4. Implementasi

Sekarang mari kita lihat bagaimana mengimplementasikannya:

public static int[] merge(int[] foo, int[] bar) { int fooLength = foo.length; int barLength = bar.length; int[] merged = new int[fooLength + barLength]; int fooPosition, barPosition, mergedPosition; fooPosition = barPosition = mergedPosition = 0; while(fooPosition < fooLength && barPosition < barLength) { if (foo[fooPosition] < bar[barPosition]) { merged[mergedPosition++] = foo[fooPosition++]; } else { merged[mergedPosition++] = bar[barPosition++]; } } while (fooPosition < fooLength) { merged[mergedPosition++] = foo[fooPosition++]; } while (barPosition < barLength) { merged[mergedPosition++] = bar[barPosition++]; } return merged; }

Dan mari kita lanjutkan dengan tes singkat:

@Test public void givenTwoSortedArrays_whenMerged_thenReturnMergedSortedArray() { int[] foo = { 3, 7 }; int[] bar = { 4, 8, 11 }; int[] merged = { 3, 4, 7, 8, 11 }; assertArrayEquals(merged, SortedArrays.merge(foo, bar)); }

5. Kompleksitas

Kami melintasi kedua array dan memilih elemen yang lebih kecil. Pada akhirnya, kami menyalin elemen lainnya dari foo atau bar array. Jadi kompleksitas waktu menjadi O (fooLength + barLength) . Kami telah menggunakan array tambahan untuk mendapatkan hasilnya. Jadi kompleksitas ruang juga O (fooLength + barLength) .

6. Kesimpulan

Dalam tutorial ini, kita belajar bagaimana menggabungkan dua array yang diurutkan menjadi satu.

Seperti biasa, kode sumber untuk tutorial ini dapat ditemukan di GitHub.