Join With Me On Twitter

Join With Me On Twitter : @supersahrul

Kamis, 15 Oktober 2009

Searching array dalam Turbo Pascal

I. Judul Praktikum : Searching
II. Tujuan Praktikum :
1. Untuk mengetahui pengertian searching.
2. Dapat mengetahui pengertian dan prinsip pencarian biner.
3. Dapat mengetahui penggunaan metode pencarian beruntun atau pencarian bagi dua.
4. Untuk mengetahui kinerja pencarian beruntun dan pencarian bagidua.
III. Dasar Teori
Array pada dasarnya merupakan suatu tipe data yang dapat menampung serangkaian tipe data yang sama dalam suatu variabel. Bila pada dasarnya kita mengenal tipe variabel seperti character atau char, integer atau int, dan float atau real, maka tipe data tersebut umumnya hanya dapat menampung sebuah data saja bila tidak menggunakan array.
Ketika menggunakan array pun, banyak bahasa pemrograman yang menggunakan index atau key dalam array menggunakan angka bulat atau integer yang umumnya dimulai dari 0 (nol).
Proses pencarian (searching) adalah menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe sama (baik bertipe dasar atau bertipe bentukan).
Terdapat 2 metode pencarian yaitu Metode Pencarian Beruntun (Sequential Search) dan Metode Pencarian Bagidua (Binary Search), kita hanya akan membahas metode yang kedua yaitu Metode Pencarian Bagidua (Binary Search). Karena metode ini adalah metode pencarian pada data terurut yang paling efficient. Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Prinsip pencarian dengan membagi data atas dua bagian mengilhami metode ini. Data yang disimpan di dalam larik harus sudah terurut.
Pada suatu data seringkali dibutuhkan pembacaan kembali informasi (retrieval information) dengan cara searching. Searching merupakan pencarian data dengan cara menelusuri data-data tersebut Pencarian(searching) merupakan proses yang fundamental dalam pengolahan data.
Proses pencarian adalah menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe sama ( baik bertipe dasar atau bertipe bentukan ). Tempat pencarian data dapat berupa array dalam memori, bisa juga pada file pada external storage.
Di dalam Buku Algoritma dan Pemrograman telah disebutkan bahwa aktivitas yang berkaitan dengan pengolahan data sering didahului dengan proses pencarian. Sebagai contoh, untuk mengubah (update) data tertentu, langkah pertama yang harus dilakukan adalah mencari keberadaan data tersebut di dalam kumpulannya.
Jika data yang dicari ditemukan, maka data tersebut dapat diubah nilainya dengan data yang baru. Aktivitas awal yang sama yang sama juga dilakukan pada proses penambahan (insert) data baru. Proses penambahan data dimulai dengan mencari apakah data yang akan ditambahakan sudah terdapat di dalam kumpulan. Jika sudah ada dan mengasumsikan tidak boleh ada duplikasi data maka data tersebut tidak perlu ditambahkan, tetapi jika belum ada, maka tambahkan.
Binary Search Adalah teknik pencarian data dalam array dengan cara membagi array menjadi dua bagian setiap kali terjadi proses pengurutan.
 Prinsip pencarian biner adalah:
o Data diambil dari posisi 1 sampai posisi akhir N
o Kemudian cari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2
o Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?
o Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1
o Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1
o Jika data sama, berarti ketemu.
Cara kerja metode pencarian biner dapat dijelaskan sebagai berikut: dimisalkan kita memiliki larik terurut seperti di bawah ini:

Misalkan, kita ingin mencari posisi dari nilai 56. Pertama kali, larik di atas dapat kita bagi menjadi 2 sublarik sebagai berikut:

Kemudian, data (56) dibandingkan dengan elemen terakhir pada sublarik 1 (yang bernilai 11). Jika data tersebut (56) lebih kecil dari elemen terakhir pada sublarik1
(11) maka data akan dicari di subvektor 1. Jika tidak, berarti data akan dicari di sublarik 2 dan sublarik 1 tidak perlu dihiraukan lagi. Proses di atas diulangi lagi. Sublarik 2 dibagi 2 lagi sehingga menghasilkan sublarik dibawah ini:

Kita bandingkan lagi data (56) dengan elemen terakhir sublarik 2.1 (34). Ternyata data (56) lebih besar dari (34), maka pasti data yang dicari ada di sublarik 2.2. terakhir, sublarik 2.2 dipecah lagi. Hasilnya adalah sebagai berikut:

Larik merupakan tipe data terstruktur. Sebuah larik dapat dibayangkan sebagai sekumpulan kotak yang menyimpan sekumpulan elemen bertipe sama secara berturutan (sequential) di dalam memori komputer. Setiap elemen larik data diacu melalui indeksnya.
Karena elemen disimpan secara berurutan, indeks larik haruslah suatu tipe yang juga mempunyai keterurutan (memiliki suksesor dan ada predesesor), misalnya tipe integer atau karakter. Jika indeks larik adalah karakter maka keterurutan indeks sesuai dengan urutan karakter. Tiap elemen larik langsung diakses dengan menspesifikasikan nama larik berikut indeksnya.
Larik dipelajari lebih mendalam dalam Buku 2, karena larik adalah struktur internal (yaitu, struktur yang direalisasikan di dalam memori utama), maka pencarian elemen di dalam larik disebut juga pencarian internal. Sedangkan pada pencarian eksternal, pencarian dilakukan terhadap sekumpulan data yang disimpan di dalam memori sekunder seperti tape atau disk. Penyimpanan data di dalam storage bersifat permanen dengan tujuan agar dapat dibaca kembali untuk pemrosesan lebih lanjut.
Persoalan Pencarian
Diberikan larik L yang sudah terdefinisi elemen-elemennya , dan x adalah elemen yang bertipe sama dengan elemen larik L. Carilah x di dalam larik L.
Hasil atau keluaran dari persoalan pencarian dapat bermacam-macam, bergantung pada spesifikasi (spek) rinci dari persolan tersebut, misalnya:
a. Pencarian hanya untuk memeriksa keberadaan x. Keluaran yang diinginkan misalnya pesan (message) bahwa x ditemukan atau tidak ditemukan di dalam larik.
b. Hasil pencarian adalah indeks elemen larik. Jika x ditemukan, maka indeks elemen larik tempat x berada diisikan ke dalam idx. Jika x tidak terdapat di dalam larik L, maka idx diisi dengan harga khusus, misalnya -1.
c. Hasil pencarian adalah sebuah nilai boolean yang menyatakan status hasil pencarian. Jika x ditemukan, maka sebuah peubah bertipe boolean, misalnya ketemu, diisi dengan nilai true, sebaliknya “ketemu” diisi dengan nilai false. Hasil pencarian ini selanjutnya disimpulkan pada pemanggilan prosedur.
Contoh : keluaran hasil pencariaan berupa boolean
Perhatikan larik
Misalkan x = 68, maka ketemu= true, dan bila x = 100, maka ketemu = false.
Untuk kedua macam keluaran b dan c di atas, kita mengkonsultasi hasil pencariaan setelah prose pencarian selesai dilakukan, bergantung pada kebutuhan. Misalnya menampilkan pesan bahwa x ditemukan (atau tidak ditemukan) atau memanipulasi nilai x.
Contoh:
(1) If ketemu then {artinya ketemu = true}
Write (x, ‘ditemukan’)
Else
Write(x, ‘ditemukan’)
Endif
(2) If idx = -1 then {berarti x ditemukan}
L[idx] L[idx] + 1 {manipulasi nilai x}
Endif
Hal lain yang harus diperjelas dalam spesifikasi persoalan pencarian adalah mengenai duplikasi data. Apabila x yang dicari terdapat lebih dari satu banyaknya di dalam larik L, maka hanya x yang pertama kali ditemukan saja yang diacu dan algoritma pencarian selesai. Sebagai contoh, larik memiliki tiga buah nilai 36. Bila x = 36, maka algoritma pencarian selesai ketika x ditemukan pada elemen ke-2 dan menghasilkan idx=2 (atau menghasilkan ketemu = true jika mengacu pada keluaran pencarian jenis b). Elemen 36 lainnya tidak dipertimbangkan lagi.
Metode pencarian yang akan dibahas adalah :
1. Metode pencarian beruntun.
2. Metode pencarian bagidua.
Untuk masing-masing algoritma dari kedua metode percarian metode pencarian di atas, tipe larik yang digunakan dideklarasikan di dalam bagian deklarasi global seperti di bawah ini. Larik L adalah bertipe larik Int.
{kamus data global}
DEKLARASI
const Nmaks = 100{jumlah maksimum elemen larik}
type LarikInt = array[1..Nmaks] of integer
Metode pencarian beruntun
Metode pencarian yang paling sederhana yaitu metode pencarian beruntun. Nama lain metode pencarian beruntun adalah pencarian lurus (linear search). Pada dasarnya metode pencarian beruntun adalah proses membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama, sampai elemen yang dicari ditemukan, atau seluruh elemen sudah diperiksa.
(a) Versi 1 (pembandingan elemen dilakukan di awal pengulangan)
1. Hasil pencarian : sebuah peubah boolean yang bernilai true bila x ditemukan atau bernilai false bila x tidak ditemukan.
Setiap elemen larik L dibandingkan dengan x mulai dari elemen pertama, L[1]. Aksi pembandingan dilakukan selama indeks larik i belum melebihi n dan L[i] tidak sama dengan x. Aksi pembandingan tidak dihentikan bila L[i] = x atau i = n. Elemen terakhir, L[n], diperiksa secara khusus. Keluaran yang dihasilkan oleh prosedur pencarian adalah sebuah peubah boolean (misal nama peubahnya ketemu) yang bernilai true jika x ditemukan atau bernilai false jika x tidak ditemukan. Untuk pencarian beruntun yang berupa fungsi, contoh cara pemanggilan fungsi SeqSearch1:
read(x)
if not SeqSearch1(L,n,x) then
write(x,’tidak ditemukan!’)
else
{proses terhadap x}
...
endif
2. Hasil pencarian : indeks elemen larik yang mengandung nilai x.
Setiap elemen larik L dibandingkan dengan x mulai dari elemen pertama, L[1]. Aksi pembandingan dilakukan selama indeks larik i belum melebihi n dan L[i] tidak sama dengan x. Aksi pembandingan dihentikan bila L[i] = x atau i = N. Elemen terakhir, L[n], diperiksa secara khusus. Keluaran yang dihasilkan oleh prosedur pencarian adalah peubah idx yang berisi indeks larik tempat x ditemukan. Jika x tidak ditemukan, idx diisi dengan -1.
(b) Versi 2 (pembandingan elemen dilakukan di dalam badan pengulangan)
Pada versi yang kedua ini, aksi pembandingan dilakukan didalam badan pengulangan(jadi bukan diawal pengulangan seperti pada varian pertama). Untuk itu, kita memerlukan sebuah peubah boolean yang akan berfungsi untuk menyatakan apakah x sudah ditemukan.
Misalkan peubah tersebut bernama ketemu yang pada mulanya diisi nilai false. Bila x ditemukan pada elemen ke-i yaitu L[i]= x, maka ketemu diisi dengan nilai true. Pengulangan dihentikan bila ketemu = true. Hasil pencarian disimpulkan di luar badan pengulangan. Algoritma pencarian beruntun versi 2 lebih elegan dibandingkan dengan algoritma versi 1 karena semua elemen dibandingkan dengan cara yang sama. Algoritma pencarian kita buat 2 macam, yang pertama untuk hasil pencaraian berupa peubah boolean, dan algoritma kedua untuk hasil pencarian berupa indeks elemen larik.
1. Hasil pencarian : sebuah boolean yang bernilai true bila x ditemukan atau bernilai false bila x tidak ditemukan. Pada versi ini, peubah boolean ketemu diinisialisasi dengan nilai false dan indeks larik i diisi dengan 1(karena pembandingan dimulai dari elemen pertama). Setiap elemen L dibandingkan dengan x mulai dari elemen pertama.
Jika L[i]=x, peubah ketemu diisi nilai true dan pengulangan dihentikan. Sebaliknya L[i] tidak sama dengan x pembandingan dilanjutkan untuk elemen berikutnya(i=i+1). Pada versi 2 ini, setiap elemen larik, termasuk elemen terakhir, diperiksa dengan cara yang sama. Keluaran yang dihasilkan adalah nilai yang disimpan di dalam peubah ketemu.
2. Hasil pencarian : indeks elemen larik mengandung nilai x.
Algoritmanya sama seperti SeqSearch3 di atas, hanya saja setelah kalang while-do ditambahkan pernyataan if-then untuk memberikan hasil pencarian berupa indeks elemen larik(idx)yang bernilai x.Jika x tidak ditemukan maka idx diisi nilai 1.
Algorima pencarian beruntun versi 2 untuk kategori hasil berupa indeks elemen larik dapat kita tulis sebagai prosedur atau sebagai fungsi.
Kinerja Metode Pencarian Beruntun
Secara umum, metode pencarian beruntun berjalan lambat. Waktu pencarian sebanding dengan jumlah elemen larik. Misalkan larik berukuran n elemen. Maka pada kasus di mana x tidak terdapat di dalam larik atau x ditemukan pada elemen yang terakhir, kita harus melakukan perbandingan dengan seluruh elemen larik, yang berarti jumlah perbandingan yang terjadi sebanyak n kali. Kita katakan bahwa waktu pencarian dengan algoritma pencarian beruntun sebanding dengan n.
Bayangkan bila larik berukuran 100.000 buah elemen, maka kita harus melakukan perbandingan sebanyak 100.000 buah elemen. Andaikan satu operasi perbandingan elemen larik membutuhkan waktu 0,01 detik, maka untuk 100.000 buah perbandingan diperlukan waktu sebesar 1000 detik atau 16,7 menit. Semakin banyak elemen larik, semakin lama pula waktu pencariannya. Karena itulah metode pencarian beruntun tidak bagus untuk volume data yang besar.
Metode Pencarian Beruntun pada Larik Terurut
Larik yang elemen-elemennya sudah terurut dapat meningkatkan algoritma pencarian beruntun. Jika pada larik tidak terurut jumlah perbandingan elemen larik maksimum n kali, maka pada larik terurut (dengan ansumsi distribusi elemen-elemen larik adalah seragam atau uniform) hanya dibutuhkan rata-rata n/2 kali perbandingan. Hal ini karena pada larik yang terurut kita dapat segera menyimpulkan bahwa x tidak terdapat di dalam larik bila ditemukan elemen larik yang lebih besar dari x (pada larik yang terurut menaik) [TEN86].
Metode Pencarian Beruntun dengan Sentinel
Jika pencarian bertujuan untuk menambahkan elemen baru setelah elemen terakhir larik, maka terdapat sebuah varian dari sebuah metode pencarian beruntun yang mangkus. Nilai x yang akan di cari sengaja ditambahkan terlebih dahulu pada elemen ke-n+1. Data yang ditambahkan setelah elemen terakhir larik ini disebut sentinel. Selanjutnya, pencarian beruntun dilakukan di dalam larik L[1..n+1]. Akibatnya, proses pencarian selalu menjamin bahwa x pasti berhasil ditemukan.
Untuk menyimpulkan apakah x ditemukan pada elemen sentinel atau bukan, kita dapat mengetahuinya dengan melihat nilai idx. Jika idx = n+1 (yang berarti x ditemukan pada elemen sentinel), maka hal itu berarti bahwa x tidak terdapat di dalam larik L semula (sebelum penambahan sentinel).
Keuntungannya, elemen sentinel otomatis sudah menjadi elemen yang ditambahkan ke dalam larik. Sebaliknya, jika idx < n+1 (yang berarti x ditemukan sebelum sentinel), maka hal itu berarti bahwa x sudah ada di dalam larik L semula.
Metode Pencarian Bagidua
Pencarian pada data yang terurut menunjukan kinerja yanh lebih baik daripada pencarian pada data yang belum terurut. Hal ini sudah kita bicarakan pada metode pencarian beruntun untuk data yang sudah terurut. Data yang terurut banyak ditemukan di kehidupan sehari-hari.
Data nomor telepon di dalam buku telepon misalnya, sudah terurut berdasarkan nama/instansi pelanggan telepon dari A sampai Z. Data karyawan diurut berdasarkan nomor induknya dari nomor kecil ke nomor besar. Data mahasiswa diurut berdasarkan NIM (Nomor Induk Mahasiswa), kata-kata (entry) di dalam kamus bahasa inggris/indonesia telah diurut dari A sampai Z, dan sebagainnya.
Untuk mencari arti kata tertentu di dalam kamus (misalnya kamus bahasa inggris), kita tidak membuka halaman kamus tersebut dari halaman awal sampai halaman terakhir satu per satu, namun kita mencarinya dengan cara membelah atau membagi dua buku itu.
Jika kata yang dicari tidak terletak di halaman pertengahan itu, kita mencari lagi di belahan bagian kiri atau belahan bagian kanan dengan cara membagi dua belahan yang dimaksud. Begitu seterusnya sampai kata yang dicari ditemukan. Hal ini hanya bisa dilakukan jika kata-kata di dalam kamus sudah terurut.
Prinsip pencarian dengan cara membagi data atas dua bagian mengilhami metode pencarian bagidua. Data yang disimpan didalam larik harus sudah terurut. Untuk memudahkan pembahasan, selanjutnya kita misalkan elemen larik sudah terurut menurun. Dalam proses pencarian, kita memerlukan dua buah indeks larik, yaitu indeks terkecil dan indeks terbesar. Kita menyebut indeks terkecil sebagai indeks ujung kiri larik dan indeks terbesar sebagai indeks ujung kanan larik. Istilah “kiri” dan “kanan” dinyatakan dengan membayangkan elemen larik terentang horizontal.
Misalkan indeks kiri adalah i dan indeks kanan adalah j. Pada mulanya kita inisialisasi i dengan 1 dan j dengan n.
Langkah 1 : Bagi dua elemen larik pada elemen tengah. Elemen tengah adalah elemen dengan indeks k = (i+j) div 2.
(Elemen tengah, L[k], membagi larik menjadi dua bagian, yaitu bagian kiri L[i..j] dan bagian kanan L[k+1..j)
Langkah 2 : Periksa apakah L[k] = x. Jika L[k] = x, pencarian selesai sebab x sudah ditemukan. Tetapi, jika L[k] tidak sama dengan x, harus ditentukan apakah pencarian akan dilakukan di larik bagian kiri atau di bagian kanan. Jika L[k] < x, maka pencarian dilakukan lagi pada larik bagian kiri. Sebaliknya, jika L[k] > x, pencarian dilakukan lagi pada larik bagian kanan.
Langkah 3 : Ulangi Langkah 1 hingga x ditemukan atau i > j (yaitu, ukuran larik sudah nol !)
Algoritma pencarian bagidua pada larik integer yang sudah terurut kita tuliskan di bawah ini, masing-masing sebagai prosedur dan sebagai fungsi. Untuk algoritma pencarian bagidua pada larik yang sudah terurut menaik, kita hanya perlu mengganti pernyataan if (L[k] > x ) dengan (if L[k] < x).

Kinerja Metode Pencarian Bagidua
Pembaca dapat melihat bahwa pada setiap kali pencarian, larik dibagidua menjadi dua bagian yang berukuran hampir sama. Pada setiap pembagian, elemen tengah dibandingkan apakah sama dengan x (if (L[k] = x).
Pada kasus terburuk, yaitu pada kasus x tidak terdapat di dalam larik atau x ditemukan setelah ukuran larik tinggal 1 elemen, larik akan dibagi sebanyak 2log (n) kali, sehingga jumlah pembandingan yang dibutuhkan adalah sebanyak 2log (n) kali.
Kita katakan bahwa waktu pencarian sebanding dengan 2log(n) [WIR76]. Untuk n = 256 elemen misalnya, kasus terburuk menghasilkan pembagian larik sebanyak 2log(256) = 8 kali, yang berarti jumlah pembandingan elemen adalah 8 kali (bandingkan dengan metode pencarian beruntun yang pada kasus terburuk melakukan pembandingan sebanyak 256 kali). Jadi, untuk larik yang terurut, algoritma pencarian bagidua jauh lebih cepat daripada pencarian beruntun.
Pencarian pada Larik Terstruktur
Metode pencarian yang dibahas sebelum ini menggunakan larik dengan elemen-elemen bertipe sederhana. Pada kebanyakan kasus, elemen larik sering bertipe terstruktur. Contoh, misalkan M adalah sebuah larik yang elemennya menyatakan nilai ujian seorang mahasiswa untuk suatu mata kuliah (MK) yang ia ambil. Data setiap mahasiswa adalah NIM (Nomor Induk Mahasiswa), nama mahasiswa, mata kuliah yang ia ambil, dan nilai mata kuliah tersebut. Deklarasi nama dan tipe adalah sebagai berikut :
DEKLARASI
const Nmaks = 100
type Mahasiswa : record < NIM : integer, {Nomor Induk Mahasiswa}
NamaMhs : string,{nama mahasiswa}
KodeMK : string, {kode mata kuliah}
Nilai: char {indeks nilai MK (A/B/C/D/E)}
>
type TabMhs : array [1..Nmaks] of Mahasiswa
M : TabMhs
Pencarian pada Larik yang Tidak Bertipe Numerik
Meskipun algoritma-algoritma pencarian yang sudah dikemukakan di atas diterapkan pada larik integer, mereka tetap benar untuk larik data yang bertipe bukan numerik misalnya data bertipe karakter, maupun string.
Menggunakan Metode Pencarian Beruntun atau Metode Pencarian Bagidua?
Kedua metode pencarian ini mempunyai kelebihan dan kekurangan masing-masing. Metode pencarian beruntun dapat digunakan baik untuk data yang belum terurut maupun untuk data yang sudah terurut. Sebaliknya, metode pencarian bagidua hanya dapat digunakan untuk data yang sudah terurut saja.
Ditinjau dari kierja pencarian, sudah mengtahui bahwa untuk kasus terburuk (yaitu jika pencarian gagal menemukan x), algoritma pencarian beruntun memerlukan waktu yang sebanding dengan n (banyaknya data), sedangkan algoritma pencarian membutuhkan waktu yang sebaning dengan 2log (n). Karena 2log (n) < n untuk n > 1, maka jika n semakin besar waktu pencarian dengan algoritma bagidua jauh lebih sedikit daripada waktu pencarian dengan algoritma beruntun.
Sebagai perbandingan antara algoritma pencarian beruntun dengan pencarian bagidua, ditinjau dari kasus di mana x tidak ditemukan di dalam larik yang sudah terurut. Misalkan,
(a)untuk larik yang berukuran n = 256 elemen
• algoritma pencarian beruntun melakukan pembandingan elemen larik sebanyak 256 kali,
• algoritma pencarian bagidua melakukan pembandingan sebanyak 2log (256) = 8 kali,
(b)untuk larik yang berukuran n = 1024 elemen
• algoritma pencarian beruntun melakukan pembandingan elemen larik sebanyak 1024 kali,
• algoritma pencarian bagidua melakukan pembandingan sebanyak 2log (1024) = 10 kali,

2 komentar:

  1. sala mau tanya nih..2 log maksudnya apa??

    BalasHapus
  2. blog nya berantakan,bingung bcanya..

    BalasHapus