METODE PENGURUTAN MERGE SORT

Ya, kali ini gua posting lagi tentang Mergesort, dan sebenernya ini jug hasil dari quis, checkthis out:

 Mergesort 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 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.

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

a.       pertama kali larik tersebut dibagi menjadi dua bagian, {3, 9, 4} dan {1, 5, 2}

b.      Kedua larik kemudian diurutkan secara terpisah sehingga menjadi {3, 4, 9} dan {1, 2, 5}

c.       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)

d.      langkah berikutnya adalah penggabungan dari masing-masing larik ke dalam larik baru yang dibuat sebelumnya

e.       {1, 2} ↔{3, 4, 9} dan {5}

f.       {1, 2, 3} ↔ {4, 9} dan {5}

g.      {1, 2, 3, 4}↔{9} dan {5}

h.      {1, 2, 3, 4, 5}↔{9} dan {null}

i.        {1, 2, 3, 4, 5, 9}↔{null}dan {null}

Contoh program sedehana mergesort

Public class mergeSort{

Public static void main(String args [ ] ){

int i;

int array [ ] = {7,5,1,3,6,4,9,8};

System.out.println("\n\n Kelompok 3\n\n");

System.out.println(" Pengurutan dengan MergeSort\n\n");

System.out.println("Data Sebelum Diurutkan:\n");

    for(i = 0; i < array.length; i++)

System.out.print( array[i]+"  ");

System.out.println( );

Merge Sort_srt(array,0, array.length - 1);

System.out.print("Data Setelah Diurutkan:\n");

    for(i = 0; i < array.length; i++)

System.out.print(array[i]+"  ");

System.out.println();

    }

Public static void mergeSort_srt(int array[ ],int lo, int n){

 int low = lo;

int high = n;

if (low > = high)

    {return; }

int middle = (low + high) / 2;

mergeSort_srt(array, low, middle);

mergeSort_srt(array, middle + 1, high);

int end_low = middle;

int start_high = middle + 1;

while ((lo <= end_low) && (start_high <= high))

    {

if (array[low] < array[start_high]) {

low++; }

else {

int Temp = array[start_high];

            for (int k = start_high- 1; k > =low; k--) 

                {array[k+1] = array[k]; }

array[low] = Temp;

low++;

end_low++;

start_high++;  }

        }

    } 

Kesimpulan

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

Endah Sakti M      

Nanang Nur Ichsan          

Kholid Maulana              

Jerry Andrianto                  

Deni Indra P