Home » Pemrograman » Konsep Metode Merge Sort

Konsep Metode Merge Sort

usahawan-maju

Metode "Merge Sort" atau sering juga disebut metode penggabungan. 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.
Dalam algoritma juga mengenal dua macam pengurutan, yaitu
1.    urut naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling besar
2.    urut turun (descending) yaitu data yang mempunyai nilai paling besar sampai paling kecil.
Dimana prinsip utama yang diimplementasikan pada algoritma merge-sort seringkali disebut sebagai pecah-belah dan taklukkan (bahasa Inggris: divide and conquer). Hal ini dikarenakan algoritma sorting melakukan pembagian struktur data sebelum kemudian dioperasikan satu per satu. Intinya, algoritma ini menggunakan du aide utama, yaitu sebagai beriut:
1.    Sebuah list yang kecil membutuhkan langkah yang lebih sedikit untuk pengurutan daripada sebuah list yang besar.
2.    Untuk membentuk sebuah list terurut dari dua buah list terurut membutuhkan langkah yang lebih sedikit daripada membentuk sebuah list terurut dari dua buah list tak terurut.
 Adapun cara kerja algoritma merge sort dengan berpola divide and conquer adalah sebagai berikut:
1.    Divide : membagi list yang tak berurut menjadi dua bagian sama panjang atau boleh salah satunya lebih panjang satu elemen.
2.    Conquer : membagi masing-masing dari sub-list secara rekursif sampai didapatkan list dengan ukuran 1.
3.    Combine : menggabungkan 2 sub-list kembali menjadi satu list terurut.
Dengan kata lainmetode merge sort merupakan metode yang membutuhkan fungsi rekursi untuk penyelesaiannya. Proses rekursif berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian. Untuk lebih jelasnya, perhatikan gambar berikut :

at 17.55
Labels:
usahawan-maju
Konsep Metode Merge Sort | 5