JURNAL TEKNOLOGI INFORMASI & PENDIDIKAN VOL. 6 NO. 1 Maret 2013
ISSN : 2086 – 4981
PERBANDINGAN METODE BUBBLE SORT DAN INSERTION SORT TERHADAP EFISIENSI MEMORI Des Suryani1
ABSTRACT Sorting of data is one of the important operation in the processing of data. Basically there are two kinds of data sorting conditions, ie in ascending sort order (ascending) and descending sort order (descending). The number of methods that can be used in data sorting allows for the selection of the best methods in the process of sorting the data in an effort to save memory usage. Referring to the results of previous studies in which the bubble sort method uses memory more efficiently than the method of selection sort in the process of sorting the data in this study were compared to the previous best method bubble sort method with the following method is insertion sort. Both testing methods are still performed using the programming language C + + on 100 and 1500 data with multiple 100 each data type integer. Based on the test results of the two methods can be concluded that the bubble sort method still uses memory more efficiently than the method of insertion sort. Kata Kunci: sorting, bubble sort, insertion sort INTISARI Pengurutan data merupakan salah satu operasi penting dalam pengolahan data. Pada dasarnya terdapat dua macam kondisi pengurutan data, yaitu pengurutan secara menaik (ascending) dan pengurutan secara menurun (descending). Banyaknya metode yang dapat digunakan dalam pengurutan data memungkinkan untuk dilakukan pemilihan metode yang terbaik dalam proses pengurutan data tersebut sebagai salah satu upaya untuk penghematan penggunaan memori. Merujuk pada hasil penelitian sebelumnya dimana metode bubble sort menggunakan memori yang lebih efisien dibandingkan metode selection sort dalam proses pengurutan data maka dalam penelitian ini dilakukan perbandingan terhadap metode yang terbaik sebelumnya yaitu metode bubble sort dengan metode berikutnya yaitu insertion sort. Kedua metoda tersebut tetap dilakukan pengujian dengan menggunakan bahasa pemrograman C++ terhadap 100 sampai 1500 data dengan kelipatan 100 data yang masing-masingnya bertipe integer. Berdasarkan hasil pengujian dari kedua metode tersebut dapat disimpulkan bahwa metode bubble sort tetap menggunakan memori yang lebih efisien dibandingkan dengan metode insertion sort . Kata Kunci: sorting, bubble sort, insertion sort 1
Dosen Teknik Perangkat Lunak, Fakultas Teknik, Universitas Islam Riau
1
JURNAL TEKNOLOGI INFORMASI & PENDIDIKAN VOL. 6 NO. 1 Maret 2013 PENDAHULUAN Pengurutan data atau sorting merupakan jenis operasi penting dalam pengolahan data. Hampir setiap saat dalam kehidupan seharihari kita selalu menjumpai permasalahan yang harus diselesaikan dengan melibatkan operasi pengurutan data. Begitu pentingnya operasi tersebut sehingga sampai saat ini telah banyak dikembangkan metodametoda pengurutan data dan mungkin akan tetap bermunculan metoda metoda baru. Pengurutan data juga merupakan salah satu proses yang sangat dibutuhkan di dalam pemrograman. Sorting atau pengurutan ini adalah proses mengatur sekumpulan objek menurut urutan atau susunan tertentu. Adanya kebutuhan akan pengurutan melahirkan beberapa macam pengurutan. Metode-metode pengurutan antara lain, yaitu bubble sort, selection sort, insertion sort, dilakukan pada beberapa jenis/tipe data seperti bilangan bulat (integer), bilangan pecahan/desimal, karakter maupun kumpulan karakter (string). Dari kumpulan data yang disimpan dapat mempunyai tipe data yang berbeda-beda dan pengurutan terhadap data tersebut dapat dilakukan untuk satu atribut atau lebih tergantung pada kebutuhan yang diinginkan. Contoh: untuk menentukan rangking tertinggi nilai mahasiswa dapat dilakukan proses pengurutan data nilai mahasiswa yang bertipe numerik (bilangan desimal) secara menurun dari nilai tertinggi ke nilai terendah, pembuatan daftar kehadiran mahasiswa maupun karyawan datanya pada umumnya banyak diurutkan berdasarkan nama yang bertipe kumpulan karakter (string) yang data nama tersebut diurutkan mulai menaik. Dan mungkin banyak contoh lainnya yang dapat dilakukan dalam kehidupan kita.
ISSN : 2086 – 4981
quick sort, merge sort dan lain sebagainya. [1] Dalam ilmu komputer, algoritma pengurutan adalah algoritma yang meletakkan elemen-elemen suatu kumpulan data dalam urutan tertentu. Pada kenyataannya algoritma ini digunakan adalah secara terurut baik secara numerikal ataupun secara leksikografi (urutan secara abjad sesuai kamus). Sorting dapat diartikan sebagai sebuah penyortiran atau dengan kata lain mempunyai arti pengurutan. Salah satu contohnya adalah pengurutan data integer, string, float, dan lain-lain. Dalam algoritma bubble sort yang akan dibuat adalah kondisi urut naik (ascending). Dimana perbandingan kedua data memiliki ketentuan yaitu data pertama lebih besar dengan data kedua dan jika kondisi tersebut terpenuhi maka dilakukan proses pengurutan data atau sorting. Semua metoda yang digunakan dalam proses pengurutan data dapat Di atas telah diketahui bahwa terdapat begitu banyak metode yang dapat digunakan untuk menyelesaikan masalah dalam pengurutan data. Aspek yang harus dipertimbangkan di dalam pemilihan metode ini berhubungan dengan keefisienan khususnya dalam pemakaian ruang penyimpanan data (memori). Masing-masing metode mempunyai kelebihan dan kelemahan. Namun, efisiensi dari algoritma sorting tetap harus dipertimbangkan. Menurut hasil penelitian sebelumnya[5] membuktikan bahwa hasil pengujian dari metode bubble sort dan selection sort, metode bubble sort menggunakan memori yang lebih efisien dibandingkan dengan metode selection sort. Berdasarkan hal tersebut di atas, perlu dilanjutkan penelitian berikutnya untuk metode yang lain. Dalam hal ini dilakukan perbandingan 2
JURNAL TEKNOLOGI INFORMASI & PENDIDIKAN VOL. 6 NO. 1 Maret 2013 metode yang terbaik sebelumnya metode Bubble Sort dengan Insertion Sort dalam proses pengurutan data secara menaik (ascending) dengan melakukan pengujian menggunakan bahasa pemrograman C++ terhadap 100 sampai 1500 data dengan kelipatan 100 data yang masingmasingnya bertipe integer dengan data yang telah disusun secara acak. PENDEKATAN PEMECAHAN MASALAH Proses pengurutan data banyak ditemukan dalam komputer. Hal ini karena data yang sudah urut akan lebih mudah dan cepat untuk dicari. Untuk membentuk data yang tidak urut menjadi data yang terurut, terdapat berbagai algoritma yang bisa digunakan. Pengurutan data itu sendiri dapat dilakukan terhadap data yang secara keseluruhan diletakkan dalam memori ataupun terhadap data yang tersimpan pada pengingat eksternal. Efisiensi di dalam algoritma sangat dipertimbangkan karena suatu masalah dapat diselesaikan dengan berbagai macam cara yang dalam hal ini disebut sebagai algoritma sebagai langkah penyelesaian masalah. Algoritma yang baik adalah algoritma yang efisien, salah satunya dinilai dari aspek kebutuhan ruang penyimpanan data (memori) yang lebih sedikit. Pembuatan program yang meminimumkan penggunaan memori akan dapat mempercepat proses eksekusi program. Dalam bidang pemrograman, algoritma didefinisikan sebagai suatu metode khusus yang tepat dan terdiri dari serangkaian langkah terstruktur dan dituliskan secara sistematis yang akan dikerjakan untuk menyelesaikan suatu masalah dengan bantuan komputer.
ISSN : 2086 – 4981
merupakan metode pengurutan yang menggunakan konsep gelembung (bubble). Bubble sort adalah metode sorting yang paling sederhana [6]. Diberikan nama “bubble” karena konsep dari algoritmanya diibaratkan seperti gelembung air untuk elemen struktur data yang seharusnya pada posisi awal. Bubble sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Dimana cara kerjanya adalah dengan berulang-ulang melakukan proses looping (perulangan) terhadap elemenelemen struktur data yang belum diurutkan. Nilai dari masing-masing elemen akan dibandingkan secara terus menerus sampai pengurutan selesai [1]. Seringkali dikatakan bahwa metode ini kurang efisien namun sangat mudah dipahami. Sesungguhnya secara tidak langsung, algoritma dari metode ini seolah-olah menggeser satu demi satu elemen dari kanan ke kiri atau dari kiri ke kanan tergantung pada jenis pengurutannya. Jenis pengurutan sorting ada 2 yaitu menaik (ascending) dan menurun (descending). Dimana ascending itu mengurutkan data dari kecil ke besar dan descending itu mengurutkan data dari besar ke kecil. Sebelum dilakukan proses penukaran data, terlebih dahulu dilakukan proses perbandingan, dimana perbandingan datanya tergantung pada jenis pengurutannya. Pengurutan data secara ascending, akan dilakukan pembandingan data n > data n+1. Selama pembandingan tersebut memenuhi, maka dilakukan pertukaran data dan sebaliknya selama tidak memenuhi kondisi tersebut, maka tidak akan terjadi pertukaran data. Untuk lebih jelasnya logika pengurutan data secara ascending dengan menggunakan metoda bubble sort dapat dilihat pada gambar 1.
HASIL DAN PEMBAHASAN Bubble Sort Bubble sort merupakan salah satu jenis sorting. Metode bubble sort
3
JURNAL TEKNOLOGI INFORMASI & PENDIDIKAN VOL. 6 NO. 1 Maret 2013
ISSN : 2086 – 4981
Tabel 1. Contoh pengurutan data secara menaik (ascending) dengan metoda bubble sort Iter asi ke i 0 1 2 3 4 5 6 Has il
Hasil Pengurutan
3 4 3 4 3 4 3 4 3 4 2 8 2 3 1 5
6 7 6 7 6 7 1 5 1 5 1 5 1 5 2 3
2 3 2 3 2 3 2 3 2 3 2 3 2 8 2 8
2 8 2 8 2 8 2 8 2 8 3 4 3 4 3 4
9 8 6 7 6 7 6 7 6 7 6 7 6 7 6 7
1 5 1 5 1 5 6 7 6 7 6 7 6 7 6 7
8 9 8 9 8 9 8 9 8 9 8 9 8 9 8 9
6 7 9 8 9 8 9 8 9 8 9 8 9 8 9 8
Insertion Sort Metode insertion sort adalah metode pengurutan yang mengambil sebuah data sisip pada data yang diurutkan dan menggeser data yang lebih besar dari data sisip agar data sisip dapat ditempatkan pada tempat yang benar[1]. Algoritma pengurutan data secara menaik dengan metoda insertion sort dapat dijelaskan dalam program flowchart pada gambar 2.
Gambar 1. Program Flowchart metode Bubble Sort Berdasarkan program flowchart diatas, dapat diberikan contoh datadata yang akan diurutkan adalah sebagai berikut: Contoh : 34 67 23 28 98 15 89 67 Dari data-data tersebut, langkah-langkah yang dilakukan dalam proses pengurutan secara menaik menggunakan metoda bubble sort dapat ditelusuri sebagaimana ditunjukkan pada tabel 1. Dalam tabel tersebut, data yang bergaris bawah merupakan data terbesar yang ditemukan dan akan menempati posisi paling akhir sebelum elemenelemen data yang telah diurutkan pada langkah sebelumnya.
Contoh : 34 67 23 28 98 15 89 67
4
JURNAL TEKNOLOGI INFORMASI & PENDIDIKAN VOL. 6 NO. 1 Maret 2013 3 4 5 6 7 Ha sil
Berdasarkan program flowchart diatas, dapat diberikan contoh datadata yang akan diurutkan secara menaik. Langkah-langkah yang dilakukan dalam proses pengurutan ditunjukkan pada tabel 2. Dalam tabel tersebut, data yang bergaris bawah merupakan data sisip. Data sisip dimulai dari data pada array dengan indeks 2 sampai array dengan indeks sebanyak jumlah data (n). Setiap data sisip dibandingkan dengan data yang ada sebelumnya. Jika data sebelumnya tidak ada yang lebih besar dari data sisip, maka tidak ada data yang harus bergeser ke belakang. Tabel 2. Contoh pengurutan data secara menaik (ascending) dengan metoda insertion sort Hasil Pengurutan 3 4
6 7
2 3
2 8
9 8
1 5
8 9
6 7 3 4 2 8 2 8 2 3 2 3 2 3
2 3 6 7 3 4 3 4 2 8 2 8 2 8
2 8 2 8 6 7 6 7 3 4 3 4 3 4
9 8 9 8 9 8 9 8 6 7 6 7 6 7
1 5 1 5 1 5 1 5 9 8 8 9 6 7
8 9 8 9 8 9 8 9 8 9 9 8 8 9
6 7 6 7 6 7 6 7 6 7 6 7 9 8
Penyusunan Program Program merupakan salah satu bagian penting pada komputer yang mengatur komputer agar melakukan aksi yang sesuai dengan yang dikehendaki oleh pembuatnya [4]. Suatu program ditulis dengan mengikuti kaidah bahasa pemrograman tertentu. Dalam konteks pemrograman, terdapat sejumlah bahasa pemrograman, seperti C, C++, Pascal, Basic dan lain-lain. Orang membuat program biasanya bertujuan untuk menyelesaikan masalah. Namun sebelum dapat menyelesaikan masalah dengan program, terdapat 3 (tiga) langkah penting yang perlu dilakukan terlebih dahulu. 1. Menganalisis masalah dan membuat algoritma Proses pertama, menganalisis masalah dan membuat algoritma memang tidak dapat begitu saja diwujudkan. Pengalaman, pengetahuan, kreativitas, imajinasi, dan kelihaian merupakan faktor-faktor yang menentukan sekali keberhasilan langkah ini. Di dalam analisis masalah ini diperlukan tindakan untuk mengidentifikasi informasi yang menjadi keluaran pemecahan masalah dan datadata yang menjadi masukan. Berdasarkan hal itu diperlukan
Gambar 2. Program flowchart metode Insertion Sort
Iter asi 1 2
3 4 2 3 2 3 2 3 1 5 1 5 1 5
ISSN : 2086 – 4981
6 7 5
JURNAL TEKNOLOGI INFORMASI & PENDIDIKAN VOL. 6 NO. 1 Maret 2013
ISSN : 2086 – 4981
prosedur untuk mengolah masukan menjadi keluaran yang dikehendaki. Komputer tidak akan berarti apa-apa tanpa adanya langkah detail yang menyusun prosedur. Langkah detail yang ditujukan untuk komputer guna menyelesaikan suatu masalah inilah yang disebut algoritma. 2. Menuangkan algoritma kedalam bentuk program Langkah menuangkan algoritma ke dalam program ditentukan oleh faktor bahasa pemrograman yang akan digunakan. 3. Mengeksekusi dan menguji program. Setelah program dibuat dan dikompilasi, program perlu dijalankan untuk diuji kebenarannya.
main() { int x [100] = { 3,5,1,8,4,2,0,9,7,6,
Berdasarkan algoritma dari masing-masing metode tersebut, kemudian diuji dengan menggunakan bahasa pemrograman C++. Bahasa pemrograman C++ merupakan pengembangan dari bahasa pemrograman C dan mendukung pemrograman berorientasi objek. Dengan menggunakan C++, tetap dapat menulis program C.
int tukar=1; int i,temp; clrscr(); while (tukar==1) { tukar=0; for (i=0; i<100-1; i++) { if (x[i]>x[i+1]) { temp=x[i]; x[i]=x[i+1]; x[i+1]=temp; tukar=1; } } } for (i=0; i<100; i++) cout << setw (5) << x[i]; getch();
13,15,11,18,14,12,10,19,17,16, 23,25,21,28,24,22,20,29,27,26, 33,35,31,38,34,32,30,39,37,36, 43,45,41,48,44,42,40,49,47,46, 53,55,51,58,54,52,50,59,57,56, 63,65,61,68,64,62,60,69,67,66, 73,75,71,78,74,72,70,79,77,76, 83,85,81,88,84,82,80,89,87,86, 93,95,91,98,94,92,90,99,97,96 };
Berikut ini diberikan contoh pemrograman C++ untuk proses pengurutan data secara ascending terhadap 100 data yang disusun secara acak dan masing-masingnya bertipe integer dengan menggunakan metode bubble sort dan insertion sort. Dan untuk data kelipatan 100 berikut sampai 1500 data dilakukan dengan menambahkan sesuai jumlah datanya dan jumlah perulangan juga disesuai dengan jumlah datanya.
}
Program C++ untuk metode Insertion Sort:
Program C++ untuk metode Bubble Sort: # include # include # include # include
# include # include # include # include main()
<stdio.h>
6
<stdio.h>
JURNAL TEKNOLOGI INFORMASI & PENDIDIKAN VOL. 6 NO. 1 Maret 2013
ISSN : 2086 – 4981
Tabel 3. Perbandingan penggunaan memori antara metode Bubble Sort dan Insertion Sort
{ int x [100] = { 3,5,1,8,4,2,0,9,7,6, 13,15,11,18,14,12,10,19,17,16, 23,25,21,28,24,22,20,29,27,26, 33,35,31,38,34,32,30,39,37,36, 43,45,41,48,44,42,40,49,47,46, 53,55,51,58,54,52,50,59,57,56, 63,65,61,68,64,62,60,69,67,66, 73,75,71,78,74,72,70,79,77,76, 83,85,81,88,84,82,80,89,87,86, 93,95,91,98,94,92,90,99,97,96 }; int i,j,data_sisip; clrscr(); for (i=1; i<100; i++) { data_sisip=x[i]; j=i-1; while ((data_sisip<x[j]) && (j>0)) { x[j+1]=x[j]; j=j-1; } x[j+1]=data_sisip; } for (i=1; i<100; i++) cout << setw (5) << x[i]; getch();
KESIMPULAN Berdasarkan logika proses pengurutan data dengan menggunakan metoda Bubble Sort dan Insertion Sort yang diuji dengan bahasa pemrograman C++ mulai dari pembuatan program sumber (.cpp), dilanjutkan dengan proses kompilasi yang menghasilkan file objek (.obj) dan hasil eksekusi akan membentuk file yang dapat dieksekusi (.exe). Hasil pengujian dari masing-masing file tersebut dapat disimpulkan sebagai berikut : a. File sumber (.cpp) pada metoda insertion sort menggunakan jumlah memori yang lebih kecil dibandingkan metoda bubble sort. b. Hasil kompilasi program yang menghasilkan file objek (.obj) antara metode bubble sort dan insertion sort memerlukan jumlah memori yang sama. c. Sedangkan program yang menghasilkan file yang dapat dieksekusi (.exe), ternyata metode bubble sort menggunakan jumlah memori yang lebih kecil dibanding metode insertion sort. d. Berdasarkan perbandingan jumlah pemakaian memori antara
} Hasil eksekusi kedua program tersebut, akan menampilkan data yang terurut dari data terkecil ke data terbesar. Pengujian dilakukan mulai dari 100 data sampai 1500 data dengan kelipatan 100 data. Data-data tersebut disimpan dalam sebuah variabel x bertipe data array yang masing-masingnya merupakan bilangan bulat (integer). Nilai dari data-data tersebut, sebelumnya diset secara acak, kemudian baru dilakukan proses pengurutan data secara ascending. Berdasarkan perbandingan kedua metode dengan 3 (tiga) file yang dihasilkan dari pemrograman C++ terhadap penggunaan memori dapat diuraikan pada tabel 3.
7
JURNAL TEKNOLOGI INFORMASI & PENDIDIKAN VOL. 6 NO. 1 Maret 2013 metoda bubble sort dan insertion sort dengan menggunakan bahasa pemrograman C++ dalam proses pengurutan data, metoda bubble sort akan memerlukan memori yang lebih efisien dibandingkan metoda insertion sort. e. Hasil ini dapat dilanjutkan dengan membandingkan antara metodametoda sorting lainnya. DAFTAR PUSTAKA [1] Kadir, Abdul, Heriyanto, 2005, Algoritma Pemrograman Menggunakan C++, Yogyakarta, Andi [2]
Suryani, Des. 2012, Perbandingan Metode Bubble Sort dan Selection Sort Terhadap Efisiensi Memori, Prosiding Seminar KNSI 2012, Bali, P3M STIKOM Bali.
[3]
H.M. Deitel, P.J, Deitel, 1994, C++ How to Program, Prentice Hall International Edition.
8
ISSN : 2086 – 4981
