Komparasi Algoritma Quicksort dan Bucket Sort pada Pengurutan Data Integer Dengan Menggunakan Bahasa Pemrograman Java, C++ dan VB.net
Afri Yudha (14002005) Program Pascasarjana Magister Ilmu Komputer,STMIK Nusa Mandiri Jl.Kramat No.18. Senen, Jakarta Pusat 10420 Email :
[email protected]
Abstrak Pengurutan data sangat sering dilakukan dalam dunia komputasi. Keperluan-keperluan yang membutuhkan pengurutan data begitu banyak, sehingga perlu dicari metode pengurutan data yang dapat bekerja secara cepat dan efisien, Quicksort dan Bucket Sort adalah salah satunya. pengujian dengan pengurutan algortitma Quick Sort yang menggunakan metode rekursif dan Algoritma Bucket Sort yang menggunakan Bucket/ember dalam menyimpan pengurutan nya. Paper ini ingin menunjukkan perbandingan kecepatan waktu yang didapat, dari pengurutan Algoritma Quicksort dan Algoritma Bucket Sort menggunakan bahasa pemrograman Java, C++ dan Vb.Net, yang dimana dari hasil pengujian yang dilakukan, Algoritma Quicksort lebih unggul dibanding Agoritma Bucket Sort dari data random 1 sampai 5000 dengan angka yang dikeluarkan sebanyak 4200 data. Key word : Algoritma, Sorting, Quicksort, Bucket Sort, C++, Vb.Net, Java 1. Pendahuluan 1.1 Latar Belakang Masalah Pengurutan data atau sorting merupakan salah satu jenis operasi penting dalam pengelolaan data. Didalam buku Reference model for an Open archival Information System (OAIS)[2], data adalah suatu hal yang dapat diterjemahkan dan direpresentasikan ke dalam bentuk formal agar dapat digunakan untuk komunikasi, intrepretasi, atau pengelolaan informasi.
Banyaknya Penelitian mengenai perbandingan kecepatan antara algoritma Quicksort dan Bucket sort, seperti yang dilakukan oleh Audy dalam jurnalnya (Komparasi Algoritma Quicksort dan Bucket Sort dengan Pengurutan Data integer (2015))[1] dengan menggunakan bahasa pemrograman Vb.NET yang menggunakan 4000 data integer secara random, dia mengatakan bahwa algoritma Bucket Sort lebih cepat dalam mengurutkan data
dengan perbandingan hampir 37 kali dibandingkan dengan algoritma Quicksort. Senada dengan pendapat audi diatas, Mira Kusmira dalam jurnalnya (Komparasi Algoritma Quicksort dan Bucket Sort dengan Pengurutan Data integer dengan menggunakan bahasa pemrograman C++ (2016))[8], Mira mengatakan bahwa Algoritma Bucket Sort lebih cepat dibandingkan dengan algoritma Quicksort, dimana yang digunakan 10 data integer, dan dalam perbandingan tersebut didapat waktu pengujian untuk Algoritma Quicksort 8.669 second dan Algoritma Bucket Sort 7,828 second. Sebelumnya penulis telah melakukan pengujian pada algoritma Quicksort dan Bucket sort dengan bahasa pemrograman Java, dimana data integer yang digunakan 10, dengan hasil pengujian, algoritma Quicksort lebih cepat dibandingkan Bucket Sort, waktu yang didapatkan adalah 7.186 second untuk algoritma Quicksort dan 8.213 second untuk algoritma Bucket Sort. Dengan adanya perbedaan hasil perbandingan yang didapatkan, maka penulis akan melakukan pengujian kembali dengan menggunakan bahasa pemrograman Java, Vb.NET, C++ dengan data yang digunakan 5000 yang akan dibuat random. 2. Landasan Teori 2.1 Pengertian Algoritma Algoritma pada dasarnya adalah alur pikiran dalam menyelasaikan suatu pekerjaan yang dituangkan dalam bentuk tertulis yang dapat dimengerti orang lain. Algoritma adalah sekumpulan intruksi yang jumlahnya terbatas yang apabila dijalankan akan menyelesaikan suatu tugas tertentu. Menurut Rosen (202) [9] algoritma adalah sebuah urutan intruksi yang terbatas untuk
melakukan komputasi atau untuk menyelesaikan suatu masalah, yang dimasksud dengan kalimat “urutan instruksi yang terbatas” menggambarkan bahwa ada suatu nilai akhir atau output yang dihasilkan oleh algoritma. 2.2 Pengertian Pengurutan Data (Sorting) Sorting adalah proses pengurutan data yang sebelumnya disusun secara acak atau tidak teratur menjadi urut dan teratur menurut suatu aturan tertentu. Sadgewick & Wayne (2011)[10] mengatakan, 30% pekerjaan yang dilakukan oleh computer berhubungan dengan proses pengurutan data. Angka 30% ini begitu besar karena pada penggunaan komputer sehari-hari hampir setiap operasi yang dilakukan oleh pengguna melibatkan proses pengurutan data. Ketika pengguna membuka Windows Explorer, misalnya berkas yang ditampilkan di layar langsung terurut berdasarkan jenisnya (berkas atau folder), kemudian terurut secara sekumpulan tweets yang terurut berdasarkan waktu penulisan atau nama foldernya. Cormen, et al.,(2009)[4] mengatakan pengurutan data merupakan salah satu masalah fundamental dalam suatu algoritma, dengan alasan-alasan : Ada program-program komputer yang memang memerlukan proses pengurutan data secara explisit karena businesss processnya mengharuskan demikian. Pengurutan data memegang peranan penting dalam beberapa jenis algoritma. Contohnya, perangkat lunak yang melakukan proses graphic rendering yang memiliki beberapa layer perlu
melakukan pengurutan layerlayer tersebut, sehingga rendering akan dilakukan dari layer terbawah hingga teratas. Beberapa teknik pemrograman dan ide pemecahan masalah, baru ditemukan ketika algoritma pengurutan data dikembangkan. Analisa suatu algoritma pengurutan data dapat dilakukan hingga muncul kesimpulan apakah algoritma pengurutan data ini optimal, baik dalam kasus terburuk maupun dalam kasus terbaik. Banyak isu yang muncul ketika implementasi suatu perangkat lunak dapat diselesaikan dengan analisa mendalam pada level desain, bukan memperbaiki kode program pada level implememtasi.
Beberapa algoritma pengurutan data yang dikenal dalam dunia komputasi adalah insertion sort, merge sort, heap sort, quick sort, counting sort, radix sort dan bucket sort. Salah satu alasan utama kenapa pengurutan data begitu penting dan sering digunakan dalam dunia komputasi adalah karena mencari data dalam sekelompok data terurut lebih mudah daripada mencari data dari sekolompok data yang tidak terurut. Sebagai contoh, buku kuning Yellow Pages yang beredar luas pada tahun 2000an menampilkan daftar nomor telepon terurut berdasarkan nama sehingga pengguna buku dapat mencari nama yang ingin dihubungi dengan cepat. Di era komputasi modern, sebagian kecil implementasi pengurutan data yang ditemukan dalam kehidupan sehari-hari
adalah aplikasi pemutar musik mengurutkan daftar lagu berdasarkan album atau penyanyinya, mesin pencari menampilkan hasil pencarian terurut berdasarkan relevansi dengan kata kunci yang diberikan, aplikasi spreadsheet menampilkan data terurut berdasarkan kolom tertentu, dan masih banyak lagi implementasi pengurutan data yang ditemukan sehari-hari. Keperluan lain pun menjadi lebih mudah dilakukan jika sekolompok data yang digunakan sudah dalam kondisi terurut, misalnya mencari kata kunci tertentu dari suatu index di bagian belakang buku, menghapus data ganda dari suatu daftar website atau mailing list, atau komputasi statistic seperti mencari nilai median atau menghitung persentil. Pengurutan data juga digunakan dalam kasus-kasus penting yang kelihatannya tidak berkaitan dengan pengurutan data. Contohnya, kompresi data proses render grafis , komputasi biologi, atau voting dalam pemilihan opsi tertentu. Biasanya pengurutan data terbagi menjadi dua yaitu ascending dan descending dimana ascending adalah pengurutan data atau karakter dari yang terkecil sampai yang terbesar, sedangkan descending sendiri adalah pengurutan data atau karakter dari yang terbesar ke yang terkecil. 2.2.1 Algoritma Quick Sort Algoritma Quicksort diperkenalkan pertama kali oleh C.A.R Hoare pada tahun 1960 dan dimuat sebagai artikel di “Computer Journal 5” pada April 1962[3]. Quicksort adalah sorting yang berdasarkan perbandingan dengan metode divide-andconqueror. Divide-and-conqueror meyelesaikan masalah menggunakan metode rekursif.
Menurut Cormen, et al., 2009 ada tiga hal yang dilakukan oleh divide-and-conqueror : 1. Membagi (divide) permasalahan yang dihadapi kedalam beberapa subproblems yang lebih kecil. Namun masih mengandung masalah yang sama. 2. Menyelesaikan (conquer) subproblems secara rekursif. Jika ukuran sub-problems sudah cukup. 3. diselesaikan, maka lakukan penyelesaian masalah. 4. Gabungkan (combine) solusi untuk sub-problems yang ada untuk mendapatkan solusi global. Khreisat (2007) menyatakan algoritma Quicksort ini merupakan metode pengurutan data yang paling efisien dibandingkan dengan metode yang lain. Sejak dipublikasikan oleh Hoare pada tahun 1960, banyak orang yang mempelajari dan berusaha mengembangkan Quicksort. Tidak semua ide-ide perbaikan Quicksort berjalan dengan baik , karena algoritma Quicksort ciptaan Hoare cukup stabil sehingga improvisasi yang kurang baik justru dapat menganggu stabilitas algoritma itu sendiri (sadgewick & Wayne 2011). Namun beberapa ide-ide perbaikan Quicksort yang terpublikasi cukup berhasil dalam meningkatkan performa Quicksort sekaligus “Memuaskan” para akademisi secara kognitif. Karena Quicksort begitu luas dipakai di berbagai bidang komputasi, maka para ilmuwan memandang penting untuk selalu melakukan improvisasi dengan algoritma ini. Robert Sadgewick (1978) dari Princeton university kemudian focus mempelajari, menganalisa dan memperbaiki Quicksort
dalam tesis dan penelitian-penelitiannya (khreisat 2007). 78
17
39
26
72
94
21
12
23
68
78
17
39
26
72
94
21
12
23
68
17
39
26
72
78
94
21
12
23
68
12
17
39
26
72
78
94
21
23
68
12
17
21
39
26
72
78
94
23
68
12
17
21
23
39
26
72
78
94
68
12
17
21
23
26
39
72
78
94
68
12
17
21
23
26
39
68
72
78
94
Gambar 1 : Contoh Penerapan Algoritma Quicksort
2.2.1.1 Pseudocode Pseudocode Adalah sebuah kode yang digunakan untuk menulis sebuah algoritma dengan cara yang bebas yang tidak terikat dengan bahasa pemrograman tertentu. Atau bisa juga disebut bahasa yang digunakan untuk menyederhanakan penulisan algoritma. Pseudocode dari algoritma Quicksort dengan pendekatan rekursif dan menggunakan bahasa pemrograman java adalah sebagai berikut :
public static void quickSort(int[] arr, int low, int high) { if (arr == null || arr.length == 0) return; if (low >= high)
return; // pick the pivot int middle = low + (high - low) / 2; int pivot = arr[middle]; // make left < pivot and right > pivot int i = low, j = high; while (i <= j) { while (arr[i] < pivot) { i++; } while (arr[j] > pivot) { j--; } if (i <= j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } // recursively sort two sub parts if (low < j) quickSort(arr, low, j); if (high > i) quickSort(arr, i, high); } }
Sedangkan pseudocode quicksort dengan menggunakan bahasa pemrograman C++ void quickSort(T *array, size_t left, size_t right{ size_t l = left; size_t r = right - 1; size_t size = right - left;
if (size > 1) { T pivot = array[rand() % size + l]; while (l < r) { while (array[r] > pivot && r > l) { r--; } while (array[l] < pivot && l <= r) { l++; } if (l < r) { std::swap(array[l], array[r]); l++; } } quickSort(array, left, l); quickSort(array, r, right) } }
Dan pseudocode quicksort dengan bahasa pemrograman Vb.Net Public Sub Quicksort(ByVal lis() As Integer, ByVal min As Integer, ByVal max As Integer) Dim random_number As New Random Dim med_value As Integer Dim hi As Integer Dim lo As Integer Dim i As Integer If min >= max Then Exit Sub i = random_number.Next(min, max + 1) med_value = lis(i) lis(i) = lis(min) lo = min hi = max Do Do While lis(hi) >= med_value hi = hi - 1 If hi <= lo Then Exit Do Loop If hi <= lo Then lis(lo) = med_value Exit Do End If
lis(lo) = lis(hi) lo = lo + 1 Do While lis(lo) < med_value lo = lo + 1 If lo >= hi Then Exit Do Loop If lo >= hi Then lo = hi lis(hi) = med_value Exit Do End If lis(hi) = lis(lo) Loop Quicksort(lis, min, lo - 1) Quicksort(lis, lo + 1, max) End Sub 2.2.2 Algoritma Bucket Sort Menurut Joshi, Panwar dan Pathak (2013) [6], Bucket sort adalah algoritma pengurutan yang membagi n data kedalam berbagai ember, atau bucket, berdasarkan karakteristik tertentu, lalu melakukan pengurutan pada setiap ember secara parsial. Comen, dkk, (2001) [4] menyatakan algoritma bucket sort mengasumsikan bahwa masukkan dibuat secara acak dan didistribusikan secara seragam dengan kondisi tidak berketergantungan satu sama lain. Setiap ember dapat diurutkan dengan algoritma yang berbeda, contohnya adalah menggunakan Insertion Sort pada pengurutan tiap ember, atau dapat memanggil fungsi Bucket Sort secara rekursif. Jumlah dari ember yang dibuat sama dengan jumlah data yang diberikan sehingga Bucket Sort membutuhkan tempat atau memori yang lebih besar sebagai ganti dari pengurangan cost pemrosesan data. Algoritma Bucket Sort memiliki kompleksitas waktu rata-rata sebesar O(n) +
n.0(2.1/n) = O(n). Walaupun masukkan tidak terdistribusi secara seragam, bucket sort akan tetap berjalan secara linear terhadap waktu selama jumlah ukuran ember sama dengan jumlah masukkan. Heineman,Selkow dan Pollice (2008) [5] menyatakan Algoritma Bucket Sort hanya cocok untuk mengurutkan data bilangan saja dan merupakan algoritma noncomaprison based. Pemrosesan data dengan algoritma Bucket Sort adalah sebagai berikut : 1. Membuat suatu inisial array (ember) kosong sebanyak jumlah array yang diberikan . 2. Memasukkan setiap objek pada array yang ingin diurutkan kedalam ember yang sesuai. 3. Melakukan pengurutan pada setiap objek yang ada di setiap ember, dapat dilakukan dengan algoritma lain seperti Insertion sort. Sedangkan metode Bucket sort dengan menggunakan Insertion sort adalah secara berulang-ulang menyisipkan / memasukkan setiap elemen, kedalam posisinya / tempatnya yang benar. Prinsip kerja insertion sort adalah : a. Pengecekan dilakukan mulai dari data ke-1 sampai ke-n b. Bandingkan data ke-1 (1 data ke 2 sampai dengan ke-n) c. Bandingkan data jika lebih kecil maka data ke-1 tersebut dengan data sebelumnya (i-1), jika lebih kecil maka data tersebut dapat disispkan
kedata awal sesuai dengan posisi yang seharusnya. 78
17
0-19
26
20-39
12 17
12
39
72
94
21
40-59
21 23 26 39 17
21
23
26
39
68
12
23
68
60-79
80-99
68 72 78
94
72
2.2.2.1 Pseudocode Pseudocode dari algoritma bucketsort dengan menggunakan bahasa pemrograman Java
public class Java_bucketsort { static void printArray(int[] b) { for (int i = 0; i < b.length; i++) System.out.print(" " + b[i]); System.out.print("\n"); } // Bucket Sort Sorting Code public static void bucketSort(int entry[],int m){ int[] buckets = new int[m];
78
Gambar 2 : Contoh Penerapan Algoritma Bucket Sort
94
for(int j=0;j<m;j++) buckets[j]=0; for(int i=0;i<entry.length;i++) ++buckets[entry[i]]; for(int i=0,j=0;j<m;++j) for(int k=buckets[j];k>0;k--) entry[i++]=j; }
Sedangkan pseudocode bucket sort dengan bahasa pemrograman C++
void bucket_sort (int arr[], int n) { int m = 4200; int buckets[m]; for (int i = 0; i < m; ++i) buckets[i] = 0; element is present in the input for (int i = 0; i < n; ++i) ++buckets[arr[i]]; for (int i = 0, j = 0; j < m; ++j) for (int k = buckets[j]; k > 0; --k) arr[i++] = j; } Dan pseudocode bucket sort dengan bahasa pemrograman VB.Net
Public Shared Sub BucketSort(ByRef data As Integer()) Dim minValue As Integer = data(0) Dim maxValue As Integer = data(0) For i As Integer = 1 To data.Length - 1 If data(i) > maxValue Then maxValue = data(i) End If If data(i) < minValue Then minValue = data(i) End If Next Dim bucket As List(Of Integer)() = New List(Of Integer)(maxValue - minValue) {} For i As Integer = 0 To bucket.Length - 1 bucket(i) = New List(Of Integer)() Next For i As Integer = 0 To data.Length - 1 bucket(data(i) minValue).Add(data(i)) Next Dim k As Integer = 0 For i As Integer = 0 To bucket.Length - 1 If bucket(i).Count > 0 Then For j As Integer = 0 To bucket(i).Count - 1 data(k) = bucket(i)(j)
k += 1 Next End If Next End Sub 3. Pembahasan Dan Hasil Dalam melakukan komparasi antara Algoritma Quicksort dengan Bucket sort penulis menggunakan perangkat : 1. Notebook Acer Dengan Processor AMD C-60 APU with Radeon™ HD Graphics (2 CPUs) – 1.0 GHz. 2. VGA AMD Radeon HD 6290 Graphics – 881 MB. 3. Ram 2 GB. 4. Platform Windows 7 Ultimate 32-bit (6.1, Build 7600). 5. Tool Compiler Java NetBeans IDE 8.1, Compiler C- Free 5, dan Visual Studio 2012 Data random yang digunakan sebanyak 5000 data, dengan 4200 data yang dikeluarkan dalam pengurutan. Didapat kan hasil data seperti dibawah ini
Gambar 3 : Hasil Algoritma Quicksort di Bahasa Pemrograman C++
Gambar 4 : Hasil Algoritma Bucket Sort Di Bahasa Pemrograman C++
Gambar 7 : Hasil Algoritma Bucket Sort Di Bahasa Pemrograman Vb.Net
Gambar 5: Hasil Algoritma Bucket Sort di Bahasa Pemrograman Java Gambar 8 : Hasil Algoritma Quick Sort Di Bahasa Pemrograman Vb.Net
Gambar 6 : Hasil Algoritma Quicksort Di Bahasa Pemrograman Java
4. Kesimpulan Dan Saran Teknik-teknik pepengurutan data memang cukup beragam, namun demikian tentunya dalam prosesnya ada metode yang mempunyai kelebihan dan kekurangan sendiri, paling tidak dengan pemahaman algoritma secara sederhana tersebut, kita lebih mudah dalam menyelesaikan setiap permasalahan yang menyangkut proses pengurutan data. Pada penulisan jurnal ini telah dibahas komparasi dari implementasi algoritma pengurutan berbasis perbandingan yaitu Quicksort, dengan algoritma pengurutan yang tidak berbasiskan perbandingan yaitu Bucket Sort, terhadap data bertipe bilangan atau integer. Analisa penggunaan waktu telah dilakukan untuk menentukan algoritma yang paling tepat digunakan dalam pengurutan data bertipe integer. Berdasarkan logika proses pengurutan data dengan menggunakan algoritma Quicksort dan Bucket Sort, maka dapat disimpulkan sebagai berikut. 1. Hasil Pengujian algoritma Quick Sort lebih sesuai digunakan ketika data yang digunakan berjumlah sedikit ataupun banyak. 2. Dari Hasil pengujian menggunakan pemrograman C++ dengan 5000 data random, yang dikeluarkan hanya 4200 data, waktu yang diperlukan algoritma Quick Sort dalam pengurutan adalah 14,86 second sedangkan algoritma Bucket Sort membutuhkan waktu 68.46 second. 3. Dari Hasil pengujian menggunakan pemrograman Java dengan 5000
data random, yang dikeluarkan hanya 4200 data, waktu yang diperlukan algoritma Quick Sort dalam pengurutan adalah 8,212 second sedangkan algoritma Bucket Sort membutuhkan waktu 10,216 second. 4. Dari Hasil pengujian menggunakan pemrograman Vb.NET dengan 5000 data random, yang dikeluarkan hanya 4200 data, waktu yang diperlukan algoritma Quick Sort dalam pengurutan adalah 8,939 second sedangkan algoritma Bucket Sort membutuhkan waktu 11,391 second. 5. Jadi Quick Sort lebih disbanding Bucket Sort
cepat
Dalam mengurutkan data , masih banyak algoritma yang dapat digunakan. Penyusun menyarankan untuk pengembangan selanjutnya menggunakan metode selain Quick Sort dan Bucket Sort, sehingga dapat memahami logika dalam mengurutkan data baik secara ascending juga descending. Kami juga menyarankan peneliti selanjutnya untuk melakukan komparasi waktu pemrosesan dan pemakaian memori untuk mengurutkan berbagai tipe, seperti integer dan string , sehingga dapat diketahu mana algoritma pengurutan yang paling optimal digunakan secara praktis. UCAPAN TERIMA KASIH Penyusun mengucapakan terima kasih kepada Bapak Dr.Windu Gata, M.Kom selaku dosen mata kuliah Algorithms and Complexity yang telah membimbing penyusun dalam meyusun paper ini.
Penyusun juga mengucapkan terima kasih kepada keluarga dan rekan-rekan mahasiswa program pascasarjana Magister Ilmu Komputer, STMIK Nusa Mandiri yang telah memberi dukungan dan semangat dalam selama penyusunan paper dilaksanakan.
Daftar Pustaka [1]. Audi.,2015 Jurnal Komparasi Algoritma Quicksort dan Bucket Sort pada pengurutan Data Integer. [2]. CCDS. Reference Model for an Open Archival Information System (OAIS). Washington,DC: Magenta Book Issue 2; 2012. [3]. C. Hoare, 1962. Quicksort. Computer Journal, 5(1), pp. 10-15.
The
[4]. Cormen Thomas H., Leiserson Charles E., Rivest Ronald L., Stein Clifford. Introduction to Algorithms (third edition). USA: The MIT Press; 2009 [5]. Heineman George T., Selkow Stanley, Pollice Gary. Algorithms in a Nutshell. O’Reilly Media; 2008 [6]. Joshi Rohit, Panwar Govind Singh, Pathak Preeti. Analysis of Non-Comparison Based Sorting Algorithms: A Review. International Journal of Emerging Research in Management & Technology, 2013; 2(12): Hal. 61-65. [7]. Khreisat, L., 2007. Quicksort: A Historical Perspective and Empirical Study. IJCSNS International Journal of Computer Science and Network Security, 7(12), pp. 54-65 [8]. Mira Kusniara.,2016 Jurnal Komparasi Algoritma Quicksort dan Bucket Sort pada
pengurutan Data Integer dengan menggunakan bahasa pemrograman C++. [9]. Rosen, K. H. Discrete Mathematics and Its Applications (7th ed.). New York: McGraw-Hill; 2012. [10]. Sedgewick R., Wayne K. Algorithms (Fourth Edition). Addison-Wesley Professional; 2011.
