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.
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
2.
Conquer
Conquer setiap bagian dengan memanggil prosedur mergesortsecararekursif
Conquer setiap bagian dengan memanggil prosedur mergesortsecararekursif
3.
Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkanrangkaian data berurutan
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
