MAKALAH RANCANGAN ANALISA ALGORITMA
ALGORITMA QUICKSORT







OLEH :
150411200128 – IBNUL JAZARI
150411200130 – RENY PUJIASTUTIK
150411200135 – LAKHDAR FIROONI




PROGRAM STUDI TEKNIK INFORMATIKA
FAKULTAS TEKNIK
UNIVERSITAS TRUNOJOYO MADURA
BANGKALAN 2016

KATA PENGANTAR

Alhamdulillahirobbil ‘alamin, segala puji syukur kepada Allah SWT yang telah memberikan rahmat serta hidayahnya sehingga kami dapat meyelesaikan makalah ini untuk memenuhi tugas mata kuliah Rancangan Analisa Algoritma. Shalawat serta salam semoga senantiasa tercurahkan kehadirat Nabi Muhammad SAW, keluarga, sahabat, dan para pengikutnya. Dalam penyusunan makalah Rancangan Analisa Algoritma ini, tidak sedikit hambatan yang kami hadapi. Namun dengan penuh kesabaran dan terutama pertolongan dari Allah SWT akhirnya makalah ini dapat terselesaikan. Tetapi kami mengharap kritik yang kontruktif dari bapak Dosen mata kuliah Rancangan Analisa Algoritma demi penyempurnaan di masa yang akan datang. Semoga makalah Rancangan Analisa Algoritma ini, dapat bermanfaat dan berguna untuk para mahasiswa, atas perhatiannya kami ucapkan terima kasih.


Bangkalan,  Mei 2016
















Kata Pengantar………………………………………..……………………………………i
Daftar Isi………………………………………..……………………………………….....ii
BAB I PENDAHUALUAN………………………………………………………………..1
1. 1.   Latar Belakang…………………………………………………………………....1
1. 2.   Rumusan Masalah ………………………………………………………………..2
1. 3.   Tujuan............................................................... …………………………………..2
BAB II PEMBAHASAN…………………………………………………………………..3
2. 1.   Definisi Quick Sort........................................... …………………………………..3
2. 2.   Algoritma Quick Sort....................................... …………………………………..3
2. 3.   Implementasi Quick Sort Pada Java................. …………………………………..6
BAB III PENUTUP....................................................... …………………………………..8
3. 1.   Kesimpulan ...................................................... …………………………………..8
DAFTAR PUSTAKA..........................................................................................................9
BAB I
PENDAHULUAN
1.1 Latar Belakang
Algoritma adalah kumpulan langkah sistematis untuk memperoleh hasil yang diinginkan. Sebelum sebuah algoritma dijalankan, biasanya ada suatu kondisi awal (initial state) yang harus dipenuhi. Kemudian, langkah-langkah ini diproses hingga mencapai suatu kondisi akhir (final state).
Untuk menyelesaikan suatu masalah, terdapat berbagai algoritma yang dapat digunakan, sesuai dengan salah satu pepatah popular, “Ada banyak jalan menuju  Roma.” Akan tetapi, algoritma manakah yang harus dipilih agar masalah itu dapat diselesaikan dengan efektif? Tentu harus ada parameter yang bisa dibandingkan. Dalam aplikasinya, setiap algoritma memiliki dua buah ciri khas yang dapat digunakan sebagai parameter pembanding, yaitu jumlah proses yang dilakukandan jumlah memori yang digunakan untuk melakukan proses. Jumlah proses inidikenal sebagai kompleksitas waktu yang disimbolkan dengan T(n), sedangkan jumlah memori ini dikenal sebagai kompleksitas ruang yang disimbolkan dengan S(n). Kompleksitas waktu diukur berdasarkan jumlah proses khas suatu algoritma, bukan berdasarkan runtime, secara nyata ketika aplikasi dilakukan. Hal ini disebabkan oleh arsitektur komputer dan kompiler yang berbeda-beda, sehingga suatu algoritma yang sama akan menghasilkan waktu eksekusi yang berbeda, pada komputer dan kompiler yang berbeda.
Pengurutan data (sort)  adalah algoritma yang meletakkan elemen pada sebuah list atau tabel dengan urutan tertentu. Algoritma pengurutan data saat ini telah demikian banyaknya, mulai dari yang sederhana sampai yang kompleks. Sorting didefinisikan sebagai pengurutan sejumlah data berdasarkan nilai kunci tertentu. Pengurutan dapat dilakukan dari nilai terkecil ke nilai terbesar (ascending) atau sebaliknya (descending).Algoritma Sorting termasuk salah satu contoh yang kaya akan solusi.
1.2 Rumusan Masalah
Bertitik tolak dari latar belakang di atas maka rumusan yang dapat penulis ajukan adalah:
1.    Apa pengertian dari Quick Sort ?
2.    Bagaimanakah Algoritma yang bisa diimplementasikan dalam Quick Sort beserta penjelasannya ?
3.    Bagaimana implementasi Algoritma Quick Sort menggunakan bahasa pemprograman Java?

1.3.Tujuan Penulisan
Adapun tujuan penulisan yang dapat diambil dari kelompok kami dari rumusan masalah diatas adalah :
1.    Untuk mengetahui pengertian dari Quick Sort.
2.    Untuk mengetahui bagaimanakah Algoritma yang bisa diimplementasikan dalam Quick Sort beserta penjelasannya.
3.    Untuk mengetahui bagaimana implementasi Algoritma Quick Sort menggunakan bahasa pemprograman Java.

















BAB II
PEMBAHASAN

2.1 Definisi Quick Sort
Quick Sort adalah algoritma pengurutan yang sangat cepat dengan tipe penyelesaian Divide and Conquer sehingga cocok untuk mengurutkan data dalam jumlah besar. Algoritma Quick Sort merupakan algoritma sorting yang diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1960. Pada keadaan rata – rata membuat pengurutan O( n log n) untuk mengurutkan n item. Pada kasus terburuknya, algoritma ini membuat pengurutan O(n2).

2.2 Algoritma Quick Sort
Algoritma Quick Sort ini terdapat tiga bagian yaitu low, high, dan pivot. Low adalah batas bawah atau index awal sebuah array, sedangkan high adalah batas akhir atau index terakhir array tersebut, dan pivot sebagai index acuan.pada array normal yang belum dipecah, nilai lownya adalah 0 (nol) karena array dimulai dari index ke-0. Sedangkan untuk high, nilainya array.length-1. Adapun algoritma quick sort adalah seperti dibawah ini :
QuickSort(A, low, high)
     if   low < high
          p = Partition (A, low, high)
          QuickSort(A, low, p-1)
          QuickSort(A, p+1, high)
Pada algoritma quick sort diatas terdapat dua metod, yang pertama metod Quick Sort itu sendiri yang bersifat rekursif dan metod Partition yang digunakan untuk mengetahui penanda sehingga data tersebut terpecah menjadi dua. Algoritma dijalankan selama nilai low kurang dari high, apabila nilai low sama dengan nilai high, artinya jumlah elemen array hanya ada satu. Variabel p digunakan untuk menampung nilai pivot yang digunakan untuk acuan pemecahan array. Sebelum dipecah menjadi dua, array tersebut dipartisi dulu untuk menentukan index pivot. Setelah diketahui index keberapa yang menjadi pivot maka array terpecah menjadi dua. Pada array pertama bagian kiri, nilai lownya tetap nol dan nilai highnya pivot-1. Sedangkan pada array sisi kanan, nilai lownya adalah pivot+1 dan highnya array.length-1.

Adapun metode Partition adalah sebagai berikut :
Partition(A, low, high)
     pivot = A[high]
     i = low
     for j = low to high-1
          if A[ j ]  ≤  pivot
            i = i+1
            exchange A[ i ] with A[ j ]
     exchange A[ i ] with A[ high ]
     return i
Sebagai contoh, terdapat sebuah array A dengan nilai acak {39, 99, 19, 9, 12, 10, 33}. Maka nilai low = 0, high = 6 (nilai A.length-1). Karena nilai low kurang dari high, yang artinya jumlah elemen array A lebih dari satu, maka dilakukan partisi. Pada metod partisi, nilai pivot adalah 33 dan i berada pada index ke-0 yaitu nilai 39.
39
99
19
9
12
10
33
i





pivot
Selama perulangan dari 0 sampai 5, artinya selama dari index ke-0 hingga ke-5 akan melakukan perulangan. Pada perulangan pertama, nilai j = 0. Nilai A[ 0 ] = 39. Karena 39 tidak kurang dari 33 (pivot) maka posisi i tidak bergeser, tetap pada index ke-0 dan tidak dilakukan pertukaran antara A[0] dengan A[0].
39
99
19
9
12
10
33
i





pivot
Pada perulangan kedua, nilai j = 1. Nilai A[ 1 ] = 99. Karena 99 tidak kurang dari 33 (pivot) maka posisi i tidak bergeser, tetap pada index ke-1 dan tidak dilakukan pertukaran A[0] dengan A[1].

39
99
19
9
12
10
33
i





pivot
Pada perulangan ketiga, nilai j = 2. Nilai A[ 2 ] = 19. Karena 19 kurang dari 33 (pivot) maka posisi i bergeser pada index ke-1, dan dilakukan pertukaran antara A[0] dengan A[2].
19
99
39
9
12
10
33

i




pivot
Pada perulangan keempat, nilai j = 3. Nilai A[ 3 ] = 9. Karena 9 kurang dari 33 (pivot) maka posisi i bergeser pada index ke-2, dan dilakukan pertukaran antara A[1] dengan A[3].
19
9
39
99
12
10
33


i



pivot
Pada perulangan kelima, nilai j = 4. Nilai A[ 4 ] = 12. Karena 12 kurang dari 33 (pivot) maka posisi i bergeser pada index ke-3, dan dilakukan pertukaran antara A[2] dengan A[4].
19
9
12
99
39
10
33



i


pivot
Pada perulangan keenam, nilai j = 5. Nilai A[ 5 ] = 10. Karena 10 kurang dari 33 (pivot) maka posisi i bergeser pada index ke-4, dan dilakukan pertukaran antara A[3] dengan A[5].
19
9
12
10
39
99
33




i

pivot
Perulangan for berhenti karena kondisinya sudah tidak sesuai. Kemudian nilai A[i] = 39 ditukar dengan nilai A[high] = 33 dengan posisi i tetap.
19
9
12
10
33
99
39




i

pivot
Dari sini kembali lagi pada metod QuickSort dengan nilai p sama dengan nilai kembalian Partition, sehingga nilai p adalah 4. Selanjutnya memecah array menjadi dua bagian dan meamnggil metode quicksort dan partition lagi. Pada array sebelah kiri, nilai low = 0 dan high = 3 sedangkan pada array sisi kanan nilai low = 5 dan high = 6.

Kiri



Kanan
19
9
12
10

33

99
39
i


pivot



i
pivot
Posisi p (nilai 33) sudah ideal namun pada sisi kiri dan kanan masih belum sesuai, maka perlu di lakukan quick sort lagi. Proses dari quick sort sebagai berikut :
Kiri



Kanan
19
9
12
10

33

99
39
i


pivot



i
pivot
Pada sisi kanan yang hanya terdapat dua elemen array, nilai i lebih besar dari nilai pivot maka posisi i tetap dan tidak ditukar pada perulangan for. Namun ditukar antar A[i] dengan A[high] karena jumlah panjang arraynya hanya dua.
Kiri



Kanan
9
19
12
10

33

39
99

i

pivot





Namun pada sisi kiri masih perlu di seleksi menggunakan perulangan for seperti langkah sebelumnya. Karena 12 lebih besar dari pivot maka perulanagn berhenti dan nilai i ditukar dengan nilai high. Adapun gambarannya sebagai berikut :
Kiri



Kanan
9
10
12
19

33

39
99

i

pivot




Dari array kiri diatas array seharusnya dipecah lagi sesuai dengan posisi i. Tetapi karena di sebelah kiri indeks i hanya satu elemen maka tidak perlu dilakukan pemanggilan quicksort. Sedangkan pada sisi kanan hanya terdapat dua elemen yang sudah sesuai. Maka tampilan outputnya adalah :
9
10

12
19

33

39
99









2.3 Implementasi Quick Sort Pada Java
Implementasi algoritma Quick Sort pada java :

package Sorting;

public class QuickSort {
    public static int i,p,pivot;
    public static void main(String[] args) {
        int A [] = {39,99,19,9,12,10,33};
        System.out.print("Array A = ");
        for (int z = 0; z < A.length; z++) {
         System.out.print(A[z]+"   ");
        }
        System.out.println();
        
        QuickSort(A, 0, A.length-1);
        System.out.println("\nSetelah diurutkan : ");
        for (int z = 0; z < A.length; z++) {
            System.out.print(A[z]+"   ");
            }
            System.out.println();
    }
   
    public static void QuickSort(int []A, int lo,int hi){
        if (lo < hi){
            p = partition(A,lo,hi);
            QuickSort(A, lo, p-1);
            QuickSort(A, p+1, hi);
          
        }
    }
   
    public static int partition(int [] A, int lo, int hi){
        pivot = A[hi];
        i = lo;
        int j;
        for (j = lo; j <= hi-1; j++){
            if (A[j] <= pivot){
                int temp = A[i];
                A[i] = A[j];
                A[j] = temp;
                i = i+1;
            }
        }
        int tp = A[i];
        A[i] = A[hi];
        A[hi] = tp;
        return i;
        
    }
}

Hasil Running:

BAB III

PENUTUP

3.1 Kesimpulan:
·         Quick sort adalah algoritma sorting yang berdasarkan pembandingan dengan metode divide-and-conqueror. Algoritma quick sort mengurutkan dengan sangat cepat, namun algoritma ini sangat komplex dan diproses secara rekursif.
·         Algoritma quick sort dibedakan menjadi rekursif dan non rekursif.
·         Dalam algoritma quick sort, pemilihan pivot adalah hal yang menentukan apakah algoritma quick sort tersebut akan memberikan performa terbaik atau terburuk.
·         Kebutuhan waktu dari quicksort bergantung pada pembuatan partisi, seimbang atau tidak, yang bergantung juga pada elemen yang digunakan sebagai pivot. Terdapat 3 jenis kompleksitas waktu dari quicksort kasus terburuk (worst case) Tn=O(n2), kasus terbaik (best case) Tn= O(n log n), kasus rata-rata (average case).















DAFTAR PUSTAKA

http://dtugasalgoritma.blogspot.co.id/2010/12/quick-sort-algoritma.html?m=1 Diakses tanggal 17 Mei 2016
http://dinda-dinho.blogspot.co.id/2013/07/sorting-dengan-metode-quick-sort.html?m=1 Diakses tanggal 17 Mei 2016