1. Dalam
metode Searching ada yang disebut dengan Algoritma Sequential Searching.
Jelaskan!
Sequential
search adalah suatu teknik pencarian data dalam array ( 1 dimensi ) yang akan
menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.
Kemungkinan terbaik (best case) adalah jika data yang dicari terletak di indeks
array terdepan (elemen array pertama) sehingga waktu yang dibutuhkan untuk
pencarian data sangat sebentar (minimal). Kemungkinan terburuk (worst case)
adalah jika data yang dicari terletak di indeks array terakhir (elemen array
terakhir) sehingga waktu yang dibutuhkan untuk pencarian data sangat lama
(maksimal).
Prinsip
kerja dari Sequential Searching ini adalah semua data di cek oleh variabel
cari. Sequential search dibedakan menjadi dua macam yaitu Pencarian beruntun
pada larik tidak terurut dan pencarian beruntun pada larik terurut.
1. Pencarian
beruntun pada larik tidak terurut (acak)
Pencarian
dilakukan dengan memeriksa setiap elemen larik mulai dari elemen pertama sampai
elemen yang dicari ditemukan atau sampai seluruh elemen sudah diperiksa.
Diketahui
sebuah tabel TabInt [1..N] yang telah berisi nilai dengan tipe integer. Jika
pada tabel tersebut akan dicari apakah harga/nilai X ada dalam TabInt tersebut
? Maka pencarian yang akan dilakukan adalah membandingkan setiap nilai pada
tabel tersebut dengan nilai X yang dicari. Proses tersebut dilakukan secara
berurutan mulai dari elemen pertama sampai ketemu, atau sampai elemen terakhir.
Apabila niali X ditemukan maka harga/nilai indeks I di mana X diketemukan
pertama kalinya akan bernilai tidak sama dengan nol (I ¹ 0). I diberi harga 0
jika pencarian tidak ketemu. Pencarian segera dihentikan begitu harga pertama
diketemukan.
Contoh :
13 87 14 21 75 53
·
Misal
nilai yang dicari adalah X = 21, maka elemen yang diperiksa adalah 13, 87, 14,
21. (ditemukan)
Jadi
indeks larik yang dikembalikan : I = 4
·
Misal
nilai yang dicari adalah X = 15, maka elemen yang diperiksa adalah 13, 87, 14,
21, 75, 53. (tidak ditemukan)
Jadi
indeks larik yang dikembalikan : I = 0
DETAIL PROGRAM
#include <stdio.h>
#include <conio.h>
void main(){
clrscr();
int
data[21] = {13, 87, 14, 21, 75, 53};
int
cari;
int
flag=0;
printf("masukkan
data yang ingin dicari = "); scanf("%d",&cari);
for(int
i=0;i<21;i++){
if(data[i]
== cari) flag=4;}
if(flag==1)
printf("Data ada!\n");
else
printf("Data tidak ada!\n");}
2. Pencarian
beruntun pada larik terurut
Pencarian
dilakukan dengan memeriksa setiap elemen larik yang berurutan mulai dari elemen
pertama sampai elemen yang dicari ditemukan atau sampai seluruh elemen sudah
diperiksa.
Diketahui
sebuah tabel bilangan integer TabInt[1..N], yang telah diisi dan isinya terurut
membesar ( untuk setiap i anggota dari [1..N-1], Ti < T i+1). Jika pada
tabel tersebut akan dicari apakah harga/nilai X ada dalam TabInt tersebut ?
Maka pencarian yang akan dilakukan adalah membandingkan setiap nilai pada tabel
tersebut dengan nilai X yang dicari. Proses tersebut dilakukan secara berurutan
mulai dari elemen pertama sampai ketemu, atau sampai kepada elemen terakhir
atau sampai dengan harga X yang beinilai lebih besar dari nilai elemen suatu
posisi yang sedang diakses pada tabel. Apabila niali X ditemukan maka
harga/nilai indeks I di mana X diketemukan pertama kalinya akan bernilai tidak
sama dengan nol (I ¹ 0). I diberi harga 0 jika pencarian tidak ketemu.
Contoh :
55 56 78 80 100 156 199
·
Misal
nilai yang dicari adalah X = 100, maka elemen yang diperiksa adalah 55, 56, 78,
80, 100. (ditemukan)
Jadi
indeks larik yang dikembalikan : I = 5
·
Misal
nilai yang dicari adalah X = 170, maka elemen yang diperiksa adalah 55, 56, 78,
80, 100, 156, 199. (tidak ditemukan)
Jadi
indeks larik yang dikembalikan : I = 0
DETAIL
PROGRAM
#include <stdio.h>
#include <conio.h>
void main(){
clrscr();
int
data[100] = {55,56,78,80,100,156,199};
int
cari;
int
flag=0;
printf("masukkan
data yang ingin dicari = "); scanf("%d",&cari);
for(int
i=0;i<100;i++){
if(data[i]
== cari) flag=1;}
if(flag==1)
printf("Data ada!\n");
else
printf("Data tidak ada!\n");}
Ø Dari
program diatas, terlihat bahwa dilakukan perulangan untuk mengakses semua
elemen array
data satu persatu berdasarkan indeksnya.
Ø Program
menggunakan sebuah variabel flag yang berguna untuk menadai ada atau tidaknya
data yang dicari dalam array data. Hanya
bernilai 0 atau 1.
Ø Flag
pertama kali diinisialiasasi dengan nilai 0.
Ø Jika
ditemukan, maka flag akan diset menjadi 1, jika tidak ada maka flag tetap
bernilai 0.
Ø Semua
elemen array data akan dibandingkan satu persatu dengan data yang dicari dan
diinputkan oleh user.
a.
Contoh
Program
Program
pencarian ;
Uses
crt;
Label
1;
Var
L:array
[1..100] of integer;
Bil,I,n:integer;
ul:char;
procedure
tampil;
begin
write
(‘masukan banyak data:’); readln (n);
for
i:=1 to n do
begin
write
(‘data [‘,I,’] :’);readln (L [i]);
end;
end;
procedure
seq_search;
begin
write
(‘angka yang akan di cari:’);readln (bil);
i
: =1;
while
(I <n) and (L[i] <> bil) do
begin
i:=i+1;
end;
if
(L[i]=bil)then
writeln
(‘ditemukan pada elemen larik ke’,i)
else
writeln
(‘tidak ditemukan’);
end;
begin
1
:
Clrscr;
Writeln
(‘----------------------------------------------------------’);
Writeln
(‘------ PROGRAM PENCARIAN ANGKA ----‘);
Writeln
(‘----------------------------------------------------------‘);
Tampil;
Seq_search;
Writeln
;
Delay
(3000);
Write
(‘apakah anda ingin mengulangi [Y/T] ? : ‘);readln (ul);
If
(ul =’Y’) or (ul =’y’) then
Goto
1 ;
Readkey;
End
Program
Hasil
Run
2. Apa
itu Binary Search dan berikan contohnya!
Binary search adalah algoritma pencarian untuk data yang terurut. Pencarian
dilakukan dengan cara menebak apakah data yang dicari berada ditengah-tengah
data, kemudian membandingkan data yang dicari dengan data yang ada ditengah.
Bila data yang ditengah sama dengan data yang dicari, berarti data ditemukan.
Namun, bila data yang ditengah lebih besar dari data yang dicari, maka dapat
dipastikan bahwa data yang dicari kemungkinan berada disebelah kiri dari data
tengah dan data disebelah kanan data tengah dapat diabai. Upper bound dari
bagian data kiri yang baru adalah indeks dari data tengah itu sendiri.
Sebaliknya, bila data yang ditengah lebih kecil dari data yang dicari, maka
dapat dipastikan bahwa data yang dicari kemungkinan besar berada disebelah
kanan dari data tengah. Lower bound dari data disebelah kanan dari data
tengah adalah indeks dari data tengah itu sendiri ditambah 1. Demikian
seterusnya.
Metode pencarian beruntun (sequential)
maupun metode pencarian biner (binary search) dapat dipergunakan, jika:
- Nilai-nilai tersebut sudah tersusun secara berurutan.
- Nilai-nilai tersebut disusun ke dalam bentuk array atau struktur data
sejenis yang masing-masing nilai tersimpan dalam bagian-bagian yang
mempunyai indeks yang unik dan indeksnya berurutan dari yang paling kecil
hingga yang paling besar (bersifat ordinal).
Ilustrasi Binary search:
Berikut ini contoh implementasi binary search pada Pascal:
PROGRAM Pencarian_Binary_Search;
USES CRT;
CONST Max = 100;
TYPE
ArrData = ARRAY[1..Max] OF INTEGER;
PROCEDURE INPUT_DATA(var D :ArrData; N:INTEGER);
VAR
I : INTEGER;
BEGIN
FOR I:=1 TO N DO
BEGIN
WRITE('Tentukan Data ke - ',I,' : ');
READLN(D[I]);
END;
END;
{----------------------Fungsi Binary
search------------------------}
FUNCTION BINARY_SEARCH(var D :ArrData;
N,Cari:INTEGER):BOOLEAN;
VAR
L,R,M : INTEGER;
Ketemu : BOOLEAN;
BEGIN
L:=1;
R:=N;
Ketemu := False;
WHILE((L<=R) AND (Ketemu=False)) DO
BEGIN
M:=ROUND((L+R) / 2);
IF(D[M]=Cari) THEN
Ketemu:=True
ELSE IF(D[M]>Cari) THEN
R:=M-1
ELSE
L:=M+1;
END;
BINARY_SEARCH:=Ketemu;
END;
{--------------------------Program
Utama---------------------------}
VAR
Data : ArrData;
Jumlah, I, Cari : INTEGER;
BEGIN
CLRSCR;
WRITE('Tentukan Jumlah Data : ');READLN(Jumlah);
INPUT_DATA(Data, Jumlah);
WRITELN;
WRITE('Tentukan data yang ingin dicari : ');
READLN(Cari);
IF (BINARY_SEARCH(Data,Jumlah,Cari)) THEN
WRITELN('Data Ditemukan')
ELSE
WRITELN('Data Tidak Ditemukan');
READLN;
END.
3. Buatlah
kesimpulan dari metode Searching dalam Struktur Data.
Metode
Searching memiliki kelebihan dan kekurangannya masing-masing
Pencarian Sekuensial :
a.
Kelebihannya :
- Relatif
lebih cepat dan efisien untuk data yang terbatas
- Algoritma
sederhana
b.
Kekuranganya :
- Kurang
cepat untuk data dalam jumlah besar
- Beban
komputasi cenderung lebih besar
·
Pencarian Biner
:
a.
Kelebihannya :
- Untuk data
dalam jumlah besar, waktu searching lebih cepat
- Beban
komputasi lebih kecil
b.
Kekuranganya :
- Data harus sudah di-sorting lebih
dulu ( dalam keadaan terurut )
4. Apa
yang dimaksud dengan Graph.
Graph adalah kumpulan noktah
(simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis
(sisi). Graph dapat digunakan untuk merepresentasikan objek-objek
diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graph
adalah dengan menyatakan objek sebagai noktah, bulatan atau titik (Vertex),
sedangkan hubungan antara objek dinyatakan dengan garis (Edge).
5. Jelaskan
tentang Adjacency List dan Adjacency Matrix.
Adjacency List
Dalam teori graf, adjacency list merupakan
bentuk representasi dari seluruh sisi atau busur dalam suatu graf sebagai suatu
senarai. Simpul-simpul yang dihubungkan sisi atau busur tersebut dinyatakan
sebagai simpul yang saling terkait.
Dalam implementasinya, hash table
digunakan untuk menghubungkan sebuah simpul dengan senarai berisi simpul-simpul
yang saling terkait tersebut.
Gambar 3 : Undirected Cyclic
Graph
Graf pada gambar 3 dapat
dideskripsikan sebagai senarai {a,b},{a,c},{b,c}. Dan representasi adjacency
list dapat digambarkan melalui tabel di bawah ini.
Tabel 1. Representasi Adjacency
List
|
Vertex
|
Adjacency
|
Array of
Adjacent
|
|
a
|
adjacent
to
|
b,c
|
|
b
|
adjacent
to
|
a,c
|
|
c
|
adjacent
to
|
a,b
|
Salah satu kekurangan dari teknik
representasi ini adalah tidak adanya tempat untuk menyimpan nilai yang melekat
pada sisi. Contoh nilai ini antara lain berupa jarak simpul, atau beban simpul.
2.2. Adjacency Matrix
Adjacency Matrix merupakan
representasi matriks nxn yang menyatakan hubungan antar simpul dalam suatu
graf. Kolom dan baris dari matriks
ini merepresentasikan simpul-simpul, dan nilai entri dalam matriks ini
menyatakan hubungan antar simpul, apakah terdapat sisi yang menghubungkan kedua
simpul tersebut.
Pada sebuah matriks nxn, entri
non-diagonal aij merepresentasikan sisi dari simpul i dan simpul j. Sedangkan
entri diagonal aii menyatakan sisi kalang(loop) pada simpul i.
Gambar 4: Graf tak berarah berlabel
Gambar 5: Adjacency matrix
Gambar 5 merupakan adjacency matrix
yang berkorelasi dengan graf tak berarah pada gambar4. Kolom dan baris pada
matriks merupakan simpul- simpul berlabel 1-6.
Kelebihan dari adjacency matrix ini
adalah elemen matriksnya dapat diakses langsung melalui indeks, dengan begitu
hubungan ketetanggan antara kedua simpul dapat ditentukan dengan langsung.
Sedangkan kekurangan pada
representasi ini adalah bila graf memiliki jumlah sisi atau busur yang relative
sedikit, karena matriksnya bersifat jarang yaitu hanya mengandung elemen bukan
nol yang sedikit. Kasus seperti ini merugikan, karena kebutuhan ruang memori
untuk matriks menjadi boros dan tidak efisien karena komputer menyimpan elemen
0 yang tidak perlu.
