MAKALAH RANCANGAN ANALISA ALGORITMA
ALGORITMA QUICK
SORT
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
No comments:
Post a Comment