Jalani Dan Nikmati Hidup Dengan Senyum Dan Penuh Tanggung Jawab Dan Tetap Mencari Celah Untuk Memperbaiki Kualitas Hidup Yang Lebih Baik Dari Hari Ini Dan Buatlah Hidup Yang Cuma Sekali Ini Bermakna Buatmu Dan Buat Orang Sekitarmu

Sunday, January 13, 2013

Algoritma sorting Merge Sort



Secara   konseptual,  untuk  sebuah array  berukuran  n,
Merge Sort bekerja sebagai berikut:
1.  Jika  bernilai  0   atau   1,   maka  array  sudah   terurut.
2.   Jika Array tidak terurut, bagi menjadi 2 sub-array dengan ukuran n/2
3. Urutkan setiap sub array. Jika sub array tidak cukup kecil lakukan langkah kedua dengan rekursif
4. Menggabungkan sub array menjadi satu array

Ilustrasi Dalam Gambar

implementasi merge sort menggunakan java
 /*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package merge_sort;

import java.util.Arrays;
import javax.swing.JFrame;
import javax.swing.JOptionPane;

/**
 *
 * @author Nur_Hidayat
 */
public class Mergesort {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
     try{
            int jmldata=Integer.parseInt(JOptionPane.showInputDialog("Masukkan Jumlah Data "));
        int []arr=new int[jmldata];
        String ctk=" ";
        for (int i=0;i<jmldata;i++){//melakukan perulangan untuk memunculkan input dialog sesuai jumlah data
            arr[i]=Integer.parseInt(JOptionPane.showInputDialog("Masukkan Data Ke"+(i+1)));
            ctk=ctk+arr[i]+" ";
        }
        JFrame frame=new JFrame();
        JOptionPane.showMessageDialog(frame,"Sebelum Di Urutkan: " + ctk);
        mergeSort(arr);
        JOptionPane.showMessageDialog(frame,"Setelah Di Urutkan: " + Arrays.toString(arr));
        System.exit(0);
        }catch (NumberFormatException ee) {
            JOptionPane.showMessageDialog(null,"Mohon Masukkan Angka");
        }catch (Exception e) {
        JOptionPane.showMessageDialog(null,e);    // TODO code application logic here
    }
}
    public static void mergeSort(int[] array) {
        if (array.length > 1) {
            //membagi array menjadi dua bagian
            int[] left = leftHalf(array);
            int[] right = rightHalf(array);
           
            /** melakukan pemanggilan metod oleh dirinya sendiri (rekursif)
            * untuk membagi array menjadi bagian yang lebih kecil sampai
            * elemen paling kecil
            */
            mergeSort(left);
            mergeSort(right);
           
            // menggabungkan bagian diurutkan menjadi suatu kesatuan yang diurutkan
            merge(array, left, right);
        }
    }
   
    // Mengembalikan bagian pertama dari array yang diberikan.
    public static int[] leftHalf(int[] array) {
        int size1 = array.length / 2;
        int[] left = new int[size1];
        for (int i = 0; i < size1; i++) {
            left[i] = array[i];
        }
        return left;
    }
   
    // Mengembalikan bagian kedua dari array yang diberikan.
    public static int[] rightHalf(int[] array) {
        int size1 = array.length / 2;
        int size2 = array.length - size1;
        int[] right = new int[size2];
        for (int i = 0; i < size2; i++) {
            right[i] = array[i + size1];
        }
        return right;
    }
   
    // membuat array result untuk menampung hasil pengurutan dari array kiri dan kanan
    //jika result kosong maka kanan atau kiri di urutkan
    //result berisi hasil pengurutan array kiri dan kanan
    public static void merge(int[] result,
                             int[] left, int[] right) {
        int i1 = 0;   // index kedalam aray kiri
        int i2 = 0;   // index kedalam aray kanan
       
        for (int i = 0; i < result.length; i++) {
            if (i2 >= right.length || (i1 < left.length &&
                    left[i1] <= right[i2])) {
                result[i] = left[i1];    // ambil dari kiri
                i1++;
            } else {
                result[i] = right[i2];   // ambil dari kanan
                i2++;
            }
        }
    }
}


Untuk mengunduh program bisa anda download Disini