1.Apa yang anda ketahui tentang binary search tree? Jelaskan dan berikan contoh implementasi!
2.Jelaskan dan berikan langkah-langkah sorting yang ada di bawah ini;
a.Buble
b.Selection
c.Insertion
d.Shell
e.Merge
f.Quick
g.Heap
h.Bucket
i.Radix
3.Apa yang anda ketahui tentang sequential dan binary search? Berikan contoh dan jelaskan langkah-langkahnya!
4.Apa yang anda ketahui tentang BFS dan DFS? Berikan contoh dan langkah-langkahnya!
Soal shift
1.Binary Road.
Di kampung PASD terdapat keuinikan. Setiap jalan memiliki maksimal 2 cabang jalan, jalan kiri dan kanan. Di setiap cabang terdapat rumah warga. Rumah warga ini terurut seperti pada binary search tree (apa itu binary search tree?? ^_^) berdasarkan nama pemilik rumahnya.
Suatu hari terdapat seorang turis ingin mencari orang di kampung binary. Sebagai anggota kampung PASD yang baik, bantulah turis tersebut untuk mencari temannya dengan memberikan petunjuk.
Input :
Baris pertama berisi jumlah rumah (N). N baris berikutnya berisi nama pemilik rumah (Si, 1 <= i <= N). (Input akan disusun dengan algoritma BST berdasarkan nama pemilik rumah)
Baris berikutnya berisi jumlah rumah (H) yang ingin dikunjungi turis. H baris berikutnya berisi rumah yang ingin dikunjungi turis.
Output :
Berisi keterangan jalan dan rumah yang harus dilewati oleh turis dari awal hingga sampai tujuan.
Sample input :
10
Radik(input pertama menjadi posisi awal turis)
Hendrik
Rizky
Ahmad
Intan
Rahmawan
Andreas
Junian
Tegar
Simson
3
Simson
Ahmad
Radik
Sample output :
Jalan kanan, Rumah Rizky, Jalan kanan, Rumah Tegar, Jalan kiri, Anda sampai di rumah Simson.
Jalan kiri, Rumah Hendrik, Jalan kiri, Anda sampai di rumah Ahmad.
Anda sampai di rumah Radik.
Jawaban:
1.Binary Search Tree adalah salah sebuah pohon biner yang boleh kosong, dan setiap nodenya harus memiliki identifier/value. value pada semua node subpohon sebelah kiri adalah selalu lebih kecil dari value dari root, sedangkan value subpohon di sebelah kanan adalah sama atau lebih besar dari value pada root, masing – masing subpohon tersebut (kiri&kanan) itu sendiri adalah juga binary search tree.
Sebuah bst, pada dasarnya adalah sebuah pohon biner (binary tree), oleh karena itu, kita dapat melakukan traversal pada setiap node dengan metode inorder, preorder maupun postorder, dan jika kita melakukan traversal dengan metode inorder, pada dasarnya kita telah melakukan traversal valuenya secara terurut dari kecil ke besar, jadilah ini sebagai sorting algoritma.
Terdapat 3 operasi yang sangat mendasar dan juga sangat penting pada binary search tree yaitu operasi pencarian, penambahan, dan penghapusan elemen.
üOperasi Pencarian
Algoritma Cari Simpul (kunci K, pohon P) :
a.Jika pohon P kosong kembalikan nilai NULL (tak terdefinisi)
b.Jika kunci K cocok dengan kunci akar t maka kembalikan simpul P
c.Jika kunci K > kunci akar simpul P maka kembalikan nilai dari Cari Simpul (kunci K, upapohon kanan (P) ) Jika kunci K <= kunci akar simpul P maka kembalikan nilai dari Cari Simpul (kunci K, upapohon kiri (P).
üOperasi Penambahan Elemen
Algoritma Insert (kunci K, pohon P) :
a.Jika pohon P kosong maka kembalikan pohon baru dengan kunci akar = K <basis 0>
b.Jika kunci akar P = K, kembalikan P (tanpa diubah)
c.Jika kunci K > (kunci akar P,maka Insert (kunci K, upapohon kanan(P) )
d.Jika kunci K < (kunci akar P, maka Insert (kunci K, upapohon kiri(P) )
üOperasi Penghapusan Elemen
Algoritma DelNode(kunci K, pohon P) :
a.Cari simpul yang mengandung kunci K
b.Jika simpul dengan kunci K ketemu maka :
i.Jika upapohon kiri kosong maka tukar simpul P dengan upapohon kanan P, lalu hapus simpul yang sudah ditukar tersebut
ii.Jika upapohon kanan kosong maka tukar simpul P dengan upapohon kiri P, lalu hapus simpul yang sudah ditukar tersebut
2.Jenis-jenis sorting dan Algoritmanya:
a.Bubble:Suatu metode sorting termudah dengan cara membandingkan element sekarangdengan element berikutnya. Jika element sekarang lebih besar dari element berikutnyamaka kedua element tersebut ditukar, jika pengurutan tersebut adalah pengurutanascending. Jika element sekarang lebih kecil dari element berikutnya, maka keduaelement tersebut ditukar, jika pengurutan tersebut merupakan pengurutan descending.Algoritma dalam metode ini seolah-olah menggeser satu persatu element dari kanan kekiri atau kiri ke kanan, tergantung jenis pengurutannya. Ketika satu proses telah selesai,maka bubble sort akan mengulangi proses, demikian seterusnya. Bubble sort berhentijika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, sertatercapai perurutan yang telah diinginkan.
b.Selection:Merupakan kombinasi antara sorting dan searching.Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array. Misalnya untuk putaranpertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]). Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.
c.Insertion: Merupakan suatu metode pengurutan sederhana, dengan menggunakan perbandingan dimana array (data) diurutkan dalam satu entry yang dibuat dalam satu waktu. Algoritma ini kurang efisien bila digunakan pada data yang besar. Tetapi Insertion sort memberikan beberapa keuntungan seperti:
a.Efisien untuk data kecil
b.Efisien untuk set data yang sudah diurutkan secara substansial
c.Stabil dan tidak mengubah urutan relative dari element dengan tombol yang sama
Algoritma insertion sortpada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja kedua). Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada bagian lain dari array yang telah diurutkan. Langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.
d.Shell: Metode Pertambahan Menurun. Mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu sehingga dibentuk sub-list, kemudian dilakukan pertukaran jika diperlukan.Pemilihan sekuens dimulai dari N/2. Kemudian dilakukan perulangan dari j=1 – N/2, pada masing-masing pengulangan dilakukan pembandingan antara data yg ke-j dengan data ke-(j+N/2). Bila data ke-j lebih besar dari dataa ke-(j+N/2), maka tukar. Perulangan dilakukan terus smp semua data ke j selalu lebih kecil daripada data ke-(j+N/2). Proses berikutnya sama, gunakan jarak (N/2)/2 atau N/4 dan kemudian N/8 dst, hingga N=1.
e.Merge: Sebuah algoritma sorting yang menggunakan metode perbandingan berbasis. Algoritma ini dalam implementasinya merupakan salah satu algoritma yang stabil, artinya algoritma ini dapat mempertahankan urutan masukan dari element yang sama dalam output yang telah diurutkan. Algoritma tersebut ditemukan oleh John von Neumann pada tahun 1945.
Berikut menjelaskan langkah kerja dari Merge sort :
1.Divide
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
2.Conquer
Conquer setiap bagian dengan memanggil prosedur merge sort secararekursif
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.
Cara kerja algoritma merge sort adalah membagi larik data yang diberikan menjadi dua bagian yang lebih kecil. Kedua larik yang baru tersebut kemudian akan diurutkan secara terpisah. Setelah kedua buah list tersusun, maka akan dibentuk larik baru sebagai hasil penggabungan dari dua buah larik sebelumnya. Menurut keefektifannya, alogaritma ini bekerja dengan tingkat keefektifan O(nlog(n)).
f.Quick: Quick Sort adalah sebuah algoritma sortir dari model Divide and Conquer yaitu dengan cara mereduksi tahap demi tahap sehingga menjadi 2 bagian yang lebioh kecil. Langkah – langkahnya yaitu pertama kita harus mengidentifikasi key pada indeks pertama dalam list. Kemudian list dipartisi menjadi 2 bagian dimana list yang sebelah kiri adalah kumpulan dari key-key yang lebih kecil dari key pada indeks pertama dan listyang disebelah kanan adalah kumpulan dari key-key yang lebih besar dari key pada indeks pertama. Seperti pada merge sort, algoritma ini juga berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai berikut :
1.Divide
Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.
2.Conquer
Mengurutkan elemen pada sub-rangkaian secara rekursif Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array.
g.Heap: Binary heap digunakan sebagai struktur data dalam algoritma Heap-Sort. Sebagaimana diketahui, ketika suatu Heap dibangun maka kunci utamanya adalah node atas selalu mengandung elemen lebih besar dari kedua node dibawahnya. Apabila elemen berikutnya ternyata lebih besar dari elemen root, maka harus di swap dan lakukan proses heapify lagi. Root dari suatu Heap Sort mengandung elemen terbesar dari semua elemen dalam Heap. Proses Heap Sort dapat dijelaskan sebagai berikut:
1.Representasikan Heap dengan n elemen dalam sebuah array A[n]
2.Elemen root tempatkan pada A[1]
3.Elemen A[2i] adalah node kiri dibawah A[i]
4.Elemen A[2i+1] adalah node kanan dibawah A[i]
5.Ambil nilai root (terbesar) A[1..n-1] dan pertukarkan dengan elemen terakhirdalam array, A[n]
6.Bentuk Heap dari (n-1) elemen, dari A[1] hingga A[n-1]
7.Ulangi langkah 5 dimana indeks terakhir berkurang setiap langkah.
h.Bucket: Merupakan algoritma sorting yang bekerja dengan memartisi array menjadi beberapa bagian yang diimplementasikan sebagai beberapa buah ember. Setiap ember diurut satu persatu dengan menggunakan algoritma sorting yang berbeda atau dengan rekursif pada suatu ember.
Algoritma:
a.Membuat suatu array dengan menginisialisasikannya dengan nama “ember”
b.Taruh setiap data pada ember
c.Urutkan setiap ember yang berisi data.
d.Cek ember satu per satu dengan terurut dan taruh seluruh element pada array yang asli
i.Radix: Radix Sorting adalah metode sorting yangajaib yang mana mengatur pengurutan nilai tanpa melakukan beberapa perbandingan pada data yang dimasukkan. Secara harfiah, radix dapat diartikan sebagai posisi dalam angka. Pada sistem desimal, radix adalah digit dalam angka desimal. Seperti contoh, angka “42” mempunyai 2 digit yaitu 4 dan 2. Radix Sort memperoleh namanya dari digit-digit tersebut, karena metode ini pertama kalinya mengurutkan nilai-nilai input berdasarkan radix pertamanya, lalu pengurutan dilakukan berdasarkan radix keduanya, begitu juga seterusnya.
Sorting dilakukan dengan :
ümembagi data set ke sub-sub data set sesuai dengan harga radixnya, kemudian
ümenyatukannya subset subset tersebut menjadi satu set kembail (hanya mekonkatenasi) untuk dilakukan pembagian berikutnya berdasarkan radix yang lebih signifikan.
Setelah radix demi radix dilakukan, mulai dari radix yang paling tidak signifikan ke yang paling signifikan, maka kemudian akan dihasilkan data terurut.
3.Pengertian tentang Sequential Search dengan Binary Search
ØSequential Search :merupakan suatu metode pencari nilai data pada suatu daftar, proses dalam metode ini terdiri dari pengecekan setiap element dalam satu waktu sampai data yang diinginkan ditemukan. Metode ini merupakan salah satu algoritma yang paling mudah, karena pada beberapa permasalahan kita juga dapat menggunakan metode brute force dalam algoritma ini.
Diketahui ada data {8,10,6,-2,10,7,1,100} Dan kemudian sub data yang ingin dicari adalah misalnya angka 1. Seperti pada tabel di bawah ini :
Array
0
1
2
3
4
5
6
7
DATA
8
10
6
-2
10
7
1
100
TARGET
1
Maka Sesuai dengan permintaan di atas pada bagian Pencarian maka langkah penemuannya adalah :
1.Bandingkan data pada array 0 dengan Target. ternyata 8 != 1, maka lanjutkan ke array selanjutnya.
2.Sekarang data pada array 1 dibandingkan dengan Target. ternyata juga 10 != 1, makalanjut
Begitu seterusnya sampai berhenti pada Array ke 6. karena nilai array ke 6 = target, maka tampilkan data pada array ke 6.
ØBinary search :merupakan sebuah teknik untuk menemukan nilai tertentu dalam sebuah larik (array) linear, dengan menghilangkan setengah data pada setiap langkah. Sebuah pencarian biner mencari nilai tengah (median), melakukan sebuah pembandingan untuk menentukan apakah nilai yang dicari ada sebelum atau sesudahnya, kemudian mencari setengah sisanya dengan cara yang sama.
Prinsip pencarian biner adalah :
üData diambil dari posisi 1 sampai posisi akhir N
üKemudian cari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2
üKemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?
üJika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1
üJika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1
üJika data sama, berarti ketemu.
Contoh Data:
Misalnya data yang dicari 17
Karena 17 > 15 (data tengah), maka: awal = tengah + 1
Karena 17 < akhir =" tengah">
Karena 17 = 17 (data tengah), maka KETEMU!
4.Pengertian BFS dengan DFS:
vBFS (Breadth First Search) : merupakan suatu algoritma pencari dalam graf yang dimulai pada node root dan menjelajah seluruh node tetangganya. Lalu untuk seluruh node terdekat, mereka akan menjelajah ke node-node tetangga yang belum dijelajah dan seterusnya sampai menemukan tujuan akhirnya. Metode ini bertujuan untuk menjelajah seluruh node dari suatu graf atau kombinasi dari sekuens dengan sistem pencari melewati seluruh solusi. Dengan kata lain, metode ini adalah suatu metode yang cukup boros karena mencari seluruh graf atau sekuens tanpa berpikir tentang hasil akhir. Dari root, seluruh node child didapat dengan menjelajah node lain dengan mengunakan FIFO (first in first out) queue.
Algoritma BFS:
1.Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi (goal node),maka stop.
2.Jika Q kosong, tidak ada solusi. Stop.
3.Ambil simpul v dari kepala (head) antrian, bangkitkan semua anak-anaknya. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di belakang antrian.
Jika suatu simpul anak dari v adalah simpul solusi, maka solusi telah ditemukan, kalau tidak kembali lagi ke langkah 2.
vDepth-first search (DFS) melakukan pencarian secara preorder. Mengunjungi anak suatu simpul sebelum simpul tetangganya. Berkaitan dengan mesin pencari, DFS ini cenderung mengindeksdokumen berdasarkan suatu link.
Algoritma DFS:
1.Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi, makaStop.
2.Jika Q kosong, tidak ada solusi. Stop.
3.Ambil simpul v dari kepala (head) antrian.
4.Jika kedalaman simpul v sama dengan batas kedalaman maksimum, kembali ke langkah 2.
5.Bangkitkan semua anak dari simpul v. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di awal antrian Q.
6.Jika anak dari simpul v adalah simpul tujuan, berarti solusi telah ditemukan, kalau tidak, kembalilagi ke langkah 2.
Contoh :
Sebuah bidak (pion) bergerak di dalam sebuah matriks pada Gambar 6.11. Bidak dapat memasuki elemen matriks mana saja pada baris paling atas.Dari elemen matriks yang berisi 0, bidak dapat bergerak ke bawah jika elemen matriks di bawahnya berisi 0; atau berpindah horizontal (kiri atau kanan) jika elemen di bawahnya berisi 1. Bila bidak berada pada elemen yang berisi 1, ia tidak dapat bergerak kemanapun.Tujuan permainan ini adalah mencapai elemen matriks yangmengandung 0 pada baris paling bawah.
1
2
3
4
1
1
0
0
0
2
0
0
1
0
3
0
1
0
0
4
1
0
0
0
Gambar 6.11Matriks bidak
Operator yang digunakan:
DOWN pindahkan bidak satu posisi ke bawah
LEFT pindahkan bidak satu posisi ke kiri
RIGHT pindahkan bidak satu posisi ke kanan
Batas kedalaman maksimum pohon ruang status diandaikan 5.
