MARGE SORT

ALGORITMA PEMROGRAMAN II

MERGE SORT

DASAR TEORI

Merge Sort

            Merge sort merupakan algoritma pengurutan dalam ilmu komputer yangdirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yangtidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnyayang terlalu besar. Merge sort berfungsi untuk mengurutkan sebuah array berisinilai-nilai yang acak dengan cara mengurutkan sebagian dari array terlebih dahulusebelum mengurutkan semua array secara keseluruhan. Berikut menjelaskan langkahkerja dari Merge sort.

a.       Divide adalah membagi masalah menjadi beberapa upa-masalah yang mmilikikemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama).Dan membagi elemen – elemen dari rangkaian data menjadi dua bagian.

b.      Conquer adalah memecahkan (menyelesaikan) masing-masing upa-masalah(secara rekursif). Dan memberi solusi pada setiap bagian dengan memanggil prosedur merge sort.

c.       Combine adalah menggabungkan solusi masing-masing upa-masalahsehingga membentuk solusi masalah semula.dan menggabungkan dua bagiantersebut secara rekursif untuk mendapatkan rangkaian data berurutan.

            Algoritma pengurutan data mergesort dilakukan dengan menggunakan cara divideandconquer 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 mergesort merupakan metode yang membutuhkan fungsi rekursi untuk penyelesaiannya.

Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Mergesort.

1.   Divide
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.

2.   Conquer
Conquer setiap bagian dengan memanggil prosedur mergesortsecararekursif

3.    Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkanrangkaian data berurutan.

            Proses rekursi 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.

PELKSANAAN PRAKTIKUM

         RAPTOR

Tab Main

Tab Data

Tab Tampilan

 

Tab Marge Sort

Run Dari Program

Program Netbeans

Main Program

Hasil Run Dari Program

                                                                                                         

     

  Kesimpulan

      MergeSort adalah metode pengurutan data dengan cara data dibagi menjadi sub kumpulan-subkumpulan yang kemudian subkumpulan tersebut diurutkan secara terpisah, dan kemudian digabungkan kembali dengan metode merging.

Subscribe to receive free email updates: