Algoritma Binary Search

A. Pengertian
Binary Search adalah algoritma pencarian yang lebih efisien daripada algorima Sequential Search. Hal ini dikarenakan algoritma ini tidak perlu menjelajahi setiap elemen dari tabel. Kerugiannya adalah algoritma ini hanya bisa digunakan pada tabel yang elemennya sudah terurut baik menaik maupun menurun.
Pada intinya, algoritma ini menggunakan prinsip divide and conquer, dimana sebuah masalah atau tujuan diselesaikan dengan cara mempartisi masalah menjadi bagian yang lebih kecil. Algoritma ini membagi sebuah tabel menjadi dua dan memproses satu bagian dari tabel itu saja.
Algoritma ini bekerja dengan cara memilih record dengan indeks tengah dari tabel dan membandingkannya dengan record yang hendak dicari. Jika record tersebut lebih rendah atau lebih tinggi, maka tabel tersebut dibagi dua dan bagian tabel yang bersesuaian akan diproses kembali secara rekursif.

B. Keunggulan
Keunggulan utama dari algoritma binary search adalah kompleksitas algoritmanya yang lebih kecil daripada kompleksitas algoritma sequential search. Hal ini menyebabkan waktu yang dibutuhkan algoritma binary search dalam mencari sebuah record dalam sebuah tabel lebih kecil daripada waktu yang dibutuhkan algoritma sequential search.

C. Fungsi
Pencarian Biner (Binary Search) dilakukan untuk :
1. memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.

2. Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).

3. Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.


ALGORITMA

Kamus
Const N : integer = 8 { misalkan jumlah elemen array maksimum = 8 }
Type A = array [ 1 ..... N ] of integer
Cari, BatasAtas, BatasBawah, Tengah : Integer
Ketemu : boolean
ALGORITMA
Input (cari) { meminta nilai data yang akan dicari}
BatasAtas  1 { indeks array dimulai dari 1 }
BatasBawah  N
Ketemu  False
While (BatasAtas < BatasBawah) and (not ketemu) do
Tengah  (BatasAtas + BatasBawah) div 2
If A [Tengah] = cari then
Ketemu  true
Else
If ( A [Tengah] < cari ) then { cari di bagian kanan }
BatasAtas  Tengah + 1
Else
BatasBawah  Tengah – 1 { cari di bagian kiri }
Endif
Endif
EndWhile
If (ketemu) then
Output ( ‘Data berada di index nomor’, Tengah )
Else Output ( ‘Data tidak ditemukan’ )
Endif


CONTOH

Contoh Nilai-Nilai data yang sudah terurut :

A 2 5 8 12 15 25 37 57
1 2 3 3 5 6 7 8

Kasus 1 : cari = 12
Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 8) div 2 = 4
A [Tengah] = A [4] = 12, berarti loop pertama data langsung ditemukan

Kasus 2 : cari = 15
Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 8) div 2 = 4
A [Tengah] = A [4] = 12 < cari = 15, berarti BatasAtas = Tengah + 1 = 4 + 1 = 5
Loop kedua : Tengah = (BatasAtas + BatasBawah) div 2 = (5 + 8) div 2 = 6
A [Tengah] = A [6] = 25 > cari = 15, berarti BatasBawah = Tengah - 1 = 6 - 1 = 5
Loop ketiga : Tengah = (BatasAtas + BatasBawah) div 2 = (5 + 5) div 2 = 5
A [Tengah] = A [5] = 15, berarti setelah loop ketiga, data ditemukan

Kasus 3 : cari = 10
Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 8) div 2 = 4
A [Tengah] = A [4] = 12 > cari = 10, berarti BatasBawah = Tengah - 1 = 4 - 1 = 3
Loop kedua : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 3) div 2 = 2
A [Tengah] = A [2] = 5 < cari = 10, berarti BatasAtas = Tengah + 1 = 2 + 1 = 3
Loop ketiga : Tengah = (BatasAtas + BatasBawah) div 2 = (3 + 3) div 2 = 3
A [Tengah] = A [3] = 8, berarti setelah loop ketiga, data tidak ditemukan

Untuk jumlah data sebanyak n, maka proses pembandingan maksimal sebanyak ( log n ) kali. Untuk contoh di atas, jumlah data 8, maka proses pembandingan maksimal sebanyak 3 kali.

Algoritma Divide dan Conquer

Divide and Conquer adalah metode pemecahan

masalah yang bekerja dengan membagi masalah menjadi

beberapa upa-masalah yang lebih kecil, kemudian

menyelesaikan masing-masing upa-masalah tersebut

secara independen, dan akhirnya menggabungkan solusi

masing-masing upamasalah sehingga menjadi solusi dari

masalah semula.

Pada algortima Divide and Conquer ini meiliki tiga proses

utama yaitu:

- Divide: membagi masalah menjadi beberapa upamasalah

yang memiliki kemiripan dengan masalah semula namun

berukuran lebih kecil (idealnya berukuran hampir sama),

- Conquer: memecahkan (menyelesaikan) masingmasing

upa-masalah (secara rekursif), dan

- Combine: mengabungkan solusi masing-masing upamasalah

sehingga membentuk solusi masalah semula.

Pada algoritma ini, tiap-tiap upa-masalah mempunyai

karakteristik yang sama (the same type) dengan

karakteristik masalah asal, sehingga metode Divide and

Conquer lebih natural diungkapkan dalam skema rekursif.

Secara umum, algoritma Divide and Conquer memiliki

sekema sbb:

procedure DIVIDE_and_CONQUER(input n :

integer)

{ Menyelesaikan masalah dengan

algoritma Dand-

C.

Masukan: masukan yang berukuran n

Keluaran: solusi dari masalah semula

}

Deklarasi

r, k : integer

Algoritma

if n ≤ n0 then {ukuran masalah sudah

cukup

kecil }

SOLVE upa-masalah yang berukuran n ini

else

Dalam Algoritma divide dan conquer Pemrogram bertanggung jawab atas implementasi solusi. Pembuatan program akan menjadi lebih sederhana jika masalah dapat dipecah menjadi sub masalah - sub masalah yang dapat dikelola.

Penyelesaian masalah dengan komputer berhadapan dengan 4 hal, yaitu :

1. Pemahaman keterhubungan elemen-elemen data yang relevan terhadap solusi secara menyeluruh.

2. Pengambilan keputusan mengenai operasi-operasi yang dilakukan terhadap elemen-elemen data.

3. Perancangan representasi elemen-elemen data di memori sehingga memenuhi kriteria berikut:

a. Memenuhi keterhubungan logik antara elemen-elemen data.

b. Operasi-operasi terhadap elemen-elemen data dapat dilakukan secara mudah dan efisien.

4. Pengambilan keputusan mengenai mengenai bahasa pemrograman terbaik untuk menerjemahkan solusi persoalan menjadi program.

STRATEGI DIVIDE DAN CONQUER

Metode

Strategi Divide dan Conquer memecah masalah menjadi submasalah-submasalah independen yang lebih kecil sehingga solusi submasalah-submasalah dapat diperoleh secara mudah, solusi submasalah-submasalah digabung menjadi solusi seluruh masalah.

Skema umum algoritma divide dan conquer

Procedure DNC ( i,j : integer )

Var K : integer ;

If SMALL (i,j) then SOLVE (i,j)

Else begin

K : = DIVIDE (i,j)

COMBINE (DNC(i,k),DNC(k+1,j))

End if

Keterangan :

1. SMALL adalah fungsi yang mengirim BOOLEAN, menentukan apakah ukuran telah cukup kecil sehingga solusi dapat diperoleh. Ukuran dinyatakan sebagai telah berukuran kecil bergantung masalah.

2. DIVIDE adalah fungsi membagi menjadi 2 bagian pada posisi K. Biasanya bagian berukuran sama.

3. COMBINE adalah fungsi menggabungkan solusi X dan Y submasalah. Solusi diperoleh dengan memanggil prosedur rekursif DNC.

Jika ukuran kedua submasalah sama, waktu komputasi DNC dideskripsikan hubungan rekuren berikut :

T(n) = g (n), n kecil

2 T (n/2) + f (n), selainnya

dimana :

· T(n) adalah waktu untuk DNC dengan n masukan,

· g(n) adalah waktu komputasi jawaban secara langsung untuk masukan kecil dan

· f(n) adalah waktu COMBINE.

Untuk algoritma divide dan conquer yang menghasilkan submasalah-submasalah dengan tipe masalah yang sama dengan masalah awal, sangat alami untuk mendeskripsikan algoritma secara rekursi. Kemudian untuk meningkatkan efisiensi dilakukan penerjemahan menjadi bentuk iterasi.

Pemakaian teknik Divide dan Conquer banyak digunakan dalam menyelesaikan berbagai macam persoalan, antara lain :

1. Searching

2. Sorting

Sumber : http://pdflost.com/download/5991507/

Algoritma Kruskall

Contoh : Pandang sebuah graph sebagai berikut;

Algoritma Kruskall

Dasar pembentukan algoritma Kruskal berasal dari analogi growing forest. Growing forest maksudnya adalah untuk membentuk pohon merentang minimum T dari grafG adalah dengan cara mengambil satu per satu sisi dari graf G dan memasukkannya ke dalam pohon yang telah terbentuk sebelumnya. Seiring dengan berjalannya iterasi untuk setiap sisi, maka forest akan memiliki pohon yang semakin sedikit. Oleh sebab itu, maka analogi ini disebut dengan growing forest. Algoritma Kruskal akan terus menambahkan sisi – sisi ke dalam hutan yang sesuai hingga akhirnya tidak akan ada lagi forest dengan, melainkan hanyala

h sebuah pohon yang merentang minimum.Soal diatas dapat dijawab dengan menggunakan Algoritma Kruskall seperti ditunjukkan dibawah ini :.

-------Edge----- Cost

1. ( 1,2 )----- 10
   
2. ( 3,6 )----- 15
   
3. ( 4,6 )----- 20
   
4. ( 2,6 )----- 25
   
5. ( 1,4 )----- 30
6. ( 3,5 )----- 35

Maka Spanning Tree- nya adalah

Sehingga total costnya ialah 105

Tugas: (minimum spanning tree dan total cost nya)

TEKNIK SORTING DAN SEARCHING

Teknik Sorting

Sorting bisa didefinisikan sebagai suatu proses pengurutan data yang
sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut
suatu aturan tertentu. Sorting yang kita terapkan menggunakan tipe data array agar
pemahaman serta pengimplementasiannya lebih mudah. Pada umumnya terdapat
dua jenis pengurutan :
- Ascending (Naik).
- Descending (Turun).
Contoh :
Data : Array [1..6] of Byte = (22, 10, 15, 3, 8, 2);
Data Acak : 22 10 15 3 8 2
Terurut Ascending : 2 3 8 10 15 22
Terurut Descending : 22 15 10 8 3 2

Metode Pengurutan Data
- Pengurutan berdasarkan perbandingan (comparison-based sorting)
• Bubble sort, exchange sort
- Pengurutan berdasarkan prioritas (priority queue sorting method)
• Selection sort, heap sort
- Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep
sorted method)
• Insertion sort, tree sort
- Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer
method)
• Quick sort, merge sort
- Pengurutan berkurang menurun (diminishing increment sort method)
• Shell sort

Teknik Searching
Searching merupakan suatu proses pendarian data dari sejumlah data yang
ada. Pencarian data dapat dilakukan pada sejumlah data yang sudah terurut atau
juga pada data yang sama sekali belum terurut. Kita mencoba menggunakan dua
metode pencarian yaitu :
- Pencarian Berurutan (Sequential Searching).
Metode ini merupakan metode paling sederhana, secara garis besar metode
ini bisa dijelaskan sebagai berikut. Dari data yang diketahui, data yang dicari
dibandingkan satu per satu sampai data tersebut ditemukan atau tidak ditemukan.
Pada saat data yang dicari sudah ditemukan, maka proses pencarian langsung
dihentikan. Tetapi jika belum ditemukan, maka pencarian diteruskan sampai
seluruh data dibandingkan.

- Pencarian Biner (Binary Seacrh).
Metode ini digunakan jika sejumlah data telah diurutkan. Jika dibandingkan
dengan metode awal tadi metode ini jauh lebih cepat. Secara garis besar metode
ini bisa dijelaskan sebagai berikut. Urutkan dahulu sejumlah data. Lalu bagi dua
data-data tadi dengan jumlah data yang sama pada masing-masingnya. Kemudian
data dibandingkan dengan data terakhir dari subdata yang pertama. Jika data yang
dicari lebih keci, pencarian dilanjutkan pada sub data pertama dengan terlebih
dahulu membagi dua lagi data-data tersebut dengan jumlah yang sama. Tetapi jika
data yang dicari lebih besar dari data terakhir subdata pertama, berarti data yang
dicari kemungkinan terletak pada subdata yang kedua. Proses diatas dilakukan
berulang sampai data ditemukan atau tidak ditemukan.

STRUKTUR DATA

Struktur data adalah kelompok item data yang terorganisasi yang dianggap sebagai salah satu unit, struktur data disebut juga jenis data kompleks.

Beberapa sturktur data

1. Array
array merupakan set item data yang disusun secara baik menjadi rangkaian dan diacu atau ditunjuk oleh suatu identifier.
contoh : Nilai = (46 78 56 79)

klasifikasi array
- array 1 dimensi
- array multi dimensi

pendeklarasian array
- array 1 dimensi
variable
Nilai : array [1 . . 5] of integer
A : array [1. . 4] of real

-array multi dimensi
Variable
A : array [1 . . 5, 1 . . 2] of integer

2. String
string merupakan karakter yang ditangani sebagai unit data tunggal.
contoh :
variable string
- A : "universitas"
- B : "gunadarma"

klasifikasi string
-fixed length string
yaitu string yang mempunyai jumlah tempat karakter yang tetap yang tersedia, bisa digunakan untuk penyimpanan data.
-viriable length string
yaitu string untuk memberi data sejumlah spasi (ruang) sesuai yang diperlukan.

pendeklarasian string
-fixed length string
variables
Nama : string [5]
-variables length string
Nama : string

PERBANDINGAN BAHASA PEMROGRAMAN

1. Bahasa C

Aplikasi bahasa C :

• Bahasa C pertama kali digunakan di Computer Digital Equipment Corporation PDP-11 yang menggunakan system operasi UNIX.

• Bahasa C juga digunakan untuk menyusun operasi Linux

• Banyak bahasa pemrogaman popular seperti PHP dan Java menggunakan sintaks dasar mirip bahasa C.

Kelebihan dan Kekurangan Bahasa C

Kelebihan Bahasa C

• Bahasa C tersedia hampir di semua jenis computer

• Kode bahasa C sifatnya adalah portable dan fleksible untuk semua jenis computer

• Bahasa C hanya menyediakan sedikit kata-kata kunci, hanya terdapat 32 kata kunci

• Proses executable program bahasa C lebih cepat

• Dukungan pustaka yang banyak

• C adalah bahasa yang terstruktur

• Bahasa C termasuk bahasa tingkat menengah

Kekurangan Bahasa C

• Banyaknya operator serta fleksibilitas penulisan program kadang-kadang membingungkan pemakai

• Bagi pemula pada umumnya akan kesulitan menggunakan pointer

2. Bahasa Pascal

Aplikasi Bahasa Pascal

• Pascal dipakai sebagai landasan pembuatan kode perangkat lunak Delphi (berbasis windows)

• Pascal dipakai sebagai landasan pembuatan kode perangkat lunak Kylix (berbasis Linux)

Kelebihan dan kekurangan

Kelebihan bahasa pascal :

• Tipe data standar, tipe-tipe data standar yang telah tersedia bahasa pemrogaman. Pascal memiliki tipe data standar Boolean, integer, char, real, string.

• User defined data types, programmer dapat membuat tipe data lain yang diturunkan dari tipe data standar.

• Strongly-typed, programmer harus menentukan tipe data dari suatu variable dan variable tersebut tidak dapat dipergunakan untuk menyimpan tipe data selain format yang ditentukan.

• Terstruktur, memiliki sintaks yang memungkinkan penulisan program dipecah menjadi fungsi-fungsi kecil (procedur dan function) yang dapat dipergunakan berulang-ulang.

• Sederhana dan ekspresif, memiliki struktur yang sederhana dan sangat mendekati bahasa manusia (bahasa inggris) sehingga mudah dipelajari dan dipahami.

Kekurangan bahasa pascal :

• Versi awal Pascal kurang cocok untuk aplikasi bisnis karena dukungan basisdata yang terbatas.

• Sintaks Pascal terlalu bertele-tele

• Tidak mendukung pemrograman berorientasi objek

• Pascal tidak fleksibel dan banyak kekurangan yang dibutuhkan untuk membuat aplikasi yang besar.

3. Bahasa Cobol

Aplikasi bahasa COBOL

• Untuk membuat aplikasi bisnis

• Untuk pengolahan data dan database

Kelebihan dan Kekurangan

Kelebihan :

• Program COBOL dibuat dalam instruksi bahasa inggris, sehingga lebih mudah dipelajari dan dibuat.

• Program COBOL sesuai untuk pengolahan data yang banyak diterapkan pada permaslahan .

• Program COBOL sifatnya standard, sehingga dapat dipergunakan pada komputer-komputer yang berbeda, tanpa banyak perbedaan.

• Struktur program COBOL jelas, sehingga dapat dimengerti oleh orang seperti akuntan, auditor, atau manajer-manajer yang hanya mempunayai pengetahuan pengolahan data yang sedikit.

• COBOL menyediakan fasilitas Listing Program, bilamana perlu dapat diperiksa oleh orang lain selain programer.

• Mudah didokumentasikan dan dikembangkan bilamana perlu

• Problem Orientad Language

Kekurangan :

• Operasi masukan dan keluaran yang masih kaku

• Struktur penulisan program yang sangat kaku dan bertele-tele

( sumber : http://ndet.wordpress.com/2008/04/12/bahasa-pemrograman/ )