Gabungkan Sortir di Jawa

1. Perkenalan

Dalam tutorial ini, kita akan melihat algoritma Merge Sort dan implementasinya di Java .

Pengurutan gabungan adalah salah satu teknik pengurutan yang paling efisien dan didasarkan pada paradigma “bagi dan taklukkan”.

2. Algoritma

Merge sort adalah algoritme "bagi dan taklukkan" di mana pertama-tama kita membagi masalah menjadi beberapa subproblem. Ketika solusi untuk submasalah sudah siap, kami menggabungkannya bersama-sama untuk mendapatkan solusi akhir untuk masalah tersebut.

Ini adalah salah satu algoritme yang dapat dengan mudah diimplementasikan menggunakan rekursi karena kita menangani subproblem daripada masalah utama.

Algoritme dapat dijelaskan sebagai proses 2 langkah berikut:

  • Divide: Pada langkah ini, kita membagi larik input menjadi 2 bagian , pivotnya menjadi titik tengah larik. Langkah ini dilakukan secara rekursif untuk semua setengah larik sampai tidak ada lagi larik setengah untuk membagi.
  • Conquer: Pada langkah ini, kita mengurutkan dan menggabungkan array yang terbagi dari bawah ke atas dan mendapatkan array yang diurutkan.

Diagram berikut menunjukkan proses pengurutan gabungan lengkap untuk larik contoh {10, 6, 8, 5, 7, 3, 4}.

Jika kita melihat lebih dekat pada diagram, kita dapat melihat bahwa array secara rekursif dibagi menjadi dua bagian sampai ukurannya menjadi 1. Setelah ukurannya menjadi 1, proses penggabungan beraksi dan mulai menggabungkan kembali array saat menyortir:

3. Implementasi

Untuk implementasinya, kita akan menulis fungsi mergeSort yang mengambil input array dan panjangnya sebagai parameter. Ini akan menjadi fungsi rekursif sehingga kita membutuhkan basis dan kondisi rekursif.

Kondisi dasar memeriksa apakah panjang array adalah 1 dan itu hanya akan kembali. Untuk kasus lainnya, panggilan rekursif akan dijalankan.

Untuk kasus rekursif, kita mendapatkan indeks tengah dan membuat dua array sementara l [] dan r [] . Fungsi mergeSort kemudian dipanggil secara rekursif untuk kedua sub-array:

public static void mergeSort(int[] a, int n) { if (n < 2) { return; } int mid = n / 2; int[] l = new int[mid]; int[] r = new int[n - mid]; for (int i = 0; i < mid; i++) { l[i] = a[i]; } for (int i = mid; i < n; i++) { r[i - mid] = a[i]; } mergeSort(l, mid); mergeSort(r, n - mid); merge(a, l, r, mid, n - mid); }

Kami kemudian memanggil fungsi merge yang mengambil input dan sub-array serta indeks awal dan akhir dari kedua sub array .

Fungsi penggabungan membandingkan elemen dari kedua sub-array satu per satu dan menempatkan elemen yang lebih kecil ke dalam array input.

Ketika kita mencapai akhir dari salah satu sub-array, sisa elemen dari array lain disalin ke dalam array input sehingga memberi kita array terurut terakhir:

public static void merge( int[] a, int[] l, int[] r, int left, int right) { int i = 0, j = 0, k = 0; while (i < left && j < right) { if (l[i] <= r[j]) { a[k++] = l[i++]; } else { a[k++] = r[j++]; } } while (i < left) { a[k++] = l[i++]; } while (j < right) { a[k++] = r[j++]; } } 

Tes unit untuk program:

@Test public void positiveTest() { int[] actual = { 5, 1, 6, 2, 3, 4 }; int[] expected = { 1, 2, 3, 4, 5, 6 }; MergeSort.mergeSort(actual, actual.length); assertArrayEquals(expected, actual); }

4. Kompleksitas

Karena merge sort adalah algoritme rekursif, kompleksitas waktu dapat dinyatakan sebagai relasi rekursif berikut:

T(n) = 2T(n/2) + O(n)

2T (n / 2) sesuai dengan waktu yang dibutuhkan untuk mengurutkan sub-array dan O (n) waktu untuk menggabungkan seluruh array.

Ketika diselesaikan, kompleksitas waktu akan menjadi O (nLogn).

Ini berlaku untuk kasus terburuk, rata-rata, dan terbaik karena akan selalu membagi array menjadi dua dan kemudian menggabungkannya.

Kompleksitas ruang dari algoritme adalah O (n) karena kami membuat array sementara di setiap panggilan rekursif.

5. Kesimpulan

Dalam tutorial singkat ini, kita melihat cara kerja algoritma pengurutan gabungan dan bagaimana kita bisa menerapkannya di Java.

Seluruh kode kerja tersedia di GitHub.