Makalah Algoritma Sorting Binary Insertion Sort PDF

Preview

Summary

Makalah Algoritma Sorting Binary Insertion Sort Mata Kuliah Praktek Algoritma Pemrograman Disusun oleh: Isnainul Fahrizal 14520244007 Defriansyah 14520249003 Pendidikan Teknik Informatika Pendidikan Teknik Elektronika Fakultas Teknik Universitas Negeri Yogyakarta Desember, 2014 Pengertian Pada dasar...

Description

Makalah Algoritma Sorting

Binary Insertion Sort Mata Kuliah Praktek Algoritma Pemrograman

Disusun oleh: Isnainul Fahrizal

14520244007

Defriansyah

14520249003

Pendidikan Teknik Informatika Pendidikan Teknik Elektronika Fakultas Teknik Universitas Negeri Yogyakarta Desember, 2014

Pengertian Pada dasarnya metode Binary Insertion Sort adalah metode Insertion Sort yang menggunakan Binary Search agar jumlah proses perbandingan data dapat dikurangi. Sehingga Binary Insertion Sort ini dapat dikatakan lebih efisien / powerful dari pada Insertion Sort biasa. Sebelum mempelajari tentang apa itu Binary Insertion Sort dan cara kerjanya. Terlebih dahulu pahami tentang Insertion Sort dan Binary Search karena Binary Insertion Search adalah kombinasi dari keduanya. A. Insertion Sort Insertion (Indonesia: penyisipan) Sort seperti namanya metode sorting ini menyisipkan data ke tempat yang seharusnya, secara satu persatu setiap langkahnya. Jika dianalogikan dalam kehidupan sehari-hari, metode Insertion Sort ini seperti ketika bermain kartu (playing cards). Setiap giliran, seorang pemain akan mengambil sebuah kartu dari tumpukan (deck) yang sudah di kocok / acak. Kartu yang akan disisipkan

Deck Kartu Acak Kartu di tangan yang sudah urut Gambar 1. Gambar ilustrasi Insertion Sort. Sederhana, namun metode ini kurang efisien apabila digunakan untuk mengurutkan data yang sangat banyak daripada algoritma-algoritma yang

lebih rumit seperti quicksort, heapsort, atau merge sort. Akan tetapi Insertion Sort mempunyai kelebihannya sendiri, diantaranya : 

Efisien untuk data yang jumlahnya relatif kecil.



Lebih efisien daripada algoritma sederhana lain seperti selection sort atau bubble sort.



Efisien untuk data yang tidak terlalu acak. Karena, setiap tempat untuk menyisipkan sudah ditemukan, maka perbandingan akan berhenti. Tidak perlu mengulang berkali-kali seperti bubble sort.



Hanya membutuhkan jumlah memori yang sedikit.



Dapat langsung mengurutkan tanpa harus memeriksa dari awal apabila ada data baru yang dimasukkan.

B. Binary Search Disebut Binary Search karena sesuai namanya Binary yang artinya dua adalah metode pencarian data yang bertujuan untuk mengurangi jumlah perbandingan data dengan membagi dua sebuah array berdasarkan nilai tengahnya. Sehingga dapat diprediksi letak data tersebut di bagian kanan atau bagian kiri, tanpa harus membandingkan seluruh elemen yang ada. Bandingkan

Jika lebih kecil

Jika lebih besar

Gambar 2. Gambar ilustrasi Binary Search.

Pada gambar di atas untuk mencari nilai tengah dari searray dapat bermacam-macam caranya. Jika datanya ganjil nilai tengahnya adalah jelas. Misal seperti gambar di atas, sudah ada tujuh data yang sudah terurut. Untuk mencari nilai tengahnya tinggal menggunakan rumus matematika : posisiTengah =

jumlah data + 1 7 + 1 = =4 2 2

Apabila jumlah data yang sudah terurut genap, maka pada kasus tertentu harus ada penanganan seperti pembulatan ke bawah atau ke atas agar data yang dipilih sebagai nilai tengah untuk perbandingan menjadi jelas.

Konsep Binary Insertion Search Dengan menggunakan Binary Search pada Insertion Sort, kita dapat meminimalisir jumlah perbandingan data. Sekarang pertanyaannya adalah "mengapa bisa demikian?". Karena misal pada pengurutan data Ascending (dari kecil ke besar) kemungkinan terburuk dari Insertion Sort adalah apabila data yang akan disisipkan bernilai kecil, sedangkan isi array-nya banyak mungkin bisa ribuan. maka kita juga harus membandingkan ribuan data dari yang paling besar ke kecil sampai titik temunya. Namun bayangkan apabila kita dapat memprediksi dimana seharusnya data, tersebut berada, pasti proses penyisipan akan lebih cepat. Di situlah nantinya Binary Search digunakan. Apabila data yang akan disisipkan lebih kecil dari data tengah maka data tersebut sudah pasti berada pada bagian kiri (awal sampai tengah) array, maka tidak perlu lagi membandingkan dari akhir array. Cukup mulai membandingkan dari titik tengah array ke titik awal array. Sehingga jumlah perbandingan yang sampai ribuan data tadi dapat dikurangi menjadi setengahnya. Jika berkurang setengah dirasa masih kurang dan ingin membaginya lagi, maka Binary Search ini dapat dibuat bertingkat sehingga mendapatkan jumlah perbandingan data yang seminimal mungkin.

Contoh Perbedaan Penyisipan Data data yang bernilai 3 akan disisipkan pada sebuah array data. A. Normal Insertion Sort step

Array ← data

Keterangan :

1.

[1,2,4,7,9,12,13] ← [3]

3 < 13 ? benar. lanjut ke kiri.

2.

[1,2,4,7,9,12,13] ← [3]

3 < 12 ? benar. lanjut ke kiri.

3.

[1,2,4,7,9,12,13] ← [3]

3 < 9 ? benar. lanjut ke kiri.

4.

[1,2,4,7,9,12,13] ← [3]

3 < 7 ? benar. lanjut ke kiri.

5.

[1,2,4,7,9,12,13] ← [3]

3 < 4 ? benar. lanjut ke kiri.

6.

[1,2,4,7,9,12,13] ← [3]

3 < 2 ? salah. berhenti.

7. 8.

[1,2,i,4,7,9,12,13] ← [3] [1,2,3,4,7,9,12,13] ← [x]

Geser data 4-13 ke kanan Sisipkan 3 ke i. x adalah data. acak selanjutnya jika ada.

B. Binary Insertion Sort step 1.

Array ← data [1,2,4,7,9,12,13] ← [3]

Keterangan : Mencari titik tengah. (7+1)/2 = data ke 4 = 7

2.

[1,2,4,7,9,12,13] ← [3]

Bandingkan 3 & 7. 3 < 7?. benar bandingkan ke kiri.

3.

[1,2,4,7,9,12,13] ← [3]

3 < 4? benar. lanjut ke kiri.

4.

[1,2,4,7,9,12,13] ← [3]

3 < 2? salah. berhenti.

5.

[1,2,i,4,7,9,12,13] ← [3]

Geser data 4-13 ke kanan.

6.

[1,2,3,4,7,9,12,13] ← [x]

Sisipkan 3 ke i. x adalah data. acak selanjutnya jika ada.

Dari contoh di atas dapat dilihat bahwa perbandingan untuk 9, 12, dan 13 telah dilewati dan kita dapat menghemat 2 langkah. Untuk array yang kecil memang tidak begitu terasa signifikan. Akan tetapi apabila jumlah datanya banyak, penggunaan Binary Search pada Insertion Sort akan sangat membantu.

Kesimpulan Binary Insertion Sort adalah sebuah metode pengurutan data / sorting yang merupakan penggabungan dan pengembangan dari metode Insertion Sort biasa dengan Binary Search, sehingga proses sorting dapat berjalan dengan lebih optimal. Insertion Sort sesuai namanya metode penyisipan yaitu metode pengurutan data dengan menyisipkan sebuah data/lebih pada sekumpulan data yang sudah terurut. Pada kehidupan sehari-hari secara tidak sadar metode Insertion Sort ini sering digunakan pada saat bermain kartu apabila pemain mengurutkan kartunya setiap mengambil dari tumpukan kartu yang acak. Binary Search merupakan salah satu metode pencarian data dengan membagi sekumpulan data menjadi dua bagian dari data tengah supaya pencarian dapat lebih efisien. Penggunaan Binary Search pada Insertion Sort (disebut Binary Insertion Sort) dapat dikatakan seperti ini. Katakanlah sebuah data akan dimasukkan ke dalam sebuah array data. Maka agar data dan array data dapat disatukan dengan terurut, kita harus mencari posisi yang tepat untuk menyisipkan data tersebut pada array data. Proses pencarian ini menggunakan Binary Search. Setelah data dibagi dua dari nilai tengahnya, bandingkan data tersebut dengan data tengah. Apabila data yang akan disisipkan lebih besar dari data tengah maka cari tempat ke sebelah kanan, sebaliknya cari tempat ke sebelah kiri. Dengan begitu proses perbandingan data dapat dikurangi. Proses binary search ini seperti proses prediksi.

Daftar Pustaka Cetak:Buku, Modul Jon Bentley. 2000. Programming Pearls. Addison-Wesley. Adi. 2008.Jobsheet Algoritma Pemrograman: Sorting 2.FTUNY.

Web:Jurnal, Video, Gambar GeeksQuiz. 7 Maret 2013. Insertion Sort. url:http://geeksquiz.com. diakses pada 17 Maret 2015. GeeksQuiz. 28 Juli 2014. Binary Insertion Sort. url:http://geeksquiz.com. diakses pada 17 Maret 2015. APCS. APCS - Day 4 - Insertion Sort and Binary Search url:https://www.youtube.com/watch?v=_zgrsdFHljM. diakses pada 17 Maret 2015. Wikipedia. Insertion sort. url:http://en.wikipedia.org/wiki/Insertion_sort. diakses pada 17 Maret 2015. Wikipedia. Binary search. url:http://en.wikipedia.org/wiki/Binary_search_algorithm. diakses pada 17 Maret 2015. Byron Knoll. PNG-cards-1.3 Vector Playing Cards. url:

http://www.byronknoll.com/. diakses pada 17 Maret 2015....