Review Sejenak Algoritma Merge Sort

Aaarrrrrrrrrgggggghhhhhh

Kemarin pas praktikum masih bingung dengan logika algortima Divide and Conquer dengan menggunakan metode merge sort, padahal sudah meluangkan banyak waktu untuk memahami logikanya tetap saja mentok di situ-situ juga. Padahal konsepnya sih sudah dapat, tapi pas berhadapan dengan codingnya, bujug dahKalo begitu akan saya coba review sedikit dan sekalian membuat dokumentasinya (takut-takut suatu hari lupa lagi ^_^) algoritma merge sort secara mendasar, moga-moga sekarang udah sedikit lebih mengerti.

Biasanyan algoritma merge sort digunakan untuk menyusun daftar dengan cara membagi daftar menjadi dua bagian yang lebih kecil. Kemudian kedua daftar yang baru tersebut disusun secara terpisah dan diurutkan masing-masing. Kemudian hasil sortir dari setiap bagian tersebut digabungkan dan diurutkan lagi hingga menghasilkan urutan yang sudah tersortir.

Intinya sih menggabungkan dua array yang sudah tersortir yaitu arrayA dan arrayB kemudian membuat array ketiga yaitu arrayC yang berguna untuk menampung nilai-nilai elemen dari arrayA dan arrayB. Berikut contoh programnya :

class MergeApp

{

public static void main(String[] args)

{

int[] arrayA={23,47,81,95};

int[] arrayB={7,14,39,55,62,74};

int[] arrayC= new int[10];

merge(arrayA,4,arrayB,6,arrayC);

cetak(arrayC,10);

}

public static void merge(int[] arrayA, int sizeA, int[] arrayB, int sizeB, int[] arrayC)

{

int idxA=0, idxB=0, idxC=0;

//loop pertama membandingkan nilai elemen dan

//mengalokasikan yang nilai yang kecil ke arrayC.

while(idxA < sizeA && idxB < sizeB)

if(arrayA[idxA] < arrayB[idxB])

arrayC[idxC++] = arrayA[idxA++];

else

arrayC[idxC++] = arrayB[idxB++];

while (idxA < sizeA) //jika arrayB sudah

arrayC[idxC++] = arrayA[idxA++]; //dialokasikan semua

while (idxB < sizeB) //jika arrayA sudah

arrayC[idxC++] = arrayB[idxB++]; //dialokasikan semua

}

public static void cetak(int[] arrayC, int size)

{

for(int i=0;i<size;i++)

System.out.print(arrayC[i] + ” “);

System.out.println(“”);

}

}

Gampang kan ?

Sebelumnya sudah dijelaskan, kalau inti dari metode merge sort adalah membagi array menjadi 2 bagian, sortir tiap-tiap bagian, kemudian panggil method merge() untuk menggabungkan dua bagian menjadi satu array yang sudah tersotir. Berikut merupakan listing program yang menggunakan dua method yaitu mergesort dan merge melalui pendekatan rekursif.

//import java.io.*;

class DArray

{

private double[] isiArray;

private int nElemen;

public DArray(int max)

{

isiArray = new double[max];

nElemen=0;

}

public void insert(double n)

{

isiArray[nElemen] = n;

nElemen++;

}

public void tampilkan()

{

for(int i=0;i<nElemen;i++)

System.out.println(isiArray[i] + ” “);

System.out.println(“”);

}

public void mergeSort()

{

double[] array = new double[nElemen];

mergeSort(array, 0, nElemen-1);

}

private void mergeSort(double[] array, int lowerBound, int upperBound)

{

if(lowerBound == upperBound)

return;

else

{

int mid = (lowerBound + upperBound) /2;

mergeSort(array,lowerBound,mid);

mergeSort(array,mid+1,upperBound);

merge(array,lowerBound, mid+1, upperBound);

}

}

private void merge(double[] array, int lowPtr, int highPtr, int upperBound)

{

int j = 0;

int lowerBound = lowPtr;

int mid = highPtr-1;

int n = upperBound-lowerBound+1;

while(lowPtr <= mid && highPtr <= upperBound)

if(isiArray[lowPtr] < isiArray[highPtr])

array[j++] = isiArray[lowPtr++];

else

array[j++]=isiArray[highPtr++];

while(lowPtr<=mid)

array[j++] = isiArray[lowPtr++];

while(highPtr<=upperBound)

array[j++]=isiArray[highPtr++];

for(j=0;j<n;j++)

isiArray[lowerBound+j] = array[j];

}

}

class MergeSortApp

{

public static void main(String[] args)

{

int maxSize = 100;

DArray arr;

arr = new DArray(maxSize);

arr.insert(64);

arr.insert(21);

arr.insert(33);

arr.insert(70);

arr.insert(12);

arr.insert(85);

arr.insert(44);

arr.insert(3);

arr.insert(99);

arr.insert(0);

arr.insert(108);

arr.insert(36);

arr.tampilkan();

arr.mergeSort();

arr.tampilkan();

}

}

Di bawah ini merupakan sebagian step-step dari algoritma di atas setelah di analisa, kalo salah…. ya ma’af namanya belajar ^_^,

Masuk ke low(0-3)

lakukan sortir low(0-3)

Masuk ke low(0-1)

lakukan sortir low(0-1)

Masuk ke (0-0)

return (0-0)

lakukan sortir high(0-1)

Masuk ke (1-1)

return (1-1)

lakukan merge pada (0-1) //isiArray=21 64 33 70

lakukan sortir pada high(0-3)

masuk ke (2-3)

lakukan sortir low(2-3)

masuk ke (2-2)

return (2-2)

lakukan sortir high(2-3)

masuk ke (3-3)

lakukan merge (2-3)

return (2-3) //isiArray = 21 64 33 70

lakukan merge (0-3)

return (0-3) //isiArray = 21 33 64 70

Untuk pemanggilan rekursif mergeSort yang kedua konsepnya hampir sama. Alhamdulillahakhirnya mulai mengerti sedikit, lebih baik mengerti sedikit daripada tidak tahu sama sekali.

4 responses to this post.

  1. mau nanya,,

    gmn sih cara belajar algoritma biar bikin gw nyaman pelajarinya???coz slama ini gw slalu nyerah dengan algoritma apalagi coding k java gw ga pernah berhasil..ampe bikin gw gmw baca2 lg bukunya..tolong bagi tips donk spy gw bsa bljr algoritma ya..
    trus pake buku apa yg bagus bwt belajar algoritma??
    tolong d bls ya…

    makasih sbelumnya..

    tolong kirim jawabn ke email gw ya..

    Balas

  2. Posted by Glen on Oktober 31, 2009 at 8:56 am

    Untuk ngerti algoritma, lo kudu harus belajar konsep pemrograman secara matang karena dengan menguasai konsep pemrograman secara matang, maka untuk masuk ke dalam bahasa pemrograman apapun akan mudah..

    Balas

  3. Posted by lies on Februari 8, 2010 at 5:09 am

    bisa minta gambaran algoritma dalam bahasa c atau c++nya ga ? dicoba dari yang lain tapi belum bhasil juga.

    Balas

  4. haduh gan, kalo ane pake vb 6. konsep ada coding dah yakin bener tapi kayanya kesalahan di array-nya, jadi sortingnya kadang bener dan sering ngaco, kira2 kurang apalagi ya????

    Balas

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: