Contoh Penyelesaian Kasus Merge Sort dengan Java

Merge sort merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar. Algoritma ini ditemukan oleh John von Neumann pada tahun 1945. (id.wikipedia.org)

Algoritma pengurutan data merge sort dilakukan dengan menggunakan cara divide and conquer yaitu dengan memecah kemudian menyelesaikan setiap bagian kemudian menggabungkannya kembali. Pertama data dipecah menjadi 2 bagian dimana bagian pertama merupakan setengah (jika data genap) atau setengah minus satu (jika data ganjil) dari seluruh data, kemudian dilakukan pemecahan kembali untuk masing-masing blok sampai hanya terdiri dari satu data tiap blok.
Setelah itu digabungkan kembali dengan membandingkan pada blok yang sama apakah data pertama lebih besar daripada data ke-tengah+1, jika ya maka data ke-tengah+1 dipindah sebagai data pertama, kemudian data ke-pertama sampai ke-tengah digeser menjadi data ke-dua sampai ke-tengah+1, demikian seterusnya sampai menjadi satu blok utuh seperti awalnya. Sehingga metode merge sort merupakan metode yang membutuhkan fungsi rekursi untuk penyelesaiannya.

Contoh penerapan atas sebuah larik/array sebagai data sumber yang akan diurutkan {3, 9, 4, 1, 5, 2} adalah sebagai berikut:

• pertama kali larik tersebut dibagi menjadi dua bagian, {3, 9, 4} dan {1, 5, 2}
• Kedua larik kemudian diurutkan secara terpisah sehingga menjadi {3, 4, 9} dan {1, 2, 5}
• Sebuah larik baru dibentuk yang sebagai penggabungan dari kedua larik tersebut {1}, sementara nilai-nilai dalam masing larik {3, 4, 9} dan {2, 5} (nilai 1 dalam elemen larik ke dua telah dipindahkan ke larik baru)
• langkah berikutnya adalah penggabungan dari masing-masing larik ke dalam larik baru yang dibuat sebelumnya.
• {1, 2} <-> {3, 4, 9} dan {5}
• {1, 2, 3} <-> {4, 9} dan {5}
• {1, 2, 3, 4} <-> {9} dan {5}
• {1, 2, 3, 4, 5} <-> {9} dan {null}
• {1, 2, 3, 4, 5, 9} <-> {null} dan {null}

sebagai contoh soal sebagai berikut :

Membuat program dengan paradigma OOP yang dapat membaca isi sebuah file teks dari file berekstensi *.txt. file tersebut berisi sejumlah nama yang terdiri atas nama depan dan nama belakang.

Program yang dibuat harus dapat mengurutkan data nama tersebut berdasarkan nama depan dan atau nama belakang menggunakan metode merge sort.

Program harus dapat meminta masukkan dari user lokasi dari file teks yang berisi data, dan meminta meminta user untuk memilih apakah ingin diurutkan berdasar nama depan atau nama belakang.

Input                  :   sebuah file teks dan pilihan untuk mengurutkan berdasrakan nama depan atau nama belakang

Output               :    sebuah file teks yang telah terurut berdasarkan nama depan atau nama belakang sesuai dengan pilihan yang diminta.

Langkah-langkah penyelesaian

1. Langkah pertama adalah melakukan pembacaan data dari file teks, dalam praktikum ini nama file adalah Data Nama.txt dan selanjutnya akan disebut seperti itu. Pembacaan data dilakukan sekaligus memeriksa apakah file tersebut valid atau tidak.
2.  Kemudian setelah pembacaan data, dibuat sebuah array satu dimensi bertipe String sebagai penampung sementara dari data yang ada. Pada saat pembacaan, setiap pembacaan perbaris, akan dituliskan pada array yang bersangkutan pada baris yang telah ditetapkan melalui metode perulangan.
3. Setelah didapat array sementara yang berisi data nama perbaris dari file Data Nama.txt, langkah selanjutnya adalah membuat array 2 dimensi dengan dimensi panjang adalah panjang array sementara – 1 dan lebar 3, lebar 3 digunakan karena terdapat nama yang memiliki 3 kata. Setiap kata pada setiap urutan array sementara tadi akan dipecah dan hasilnya akan dimasukkan pada array 2 dimensi tadi, sehingga akhirnya didapatkan data array bertipe String yang memiliki data nama dengan pemisahan perkata dari masing-masing nama.
4. Metode pengurutan dengan nama depan dilakukan dengan membandingkan antara String pertama dari nama depan dengan String pertama nama depan yang lain, pembandingan dengan menggunakan nilai ASCII dari masing-masing String melalui method comparTo. Jika nama pertama memiliki awalan String yang memiliki nilai ASCII lebih besar, maka nama pertama dipindah sesuai dengan metode merge sort yang telah disebutkan di atas, dan seterusnya.
5. Metode pengurutan nama belakang dilakukan dengan membalik terlebih dahulu nama depan dengan nama belakang, kemudian dilakukan proses pengurutan melalui metode merge sort, setelah itu nama depan dan nama belakang dikembalikan lagi seperti semula.

penyelesaian dari kasus ini ada pada link dibawah ini :

kelas mergeSort

kelas Main