ALGORITMA DAN PEMROGRAMAN 2
3 SKS
By : Sri Rezeki Candra Nursari
MATERI Teks/string Pointer File Struktur Kelas/Class Konstruktor dan Destruktor • Kelas dan Obyek • • • • • •
Overloading Operator Inheritance (Pewarisan) Polimorfisme Template Fungsi dan Kelas • Sort • Search • • • •
SEARCH/PENCARIAN Pertemuan 15
3 SKS
SEQUENTIAL SEARCH / PENCARIAN SEKUENSIAL Pertemuan 15
3 SKS
SEARCH
-
PENCARIAN
Larik Merupakan tipe data terstruktur. Macam-macam tipe Larik adalah • Integer • Karakter • Rekaman Pendefinisian Larik (Nama dan Tipenya) didalam kamus adalah sbb : Kamus D : Array [1..11] of Integer Kar : Array [1..8] of Character Const N : Integer = 5 Type Data = Record
Data_Siswa : Array [1..N] of Data
Larik Bertipe Integer 22
61
15
66
18
25
34
87
55
45
10
1
2
3
4
5
6
7
8
9
10
11
f
h
u
*
#
7
8
9
10
11
Larik Bertipe Character s 1
t 2
i 3
m 4
i 5
k 6
Larik Bertipe Rekaman 1 2 3 4
Yani Luth Reny Yusuf
26 24 29 32
SEQUENTIAL SEARCH (Pencarian Sekuensial)
Disebut juga pencarian linier menggunakan prinsip sebagai berikut : Data yang ada pada suatu array dibandingkan satu persatu dengan data yang dicari Pencarian ini hanya melakukan pengulangan dari 1 s.d. dengan jumlah data. Pada setiap pengulangan, dibandingkandata ke-i dengan yang dicari. Apabila sama, berarti data telah ditemukan. Sebaliknya apabila sampai akhir pengulangan, tidak ada yang sama, berarti data tidak ada
SEQUENTIAL SEARCH (Pencarian Sekuensial)
Adalah proses membandingkan setiap elemen Larik satu persatu secara beruntun, dari elemen pertama sampai elemen yang dicari ditemukan. Ada 2 (dua) macam pencarian sekuensial : 1. Pencarian sekuensial pada Larik yang tidak berurut 2. Pencarian beruntun pada Larik yang terurut
Contoh : Larik L dibawah ini 22 61 16 66 18 25 1
2 3
4
5
6
Misalkan, nilai yang dicari 66 Maka elemen yang diperiksa : 22, 61, 16, 66 (ditemukan)
Indeks Larik yang dikembalikan : 1X = 4
Sequential Search (Pencarian Sekuensial)
• Algoritmanya sebagai berikut : 1. i 1 2. ketemu false 3. Selama (not ketemu) dan (i <= N) kerjakan baris 4 4. Jika (Data [i] = x) maka ketemu true, jika tidak i i + 1 5. IF (ketemu) maka i adalah indeks dari data yang dicari, jika tidak data tidak ditemukan
Sequential Search (Pencarian Sekuensial) •
Algoritmanya yang lain : 1. Tentukan dan simpan data dalam suatu array 2. Tentukan fungsi pencarian sekuensial 3. Fungsi pencarian sekuensial adalah sebagai berikut : int flag=-1; { for(int count=0; count < array_size; count++) { flag=count; break; } }
4. Masukkan data yang akan dicari 5. Kerjakan langkah 3, jika data ketemu kerjakan lang-kah 6. Jika data tidak ketemu lakukan langkah 6 6. Cetak data tersebut 7. Selesai
int flag=-1; { for(int count=0; count < array_size; count++) flag=count; break } }
{
Pernyataan diatas berarti : 1. Lakukan pengulangan dari data pertama sampai data yang terakhir 2. Jika data yang dimasukkan sama pada waktu pengulangan data ke count, maka data ditemukan. Jika tidak sama, maka pencarian di teruskan sampai pengulangan data terakhir/data ditemukan. Dan apabila data tidak di ketemukan sampai pengulangan terakhir, maka data tidak ada
ALGORITMANYA Kamus Const Nmaks : Integer = 1000 Type Larik100 = Array [1..Nmaks] of Integer Procedure Cari1 (Input L:Larik100, Input N:Integer, Input X:Integer, I/O Ix:Integer) {mencari X didalam Larik L[1..N] secara beruntun} K.awal : Larik L[1..N] sudah terdefinisi harganya, X adalah harga yang akan dicari K.akhir : IX berisi Indeks Larik tempat X ditemukan, IX=0 jika X tidak ditemukan}
Kamus Lokal I : Integer Algoritma
{Indeks untuk pencarian}
I1 While (I < N) and (L[I] ‡ X) do II+1 Endwhile If (L[I] ‡ X) Then IX 0 Else IX 1 Endif
Pencarian Sekuensial Pada Larik Tidak Terurut Procedure Cari2 (Input Kamus Lokal I : Integer Ketemu : Boolean
L:Larik100, Input N:Integer,Input X:Integer,I/O Ix:Integer)
Algoritma I1 Ketemu False While (I N) and (not Ketemu) do If L[I] = x Then Ketemu True Else II+1 Endif Endwhile If Ketemu Then IX 1 Else IX 0 Endif
Pencarian Sekuential Pada Larik Yang Terurut Apabila Larik sudah terurut menaik yaitu untuk setiap I=1..N, Nilai [I-1] < Nilai [I] menurun yaitu untuk setiap I=1..N, Nilai [I-1] > Nilai [I] Maka proses pencarian dpt dibuat dgn menghilangkan langkah pencarian yg tidak perlu Contoh : Procedure Cari3 (Input L:Larik100, Input N:Integer, Input X:Integer, I/O Ix:Integer)
Kamus Lokal I : Integer {Indeks untuk pencarian} Algoritma I1 While (I < N) and (L[I] < X) do II+1 Endwhile If (L[I] = X) Then IX I Else IX 0 Endif
Algoritma.........????? Group2 Pseudocode.......?????? Group1
BINARY SEARCH/ PENCARIAN BINER Pertemuan 15
3 SKS
Binary SEARCH (Pencarian Biner) Salah satu syarat pencarian bagi dua (binary search) adalah data sudah dalam keadaan terurut Apabila data belum keadaan terurut, pencarian biner tidak dapat dilakukan Data yang terurut merupakan syarat mutlak penerapan pencarian Algoritma pencarian Bagi Dua.
Binary SEARCH (Pencarian Biner) Prinsip dari pencarian biner adalah : 1. Pertama diambil posisi awal =1 dan posisi akhir =N, kemudian dicari posisi data tengah dengan rumus (posisi awal+posisi akhir)/2 2. Kemudian data yang dicari dibandingkan dengan data tengah 3. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah -1 4. Jika lebih besar, proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah +1 5. Demikian seterusnya sampai data tengah sama dengan yang dicari
Binary SEARCH (Pencarian Biner) Algoritma pencarian biner adalah : 1. 2. 3. 4. 5. 6. 7. 8. 9.
L1 RN Ketemu false Selama (L R)dan (not ketemu) kerjakan baris 5 sampai dengan 8 M (L+R)/2 Jika (Data[M] = x) maka ketemu true Jika (x < Data[M]) maka R M-1 Jika (x > Data[M]) maka L M+1 If (ketemu) maka M adalah indeks dari data yang dicari, jika tidak data tidak ditemukan
Selama proses pencarian, memerlukan 2 (dua) indeks Larik yaitu indek terkecil dan terbesar Indek Terkecil = Indek ujung Kiri Larik (Ia) Indek Terbesar = Indek ujung Kanan Larik (Ib) Langkahnya : 1. Bagi 2 elemen Larik dengan Indek K = (Ia + Ib) div 2 2. Periksa apakah L[k] = x. Jika L[k] =x pencarian dihentikan Tetapi jika L[k] ‡ x harus ditentukan apakah pencarian akan dilakukan Larik bagian Kiri (Ia=tetap; Ib=k-1)/Kanan (Ia=k+1 ; Ib=tetap) 3. Ulangi langkah 1 sampai x ditemukan
Procedure Bagi2
(Input L:Larik100, Input N:Integer,Input X:Integer,I/O Ix:Integer)
Kamus Lokal Ia, Ib : Integer K ; Integer Ketemu : Boolean Algoritma Ia 1 Ib N Ketemu False While (not Ketemu) and (Ia Ib) do K (Ia +Ib) div 2 If (L[K] = x) Then Ketemu True Else If (L[K] > x) Then Ia K + 1 Else Ib K - 1 Endif Endif Endwhile If Ketemu Then IX K Else IX 0 Endif
CONTOH - Binary Search Membuat algoritma dan program dari pencarian beberapa data yang telah diketahui dengan menggunakan Metode Binary Search. Data-data harus sudah dalam keadaan terurut, yaitu : 10 15 18 22 25 34 45 55 61 66 87
Algoritma/pseudecode : 1. Tentukan posisi awal, dalam contoh posisi awal 10 2. Tentukan posisi akhir, dalam contoh posisi akhir 87 3. Cari data tengah dengan rumus (posisi awal + posisi akhir)/2 sesuai dengan contoh diatas data tengahnya = (1+11)/2 = 12/2 = 6. Data tengah berada pada posisi ke-6 yaitu angka 34 4. Data yang dicari adalah 61. Karena angka 61 > 34, berarti posisi awal pencarian = posisi tengah + 1 = 6+1 = 7 5. Data tengah baru diperoleh yaitu (7+11)/2 = 9. Berarti data tengah terbaru ada pada posisi ke-9 yaitu angka 61 6. Angka yang dicari dibandingkan dengan data tengah baru ini. Karena angka 61 = data tengah yang terbaru yaitu angka 61, maka proses pencarian dihentikan karena data sudah ketemu 7. Pencarian selesai dan data yang ketemu bisa dicetak
Algoritma prosesnya adalah : 1. Tentukan dan simpan data didalam suatu array 2. Tentukan fungsi pencarian biner 3. Fungsi pencarian biner adalah sebagai berikut int flag=-1; { int start=0; int end=array_size=1; int middle; int position=-1; midlle=(start+end)/2; { if(elemen < array[middle]) end=middle-1; else if (elemen > array[middle]) start=middle+1; middle=(start+end)/2; } while(start <=end && array[middle] != elemen); if(array[middle]==elemen) position=middle
4. Masukkan data yang akan dicari 5. Kerjakan langkah 3, jika data ketemu kerjakan langkah 6. Jika tidak ketemu lakukan langkah 7 6. Cetak data tersebut dalam posisi diketemukan 7. Selesai
Algoritma.........????? – Group 1 Pseudocode.......?????? Group 2
UntukPrak hari RABU • Jam 8.00 s.d. 11.30 Praktikum SORT BUBBLE • Jam 13.00 s.d. 16.00 Praktikum SEARCH
Pencarian data ke x=6 (34) dengan data : 10 15 18 22 25 34 45 55 61 66 67 1. 2. 3. 4. 5.
L=1 R=11 Ketemu False M =(L+R)/2 = (1+11)/2 = 6 (Data[6] = x) maka ketemu true 34 = 34
