03 October 2017

METODA MERGE SORT (TWO-WAY MERGE SORT)

Metoda merge sort juga disebut two way merge sort. Langkah-langkah pengurutan dengan merge sort secara garis besar dapat dijelaskan sebagai berikut.
Andaikan terdapat sebuah vektor K dengan cacah elemen data sebanyak N dalam kondisi tidak terurut. Untuk mengurutkan semua data-data dalam K, mula-mula setiap elemen dalam vektor K dianggap sebagai sebuah vektor yang masing-masing mempunyai sebuah elemen data. Dengan demikian akan terdapat N vektor dengan cacah elemen masing-masing adalah 1 buah. Selanjutnya setiap pasang vektor yang beruntun kita gabungkan menjadi sebuah vektor baru. Jika kita menginginkan hasil secara urut naik, maka pada saat menggabungkan kedua vektor tersebut sekaligus dilakukan perbandingan dan pertuaran posisi antar elemen data sedemikian rupa sehingga data yang lebih kecil akan akan ditempatkan pada posisi yang mendahului data lain yang lebih besar. Pada akhir langkah pertama ini, kita akan memiliki vektor baru sebanyak N/2 yang masing-masing dalam kondisi urut naik. Cacah elemen pada masing-masing vektor adalah 2 buah, kecuali jika N bernilai ganjil maka akan terdapat N/2+1 vektor baru dimana salah satu vektor hanya memiliki sbuah elemen data.
Pada langkah selanjutnya, setiap pasang vektor yang beruntun  dilakukan penggabungan dan sekaligus dapat pertukaran posisi antar data sehingga akan terbentuk vektor-vektor baru. Demikian proses penggabungan dan pertukaran posisi data secara terus menerus akan dilakukan sehingga pada akhirnya akan diperoleh sebuah vektor baru yang memuat semua elemen data dalam vektor sumber dalam kondisi urut naik.
Sebagai ilustrasi untuk memperjelas proses pengurutan dalam metoda merge sort, maka berikut ini akan diberikan contoh penenrapannya. Diketahui sebuah vektor yang akan diurutkan secara urut naik, yaitu K yang memiliki delapan elemen data sebagai berikut.

Contoh :
87    74    71    100    75    25    56    90

Ilustrasi proses pengurutan vektor K dengan metode merge sort secara ringkas adalah ditunjukan oleh gambar dibawah ini.



Contoh ilustrasi pengurutan data dengan metoda merge sort.

Dalam contoh diatas, mula-mula vektor K akan dipecah menjadi vektor-vektor  baru yang masing-masing memiliki satu elemen data sehingga akan terdapat delapan vektor.
1. Pada langkah pertama, setiap pasang vektor yang berurutan akan digabungkan dan sekaligus dibandingkan untuk menempatkan data yang lebih kecil pada lokasi yang lebih awal. Dalam contoh diatas 87 akan digabungkan dengan 74, 71 dengan 100, 75 dengan 25, dan 56 dengan 90.
2. Pada langkah kedua akan menghasilkan empat vektor baru yang masing-masing telah diurut.
3. Pada Langkah ketiga akan menggabungkan kembali sekaligus mengatur lokasi setiap data yang digabungkan tersebut sehingga akhirnya akan menghasilkan 2 vektor baru.
4. Pada langkah terakhir, yaitu langkah keempat maka dua vektor hasil peggabungan pada langkah ketiga akan digabungkan dan diatur kembali.
Dari ilustrasi diatas terlihat bahwa untuk mengurutkan vektor KK yang memiliki  delapan elemen data akan memerlukan 3 langkah penggabungan dimana masing-masing langkah terdiri dari beberapa proses perbandingan dan pertukaran lokasi elemen data. Selanjutnya, untuk menuliskan solusi bentuk algoritma prosedur pengurutan data secara urut naik dengan metoda merge sort akan digunakan beberapa variable I,J,Kdan L adalah sebagai pencacah pada proses perulangan. Variabel N adalah menunjukan cacah elemen vektor sumber KK. Variable ITERASI menyatakan banyaknya langkah yang harus dilakukan untuk mengurutkan data. SUB  ITERASI adalah variable untuk menentukan banyaknya SUB Iterasi pada setiap Iterasi. Variabel UKURAN menunjukan cacah elemen vektor pada iterasi yang bersesuaian.sedangkan R,S,dan T adalah variabel-variabel yang akan digunakan sebagai pencacah. Untuk memperoleh vektor yang urut maka cacah Iterasi yang harus dilakukan adalah sebanyak M dimana sama dengan log2N. Algoritma prosedur pengurutan data dengan metode merge sort dapat dituliskan sebagai berikut ini :
Masukan vektor K yang memuat N buah data yang akan diurutkan KK adalah vektor hasil dalam kondisi urut naik.
1. Mulai
2. Proses berulang langkah-3 sampai dengan langkah-8
FOR ITERASI=1 TO M
3.Inisialisasikan  untuk iterasi
UKURAN =2…(ITERASI-1)
P=1
Q=P+UKURAN
SUB ITERASI=N/(2xITERASI)
4. Proses berulang langkah-5 s/d langkah-8 untuk setiap iterasi
FOR S=1 TO SUB ITERASI
5. Inisialisasi prosedur simple merge
I=P
J=Q
T=P
6. Proses memang berulang untuk membandingkan antar data dan menemukan  elemen
   terkecil
WHILE((1+1-P<=UKURAN)AND(J+1-Q<=UKURAN))
IF ITERASI=”GANJIL”
Jika ya,IF K[I]<=K[J]
Jika ya,tentukan KK[T]=K[I]
I=I+1
T=T+1
Jika tidak,tentukan KK[T]=K[J]
J=J+1
T=T+1
Jika tidak,IF KK[I]<=KK[J]
Jika ya,tentukan K[T]=KK[I]
I=I+1
T=T+1
Jika tidak,tentukan K[T]=KK[J]
J=J+1
T=T+1
7. Copykan sisa elemen data yang tidak terproses dari vektor sumber ke vektor
hasil
IF I+1-P>UKURAN
Jika ya,IF ITERASI=”GANJIL”
Jika ya,lakukan proses berulang
FOR R=J TO Q+UKURAN -1
KK[T]=K[R]
T=T+1
Jika tidak,IF ITERASI=”GANJIL”
Jika ya,lakukan proses berulang
FOR R=1 TO P +UKURAN -1
KK[I]=K[R]
T=T+1
JIka tidak,lakukan proses berulang
FOR R=1 TO P+UKURAN -1
K[T]=KK[R]
T=T+1
8. Perbaharui indikasi vektor
P=Q+UKURAN
Q=P+UKURAN
9. Copykan ulang jika diperlukan
IF M=”GANJIL”
Jika ya, lakukan proses berulang
FOR I=1 TO N
K[I]=KK[I]
10. Cetak hasil
11. Selesai
Contoh lain dari merge sort (two way merging) secara mendasar.

1. Bagi urutan urutan menjadi dua bagian dengan panjang n/2 dan n/2.
2. Mengurutkan berulang pada setiap 2 urutan, dan
3. Gabungkan urutan yang diurut hingga mencapai hasil akhir

Pengurutan dengan merge sort adalah perulangan, pambagian dan penggabungan. Dasarnya, kita mempunyai urutan dengan satu elemen pasti didalamnya. Ketika urutan sudah diurutkan, tidak perlu diurutkan lagi. Pengurutannya yaitu dengan n>1 elemen .

01 October 2017

MENGHITUNG DURASI - PEMOGRAMAN JAVA

Soal :
Buatlah suatu program untuk menghitung durasi dengan menggunakan konsep pemograman berorientasi objek. Waktu awal dan waktu akhir diinputkan dari keyboard.

Jawab :
Kasus yang diambil adalah Perhitungan harga sewa mobil dengan durasi waktu tertentu.
Aplikasi dibuat dengan 2 class

SewaMobil.java
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package uts;

/**
 *
 * @author Agus Sofyan Hidayat
 */
public class SewaMobil {
    private String str_waktu_awal,str_waktu_akhir;
    private int jam_awal,jam_akhir,menit_awal,menit_akhir,detik_awal,detik_akhir;
    private int jam,menit,detik;
    private int hargasewa;
    private double total_selisih;
    
    public void TampilWaktu(String str_jam_awal, String str_menit_awal, String str_detik_awal, String str_jam_akhir,
            String str_menit_akhir, String str_detik_akhir) {
        //  Tampilkan Waktu Awal dan Waktu Akhir
        str_waktu_awal = str_jam_awal+":"+str_menit_awal+":"+str_detik_awal;
        str_waktu_akhir = str_jam_akhir+":"+str_menit_akhir+":"+str_detik_akhir;
        System.out.println("Waktu Awal  : "+str_waktu_awal);
        System.out.println("Waktu Akhir : "+str_waktu_akhir);
    }
    
    public void KonversiData(String str_jam_awal, String str_menit_awal, String str_detik_awal, String str_jam_akhir,
            String str_menit_akhir, String str_detik_akhir, String str_sewa) {
        //  Konversi variable str menjadi integer
         jam_awal = Integer.parseInt(str_jam_awal);
         jam_akhir = Integer.parseInt(str_jam_akhir);
         menit_awal = Integer.parseInt(str_menit_awal);
         menit_akhir = Integer.parseInt(str_menit_akhir);
         detik_awal = Integer.parseInt(str_detik_awal);
         detik_akhir = Integer.parseInt(str_detik_akhir);
         
         hargasewa = Integer.parseInt(str_sewa);
    }
    
    public void SelisihWaktu() {
        //  Proses pencarian selisih Waktu Awal dan Waktu Akhir
        //  Langkah Ketiga, cari selisih detik awal dan detik akhir     
        int selisih_detik = 0;
         
        //  Jika detik awal > detik akhir
        //  Contohnya, detik awal = 40 dan detik akhir = 30
        if(detik_awal > detik_akhir) {
             
            while(detik_awal != detik_akhir) {
                 
                if(detik_awal == 60) {
                    detik_awal = 0;
                    menit_awal++;
                        continue;
                }
                detik_awal++;
                selisih_detik++;
            }
        }
         
        //  Jika detik awal < detik akhir
        //  Contohnya, detik awal = 30 dan detik akhir = 40
        else if(detik_awal < detik_akhir) {
            selisih_detik = detik_akhir - detik_awal;
        }
         
        //  Masukkan ke variable selisih waktu
        int selisih_waktu = selisih_detik;
         
        //-------------------------------------------------------
        //  Langkah Kedua, cari selisih menit awal dan menit akhir      
        int selisih_menit = 0;
         
        //  Jika menit awal > menit akhir.
        //  Contohnya, menit awal = 50 dan menit akhir = 10
        if(menit_awal > menit_akhir) {
             
            while(menit_awal != menit_akhir) {
                 
                if(menit_awal == 60) {
                    menit_awal = 0;
                    jam_awal++;
                        continue;
                }
                 
                menit_awal++;
                selisih_menit++;
            }
        }
         
        //  Jika menit awal < menit akhir
        //  Contohnya, menit awal = 10 dan menit akhir = 50
        else if(menit_awal < menit_akhir) {
            selisih_menit = menit_akhir - menit_awal;          
        }
         
        //  Ubah selisih menit menjadi satuan detik (1 menit = 60 detik)
        selisih_waktu += selisih_menit * 60;
         
        //  Langkah Pertama, cari selisih jam awal dan jam akhir        
        int selisih_jam = 0;
         
        //  Jika jam awal > jam akhir. Contohnya, Jam Awal = 22 (10 malam) dan Jam Akhir = 05 (5 pagi)
        if(jam_awal > jam_akhir) {
             
            //  Cocokkan antara jam awal dan jam akhir
            while(jam_awal != jam_akhir) {
                if(jam_awal == 24) {                
                    jam_awal = 0;
                    continue;
                }
                 
                jam_awal++;
                selisih_jam++;
            }
        }
         
        //  Jika jam awal < jam akhir. Contohnya, Jam Awal = 05 (5 pagi) dan Jam Akhir = 22 (10 malam)
        else if(jam_awal < jam_akhir)
            selisih_jam = jam_akhir - jam_awal;
         
        //  Ubah selisih jam menjadi satuan detik (1 jam = 3600 detik)
        selisih_waktu += selisih_jam * 3600;

        total_selisih= selisih_waktu;
        //  Tampilkan selisih antara waktu awal dan waktu akkhir dalam satuan detik
        System.out.println("Selisih antara waktu awal dan waktu akhir (detik) : "+total_selisih);
         
        //  Ubah selisih_waktu menjadi format waktu HH:mm:ss
        //  Ubah selisih waktu menjadi satuan jam
        jam = selisih_waktu / 3600;
        selisih_waktu %= 3600;
         
        //  Ubah selisih waktu menjadi satuan menit
        menit = 0;
        detik = 0;
        
        if(selisih_waktu >= 60) {
            menit = selisih_waktu / 60;
            detik = selisih_waktu % 60;
             
        } else {
            menit = 0;
            detik = selisih_waktu;
        }
         
        //  Tampilkan selisih antara waktu awal dan waktu akhir dalam format waktu HH:mm:ss
        String waktu = jam+":"+menit+":"+detik;
        System.out.println("Selisih antara waktu awal dan waktu akhir (HH:mm:ss) : "+waktu);
    }
    
    public double BiayaSewaMobil(){
        double Sewa;
        double TotalBiaya;
        
        Sewa=total_selisih/3600;
        
        TotalBiaya=Sewa*hargasewa;
        
        return TotalBiaya;
        
    }
}

DurasiWaktu.java
package uts;

import java.util.Scanner;
import java.text.DecimalFormat;
import java.text.DecimalFormatSymbols;
/**
 *
 *  @author Agus Sofyan Hidayat
 *  Kasus menentukan jumlah biaya untuk sewa mobil di tempat Rental A
 */

public class DurasiWaktu {
    public static void main(String[] args) {
        //Class SewaMobil
        SewaMobil sewa=new SewaMobil();
        
        //Format Desimal
        DecimalFormat kursIndonesia = (DecimalFormat) DecimalFormat.getCurrencyInstance();
        DecimalFormatSymbols formatRp = new DecimalFormatSymbols();

        formatRp.setCurrencySymbol("Rp. ");
        formatRp.setMonetaryDecimalSeparator(',');
        formatRp.setGroupingSeparator('.');

        kursIndonesia.setDecimalFormatSymbols(formatRp);
        
        
        //  Scanner
        Scanner scan = new Scanner(System.in);
        
        System.out.println("PENYEWAAN MOBIL RENTAL A");
        //  Input Waktu Awal
        System.out.println("Waktu Awal");
        System.out.print("Input Jam   : ");     String str_jam_awal = scan.nextLine();
        System.out.print("Input Menit : ");     String str_menit_awal = scan.nextLine();
        System.out.print("Input Detik : ");     String str_detik_awal = scan.nextLine();
         
        //  Input Waktu Akhir
        System.out.println("\nWaktu Akhir");
        System.out.print("Input Jam   : ");     String str_jam_akhir = scan.nextLine();
        System.out.print("Input Menit : ");     String str_menit_akhir = scan.nextLine();
        System.out.print("Input Detik : ");     String str_detik_akhir = scan.nextLine();
        
        System.out.println("\nPenyewaan Perjam");
        System.out.print("Harga Sewa   : Rp");     String str_sewa = scan.nextLine();
         
        //Tampil waktu
        sewa.TampilWaktu(str_jam_awal, str_menit_awal, str_detik_awal, str_jam_akhir, str_menit_akhir, str_detik_akhir);
        
        sewa.KonversiData(str_jam_awal, str_menit_awal, str_detik_awal, str_jam_akhir, str_menit_akhir, str_detik_akhir, str_sewa);
        
        sewa.SelisihWaktu();
        
        System.out.println("\nTotal Biaya yang harus dibayarkan penyewa : "+kursIndonesia.format(sewa.BiayaSewaMobil()));
        
    }
}


Tampilan Aplikasi

1. Proses input waktu awal, waktu akhir dan harga sewa per jam

  
2. Hasil proses perhitungan harga sewa