Jurnal Evolusi Volume 5 No 1 ‐ 2017 ‐ evolusi.bsi.ac.id Analisa Perbandingan Algoritma Insertion Sort Dan Merge Sort Dalam PENGURUTAN DATA Pada C++ Dan Java Ardiyansyah Komputerisasi Akuntansi, AMIK BSI Pontianak
[email protected] Abstract - Ordering data interpreted as a rearrangement or sort the data that was originally inserted at random and then into data sequences. The purpose of sorting the data itself, namely to simplify the search data. Data sorting method is also needed by programmers in designing applications or programs due to facilitate the processing of data, particularly data on a large scale. Comparison of the data sorting method, the algorithm used is algorithm Insertion Sort and Merge Sort. As for implementation using the programming language C ++ and Java. Then the source code of the two algorithms are implemented in each programming language will be changed so that the data entered by the user's request will generate random data. After that, the two algorithms are compared and tested in the sequencing data. And the results obtained from testing and comparison made is that in C ++ algorithm Merge Sort is faster and showed better performance than the Insertion Sort algorithm. Whereas in Java Insertion Sort algorithm is faster and better than Merge Sort algorithm. Especially for the amount of data being entered > 10000. The Insertion Sort algorithm is superior in memory usage or storage space than Merge Sort algorithm for Insertion Sort algorithm does not use recursion in the sort routine. Keywords: Data Ordering Methods, Algorithms Insertion Sort , Merge Sort algorithm. Abstrak - Data Pengurutan diartikan sebagai penataan ulang atau mengurutkan data yang awalnya disisipkan pada urutan data acak dan kemudian ke. Tujuan dari pemilahan data itu sendiri, yaitu untuk mempermudah pencarian data. metode pengurutan data juga dibutuhkan oleh programmer dalam merancang aplikasi atau program karena memudahkan pengolahan data, terutama data dalam skala besar. Perbandingan data metode pengurutan, algoritma yang digunakan adalah Algoritma Insertion Sort dan Merge Sort. Adapun implementasi menggunakan bahasa pemrograman C ++ dan Java. Kemudian kode sumber dari dua algoritma diimplementasikan dalam setiap bahasa pemrograman akan diubah sehingga data yang dimasukkan oleh permintaan pengguna akan menghasilkan data acak. Setelah itu, kedua algoritma dibandingkan dan diuji dalam data sequencing. Dan hasil yang diperoleh dari pengujian dan perbandingan yang dibuat adalah bahwa dalam algoritma C ++ Merge Sort yaitu lebih cepat dan menunjukkan kinerja yang lebih baik daripada Algoritma Insertion Sort. Sedangkan pada Algoritma Java Insertion Sort lebih cepat dan lebih baik dari Algoritma Merge Sort. Terutama untuk jumlah data yang dimasukkan > 10000. Penyisipan ini unggul dalam penggunaan memori atau ruang penyimpanan dari Algoritma Merge Sort untuk algoritma Insertion Sort tidak menggunakan rekursi dalam rutinitas semacam. Kata Kunci: Data Ordering Methods, Algoritma Insertion Sort, Algoritma Merge Sort. A.
PENDAHULUAN Sorting atau pengurutan Data diartikan sebagai penyusunan kembali atau mengurutkan data yang diinput secara acak, kemudian berakhir dengan data yang sudah terurut dengan teratur sebagai output. Penerapan dalam pengurutan data sering juga ditemui dalam kehidupan sehari-hari, sebagai contoh penerapannya adalah absensi siswa yang diurutkan berdasarkan abjad nama siswa atau nis siswa. Pengurutan data dilakukan dengan tujuan mempermudah dalam pencarian data dan mempercepat dalam mengetahui data terbesar dan data terkecil. Misalkan dalam penyeleksian nilai siswa untuk memperoleh mana siswa yang mendapatkan nilai tertinggi dan nilai terendah. Dalam penyeleksian tersebut dilakukanlah pengurutan data berdasarkan nilai siswa yang paling tinggi hingga nilai siswa yang paling rendah. ISSN : 2338 – 8161
Pengurutan data juga dibutuhkan dalam pemrograman karena dalam melakukan perancangan aplikasi atau program biasanya diperlukan sebuah pengurutan data untuk memudahkan dalam pemrosesan data tersebut. Banyak algoritma sorting yang sering digunakan dan diperlukan dalam pembuatan aplikasi atau program. Oleh karena itu, pemahaman terhadap beberapa algoritma sorting perlu diketahui dan diimplementasikan ke dalam program. Ada banyak metode sorting yang dapat digunakan yaitu: bubble sort, bi-directional bubble sort, selection sort, shaker sort, insertion sort,Merge Sort, in-place Merge Sort, shell sort, heap sort, quick sort, swap sort dan lain sebagainya. Pada penenelitian ini, akan membahas dua metode pengurutan, yaitu Insertion Sort dan Merge Sort. Kedua metode tersebut akan dibandingkan dengan menggunakan dua
7
Jurnal Evolusi Volume 5 No 1 ‐ 2017 ‐ evolusi.bsi.ac.id bahasa pemrograman yaitu C++ dan Java. Perbandingan tersebut dilakukan untuk mengetahui mana diantara kedua metode tersebut yang paling cepat dalam pengurutan data dan mudah untuk diterapkan. Kemudian dari kedua metode tersebut akan dilihat ruang atau memori mana yang lebih efektif untuk digunakan. TINJAUAN PUSTAKA Algoritma Menurut Sjukani (2009:1) Algoritma pada dasarnya adalah alur pikiran dalam menyelesaikan suatu pekerjaan, yang dituangkan dalam bentuk tertulis yang dapat dimengerti oleh orang lain. Sedangkan menurut Suarga (2012:1) algoritma merupakan susunan langkah yang pasti, yang bila diikuti maka akan mentransformasi data input dan output berupa informasi. Dari menurut para ahli bahwa algoritma adalah susunan langkah yang pasti dari alur pikiran yang dituangkan dalam bentuk tertulis sehingga menjadi sebuah informasi yang dimengerti oleh orang lain. Menurut Donald Kunth dalam buku Suarga (2012:4) Sebuah algorima juga harus memenuhi kriteria sebagai berikut: 1. Input Suatu algoritma memiliki input atau kondisi awal sebelum dilaksanakan, bisa berupa nilai-nilai peubah yang diambil dari himpunan kusus. 2. Output Suatu algoritma akan mengahsilkan output setelah dilaksanakan atau algoritma akan mengubah kondisi awal menjadi kondisi akhir, dimana nilai output diperoleh dari nilai input yang telah diproses melalui algoritma. 3. Definiteness Langkah-langkah yang dituliskan dalam algoritma terdefinisi dengan jelas sehingga mudah dilaksanakan oleh pengguna algoritma. 4. Finiteness Suatu Algoritma harus memberi kondisi akhir setelah jumlah langkah yang terbatas jumlahnya dilakukan terhadap setiap kondisi awal atau input yang diberikan. 5. Effectiveness Setiap langkah dalam algoritma bisa dilaksanakan dalam suatu selang waktu tertentu sehingga pada akhirnya didapatkan suatu yang diharapkan. 6. Generality Setiap langkah alhoritma berlaku untuk setiap himpunan input yang sesuai dengan persoalan yang diberikan, tidak hanya untuk himpunan tertentu.
a. Insertion Sort Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Insertion Sort disebut-sebut sebagai metode pertengahan. Artinya, metode ini memiliki kecepatan ratarata antara metode primitif (bubble dan selection) dan modern (merge dan quick) (Saptadi dan Sari, 2012:2). Proses yang terjadi pada pengurutan dengan menggunakan metode Insertion Sort dimulai dari data ke-2, kemudian disisipkan tempat yang sesuai. Data pada posisi pertama diandaikan memang suda pada tempatnya (Utami dan Sukirisno, 2005:239). Metode insertion sort adalah metode pengurutan data yang paling sederhana yaitu dengan menyisipkan data sesuai dengan posisi yang tepat dan pengurutan dimulai dari data ke2.
B. 1.
ISSN : 2338 – 8161
i.
Algoritma dan Pseudocode Ide dari algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini menerangkan bagaimana algoritma Insertion Sort bekerja dalam pengurutan kartu (Saptadi dan Sari, 2012:2).
Gambar 1. Analogi Metode Insertion Sort Anggaplah bahwa terdapat sebuah meja yang berisi setumpuk kartu. Meja ini melambangkan kondisi larik sebelum diurutkan. Langkah-langkah pengurutan adalah sebagai berikut: a. Ambil kartu pertama dari meja, letakan di tangan kiri. b. Ambil kartu kedua dari meja, bandingkan dengan kartu yang berada di tangan kiri, kemudian pada urutan yang sesuai setelah urutan. c. Ulangi proses hingga seluruh kartu pada meja telah diletakkan berurutan pada tangan kiri.
8
Jurnal Evolusi Volume 5 No 1 ‐ 2017 ‐ evolusi.bsi.ac.id Menurut Utami dan Sukrisno (2005:252) Metode Merge Sort adalah menggabungkan dua buah array yang sudah terurut. Menurut Saptadi dan Sari (2012:3) Merge Sort adalah metode pengurutan yang menggunakan pola divide and concuer. Langkah kerja dari Merge Sort (Saptadi dan Sari, 2012:3): 1. Divide Memilah elemen – elemen dari rangkaian data menjadi dua bagian dan mengulangi pemilahan hingga satu elemen terdiri maksimal dua nilai. 2. Conquer Mengurutkan masing-masing elemen. 3. Kombinasi Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan. Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.
Kartu-kartu pada tangan kiri tersebut menunjukan kondisi larik sesudah diurutkan. Pseudocode untuk algoritma Insertion Sort adalah sebagai berikut (Saptadi dan Sari, 2012:3): insertionsort(data[],n) for(i = 1; i < n; i++) pindahkan seluruh elemen data[j] yang lebih besar daripada data[i] sebanyak satu posisi; geser data[ i ] pada posisi yang tepat; ii.
Kompleksitas Algoritma Kondisi terbaik (best case) tercapai jika data telah terurut. Hanya satu perbandingan dilakukan untuk setiap posisi i, sehingga terdapat n – 1 perbandingan atau O(n) (Saptadi dan Sari, 2012:3).
Gambar 2. Kondisi Best Case pada Insertion Sort
Dari pengertian dan langkah kerja dari merge sort diatas dapat disimpulkan bahwa merge sort adalah metode pengurutan dengan memisahkan elemen-elemen dari rangkaian data menjadi dua bagian, mengurutkan setiap elemen yang sudah dibagi menjadi dua bagian dan menggabungkan kembali dua buah array yang sudah terurut menjadi rangkaian data yang berurutan.
Kondisi terburuk (worst case) tercapai jika data telah urut namun dengan urutan yang terbalik. Pada kasus ini, untuk setiap i, elemendata[i] lebih kecil dari elemen data[0], …,data[i-1], masing-masing dari elemen dipindahkan satu posisi (Saptadi dan Sari, 2012:3).
i.
Algoritma dan Pseudocode Algoritma Merge Sort sebenarnya sederhana (Saptadi dan Sari, 2012:4): bagi larik menjadi dua sama besar, urutkan bagian pertama, urutkan bagian kedua,lalu gabungkan. Sebagai contoh, jika terdapat data berupa 38, 27, 43, 3, 9,82, dan 10 maka ilustrasi pengurutannya adalah sebagai berikut:
Gambar 3. Kondisi Worst Case pada Insertion Sort Untuk setiap iterasi i pada kalang for terluar, selalu ada perbandingan i, sehingga jumlah total perbandingan untuk seluruh iterasi pada kalang ini adalah (Saptadi dan Sari, 2012:3): Gambar 4. Ilustrasi Merge Sort Pseudocode untuk Merge Sort (Saptadi dan Sari,2012:4) adalah sebagai berikut: b. Merge Sort
ISSN : 2338 – 8161
mergesort(data) if data memiliki setidaknya dua elemen
9
Jurnal Evolusi Volume 5 No 1 ‐ 2017 ‐ evolusi.bsi.ac.id :
mergesort (separuh kiri dari data); mergesort (separuh kanan dari data; merge (kedua bagian ke dalam suatu urutan); Sedangkan pseudocode untuk merge itu sendiri adalah: merge (arrayl, pertama, terakhir) tengah = (pertama + terakhir) / 2; il=0; i2=pertama; i3=tengah+1; while kedua sub larik dari array1 memiliki elemen if arrayl[i2] < arrayl[i3] temp[il++] = arrayl[i2++]; else temp[il++]=arrayl[i3++]; masukkan ke dalam temp sisa elemen dari arrayl; masukkan ke arrayl isi dari temp;
Gambar 5. Kondisi Worst Case Pada Merge Sort Pada kondisi ini (Saptadi dan Sari, 2012:4):
Kedua persamaan tersebut untuk selanjutnya diperluas seperti berikut (Saptadi dan Sari, 2012:4):
ii.
Kompleksitas Algoritma Kompleksitas algoritma untuk larik dengan n elemen dan jumlah pergeseran (T) dihitung melalui relasi rekursif berikut ini (Saptadi dan Sari, 2012:4):
Adapun M(n) dihitung lewat cara berikut (Saptadi dan Sari, 2012:4):
Dengan mengenali pola yang ada, maka dapat dituliskan persamaan:
Dengan 2i=n dan I=n log n dan memasukan nilai awal persamaan: Maka kompleksitas pada kondisi worst case adalah O(n log n) (Saptadi dan Sari, 2012:4).
Memilih i=log n sedemikian sehingga n=2i, maka diperoleh (Saptadi dan Sari, 2012:4):
Kasus terbaik (best case) untuk metode ini dijumpai pada kondisi dimana elemen memiliki elemen memiliki nilai terbesar yang lebih dibandingkan dengan seluruh nilai pada elemen yang lain (Saptadi dan Sari, 2012:4), sebagai berikut ini:
Kasus terburuk (worst case) terjadi bila selama pemanggilan fungsi rekursif merge, nilai terbesar dari setiap elemen terletak di larik yang berbeda (Saptadi dan Sari, 2012:4). Hal ini memaksa fungsi merge untuk melakukan pengurutan secara berpindah-pindah antar larik, sebagaimana digambarkan berikut
ISSN : 2338 – 8161
10
Jurnal Evolusi Volume 5 No 1 ‐ 2017 ‐ evolusi.bsi.ac.id double awal=GetTickCount(); {fungsi yang diuji} Double akhir= GetTickCount(); Kemudian tambahkan fungsi mengisikan data secara acak:
untuk
Serta menambahkan 2 file header yaitu: #include
#include <windows.h> Gambar 6. Kondisi Best Case pada Merge Sort Waktu eksekusi dapat diketahui dengan menggunakan selisih antara variabel awal dan akhir, seperti berikut:
Pada sekenario ini hanya n/2 perbandingan dari elemen yang diperlukan. Menggunakan peroses perhitungan yang sama sebagaimana dalam kasus terburuk diperoleh (Saptadi dan Sari, 2012:4):
cout<<endl<<endl; cout<<"Waktu Eksekusi awal)<<" "<<"MS";
:
"<<(akhir-
b. Bahasa Pemrograman Java Fungsi yang digunakan untuk menampilkan waktu eksekusi program pada Java sebagai berikut: Dengan kata lain diperoleh juga kompleksitas yang sama, O(n log n) (Saptadi dan Sari, 2012:4).
long awal = System.currentTimeMillis(); {fungsi yang diuji} long akhir = System.currentTimeMillis();
2. PEMBAHASAN a. Pengujian Pengujian ini dilakukan untuk mengetahui dan membandingkan kecepatan eksekusi program dari algoritma Insertion Sort dan Merge Sort terhadap data yang dimasukan dengan jumlah tertentu, baik pada bahasa pemrograman C++ maupun pada Java. Pengujian ini meliputi beberapa prosedur, antara lain: 1. Perangkat yang digunakan Perangkat yang digunakan pada pengujian ini adalah Borland C++ 5.02 dan NetBeans DE 7.3 platform Windows 7 Professional dan komputer notebook dengan Spesifikasi: a. Intel Pentium R Processor P62000 2.13GHz (2CPUs) b. Intel R HD Graphics c. 1,00 GB RAM
Kemudian tambahkan mengisikan data secara acak:
untuk
for(int i=0; i
2. Mengubah Kode Sumber Pengubahan kode sumber pada setiap algoritma berfungsi untuk menampilkan waktu eksekusi program, baik pada C++ maupun Java. a. Bahasa Pemrograman C++ Fungsi yang digunakan untuk menampilkan waktu eksekusi program pada C++ sebagai berikut: ISSN : 2338 – 8161
fungsi
3. Eksekusi Program Dalam pengujian ini dilakukan eksekusi program pada kedua metode tersebut baik di C++ maupun Java. Jumlah data yang di input mulai dari 10000 hingga 100000 dengan kenaikan 10000 disetiap eksekusi dilakukan. Hasil eksekusi program pengujian algoritma Insertion Sort pada C++:
11
Jurnal Evolusi Volume 5 No 1 ‐ 2017 ‐ evolusi.bsi.ac.id
Gambar 14. Hasil Pengujian Merge Sort Pada Java
Gambar 11. Hasil Pengujian Insertion Sort Pada C++ Hasil eksekusi program pengujian algoritma Merge Sort pada C++:
b. Hasil Akhir Hasil akhir yang diperoleh dari pengujian dari kedua metode pada tiap bahasa pemrograman akan dicatat ke dalam tabel, kemudian digambarkan ke dalam bentuk diagram batang dan grafik, sebagai berikut: 1. Tabel Pencatatan Hasil Eksekusi Pada C++ Tabel 1. Hasil Waktu Eksekusi Pada C++ Jumlah Data
Gambar 12. Hasil Pengujian Merge Sort Pada C++ Hasil eksekusi program pengujian algoritma Insertion Sort pada Java:
Waktu Eksekusi (MS) Insertion Sort Merge Sort
10000
63
15
20000
156
31
30000
343
47
40000
578
62
50000
905
62
60000
1280
78
70000
1747
78
80000
2277
94
90000
2886
109
100000
3557
125
2. Tabel Pencatatan Hasil Eksekusi Pada Java Tabel 2. Hasil Waktu Eksekusi Pada Java Jumlah Data
Waktu Eksekusi (MS) Insertion Merge Sort Sort 78 3837
Gambar 13. Hasil Pengujian Insertion Sort Pada Java
10000 20000
265
5148
Hasil eksekusi program pengujian algoritma Merge Sort pada Java:
30000
577
8721
40000
967
10640
50000
1529
13275
60000
2168
15850
70000
2933
22277
80000
3838
26832
90000
4836
29749
100000
5944
45646
ISSN : 2338 – 8161
12
Jurnal Evolusi Volume 5 No 1 ‐ 2017 ‐ evolusi.bsi.ac.id 3.
Hasil Waktu Eksekusi Pada C++ Yang di Gambarkan Dalam Bentuk Grafik
4.
Untuk ruang atau memori yang dibutuhkan, algoritma Merge Sort membutuhkan memori atau ruang yang lebih besar dikarenakan algoritma ini memakai dua elemen terpisah dan dilakukan secrara rekursif.
DAFTAR PUSTAKA [1] Saptadi Arief Hendra, Desi Windi Sari. 2012. Analisis Algoritma Insertion Sort, Merge Sort dan Implementasinya Dalam Bahasa Pemrograman C++. Vol. 4 No 2. 2012. [2] Sjukani Moh. 2009. Algoritma (Algoritma dan Struktur Data 1) Dengan C, C++, dan Java, Edisi 5 Teknik-teknik Dasar Pemrograman Komputer. Jakarta: Mitra Wacana Media. [3] Suaraga. 2012. Algoritma dan Pemrograman. Yogyakarta: Andi. [4] Utami, Sukrisno. 2005. 10 Langkah Belajar Logika dan Algoritma, Menggunakan Bahasa C dan C++ di GNU/LINUX. Yogyakarta:Andi.
Gambar 15. Hasil Akhir Pengujian Insertion Sort dan Merge Sort Pada C++ 4.
Hasil Waktu Eksekusi Pada Java Yang di Gambarkan Dalam Bentuk Grafik
Gambar 16. Hasil Akhir Pengujian Insertion Sort dan Merge Sort Pada C++ 4. KESIMPULAN Dari hasil implementasi, pengujian dan hasil akhir dari perbandingan yang telah dilakukan dapat di simpulkan sebagaimana berikut ini: 1. Dari hasil implementasi dari kedua bahasa pemrograman baik C++ maupun Java, algoritma Insertion Sort lebih mudah untuk diterapkan dibandingkan algoritma Merge Sort karena perintah yang digunakan tidak panjang seperti perintah Merge Sort. 2. Dari hasil pengujian pada C++ diketahui bahwa algoritma Merge Sort lebih cepat dibandingakan dengan algoritma insertion sort, terutama untuk jumlah data yang dimasukan diatas dari 10000. 3. Sedangkan hasil pengujian pada Java diketahui bahwa algoritma Insertion Sort lebih cepat dibandingkan algoritma Merge Sort, terutama untuk jumlah data > 10000.
ISSN : 2338 – 8161
13
