icomit

Just another WordPress.com site

Teknik Divide & Conquer Dalam Algoritma Merge Sort

Merge sort merupakan salah satu algoritma yang digunakan untuk memecahkan masalah pengurutan/sorting. Merge sort menggunakan teknik tingkat lanjut dalam melakukan sorting yakni teknik membagi suatu deret elemen yangakan dilakukan sorting kemudian masing-masing bagian dilakukan sorting secara terpisah dalam mekanisme rekursif. Setelah tiap-tiap bagian dilakuka sorting maka akan dilakukan penyatuan kembali/merge sehingga menghasilkan suatu deret elemen yang terurut. Teknik sorting yang diterapkan oleh algoritma merge sort biasa disebut divide and conquer.

Dalam implementasinya, algoritma merge sort memerlukan tiga array yang digunakan sebagai penampungan elemen array sementara. Dua array digunakan untuk menampung elemen array yag dibagi dan satu array lagi digunakan sebagai wadah tempat array output yag telah terurut.  Dengan menggunakan array lebih dari satu membuat algoritma ini memerlukan banyak resource system. Akan tetapi hal ini dapat diminimalisir dengan menggunakan dua array seperti yang terlihat pada potongan pseodocode berikut.

Pseudocode utama:

Pseudocode Merge Sort

Pseudocode Merge Sort

Pseudocode yang dipanggil dari pseudocode utama

Pseudocode Merge Sort

Pseudocode Merge Sort

Dari pseudocode di atas saya mencoba untuk mengimplementasikannya kedalam bahasa pemrograman java. Berikut adalah kode program lengkapnya.

public class MergeSort {
  static int[]data;
  public static void main(String[] args) {
    int []array={2,4,0,8,3,4,5};
    data=array;
    tampil(data);
    int[]wadah=new int[array.length];
    recursiveMergeSort(wadah, 0, data.length-1);
    tampil(data);
  }

  private static void <strong>recursiveMergeSort</strong>(int[]arr,int kiri,int kanan){
    if(kiri<kanan){
      int tengah=(kiri+kanan)/2;
      recursiveMergeSort(arr, kiri, tengah);
      recursiveMergeSort(arr, tengah+1, kanan);
      merge(arr, kiri, tengah+1, kanan);
    }
  }

  private static void <strong>merge</strong>(int[] workSpace, 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 (data[lowPtr] < data[highPtr])
         workSpace[j++] = data[lowPtr++];
      else
         workSpace[j++] = data[highPtr++];

    while (lowPtr <= mid)
      workSpace[j++] = data[lowPtr++];

    while (highPtr <= upperBound)
      workSpace[j++] = data[highPtr++];

    for (j = 0; j < n; j++)
      data[lowerBound + j] = workSpace[j];
  }

  static void tampil(int[]arr){
    for (int i = 0; i < arr.length; i++) {
       System.out.print(arr[i]+" ");
    }
    System.out.println();
  }
}

Keterangan kode program:

  1. Operasi program menggunakan dua array yakni array dengan nama “array” dan “wadah”. Array wadah merupakan array kosong yang digunakan untuk menampung output dari proses sorting.
  2. Mekanisme rekursif terjadi pada method recursiveMergeSort. Method ini selama proses sorting dilakukan proses pemanggilan secara berulang-ulang oleh method itu sendiri.
  3. Kemudian terdapat juga method merge yang digunakan untuk menyatukan kembali elemen-elemen yang telah dibagi menjadi suatu array baru yang terurut.
  4. Terakhir, ada method tampil yang digunakan untuk menampilkan data pada console, baik itu data yang belum terurut maupun yang telah terjadi proses sorting.
  5. Berikut adalah output dari program di atas.
Output Merge sort

Output Merge sort

Untuk dokumen pdf silakan download disini.

One response to “Teknik Divide & Conquer Dalam Algoritma Merge Sort

  1. trojandecoder January 11, 2011 at 4:40 pm

    wah mantap nih ..
    makasih infonya…
    😀

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: