ALGORITMA SEARCHING Makul algoritma

-


ALGORITMA SEARCHING


1.      Pengertian Algoritma Pencarian (searching)
Pencarian(searhing) merupakan proses yang fundamental dalam pengolahan data. Proses pensarian adalah menemukan nilai(data) tertentu didalam sekumpulan data yang bertipe sama (baik bertipe dasar maupun bertipe bentukan).
Sebuah algoritma pencarian dijelaskan secara luas adalah sebuah algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi. Algoritma pencarian (searching algorithm) adalah algoritma yang menerima sebuah argumen kunci dan dengan  langkah-langkah tertentu akan mencari rekaman dengan kunci tersebut.  Setelah proses pencarian dilaksanakan, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang dicari ditemukan (successful) atau tidak ditemukan (unsuccessful).
1.      Macam-macam Algoritma Pencarian (Searching)
1.1  Pencarian sekuensial (Sequential searching)
·         Pengertian
Pencarian Sekuensial (sequential searching) atau pencarian berurutan sering disebut pencarian linear merupakan metode pencarian yang paling sederhana.  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. Pencarian beruntun terbadi dua:
1.      Pencarian beruntun pada larik tidak terurut;
2.      Pencarian beruntun pada larik terurut.


·         Algoritma
Pencarian berurutan menggunakan prinsip sebagai berikut :
1.      data yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data tersebut ditemukan atau tidak ditemukan.
2.      Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah data.
3.      Pada setiap pengulangan, dibandingkan data ke-i dengan yang dicari.
4.       Apabila sama, berarti data telah ditemukan.   Sebaliknya apabila sampai akhir pengulangan tidak ada data yang sama, berarti data tidak ada.
Kelemahan pada kasus yang paling buruk, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula. Algoritma pencarian berurutan dapat dituliskan sebagai berikut :
(1)           i ← 0
(2)           ketemu ← false
(3)           Selama (tidak ketemu) dan (i <= N) kerjakan baris 4
(4)           Jika (Data[i] = x) maka ketemu ← true, jika tidak i ← i + 1
(5)           Jika (ketemu) maka i adalah indeks dari data yang dicari, jika data tidak ditemukan
·         Contoh
#include <stdio.h>
#include <conio.h>
void main(){
int data[8] = {8,10,6,-2,11,7,1,100};
 int cari;
   int flag=0;
  printf("masukkan data yang ingin dicari = ");scanf("%d",&cari);
   for(int i=0;i<8;i++){
                if(data[i] == cari) flag=1;
   }
   if(flag==1) printf("Data ada!\n"); 
else printf("Data tidak ada!\n");
getch();
return 1;
}
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 akan tetap bernilai 0.
·                     Semua elemen array data akan dibandingkan satu persatu dengan data yang dicari dan diinputkan oleh user.
1.1  Pencarian Beruntun dengan Sentinel
·         Pengertian
Jika pencarian bertujuan untuk menambahkan elemen baru setelah elemen terakhir larik, maka terdapat sebuah varian dari metode pencarian beruntun yang mangkus. Nilai x yang akan dicari sengaja ditambahkan terlebih dahulu. Data yang ditambahkan setelah elemen terakhir larik ini disebut sentinel.
Perhatikan array data berikut ini:
  0                       1                    2                3                     4                  5              6          indeks
3
12
9
-4
21
6
        ffea                 ffeb          ffec               ffed               ffef                  fffa           fffb       alamat
  
ü Terdapat 6 buah data dalam array (dari indeks 0 s/d 5) dan terdapat 1 indeks array tambahan (indeks ke 6) yang belum berisi data (disebut sentinel)
ü Array pada indeks ke 6 berguna untuk menjaga agar indeks data berada pada indeks 0 s/d 5 saja.  Bila pencarian data sudah mencapai array indeks yang ke-6 maka berarti data TIDAK ADA, sedangkan jika pencarian tidak mencapai indeks ke-6, maka data ADA.
· Algoritma
Procedure SeqSearchWithSentinel(input L: LarikInt, input n: integer, input x: integer, output idx: integer)
DEKLARASI
     I: integer
ALGORITMA
L[n+1]  ← X   {sentinel}
I ← 1
While (L[i] ≠ x) do
                 I ← i+1
Endwhile
If idx = n+1 then
                 idx  ← -1
else
                 idx ← 1
endif
·         Contoh
#include <stdio.h>
#include <conio.h>
void main(){
 int data[7] = {3,12,9,-4,21,6};
 int cari,i;

printf("masukkan data yang ingin dicari = ");scanf("%d",&cari);
data[6] = cari;
   i=0;
 while(data[i] != cari) i++;
 if(i<6) printf("Data ada!\n"); else printf("Data tidak ada!\n");
getch;
return 1;
}
1.1  Pencarian Biner (binary search)
·         Pengertian
Terdapat metode pencarian pada data terurut yang paling efficient, yaitu metode pencarian bagidua atau pencarian biner (binary search). 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.
BST adalah binary tree yang mana data di dalamnya tersusun sedemikian rupa sehingga pada setiap subtree di dalamnya berlaku:
setiap data di subtree kiri < data root subtree < setiap data di subtree kanan.
·                     Algoritma

class BinaryNode {
      void printInOrder( )‏
      {
              if( left != null )‏
           left.printInOrder( );                               // Left
              System.out.println( element );            // Node
              if( right != null )‏
               right.printInOrder( );                          // Right
   }
}
class BinaryTree {
   public void printInOrder( )‏
   {
              if( root != null )‏
              root.printInOrder( );
   }
}
Prinsip dari pencarian biner dapat dijelaskan sebagai berikut :
1.                   mula-mula diambil posisi awal 0 dan posisi akhir = N - 1, 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, porses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah + 1.
5.                   Demikian seterusnya sampai data tengah sama dengan yang dicari.
Algoritma pencarian biner dapat dituliskan sebagai berikut : 
1.                    L  ← 0
2.                  R ← N - 1
3.                  ketemu ← false
4.                  Selama (L <= R) dan (tidak ketemu) kerjakan baris 5 sampai dengan 8   
5.                  m ← (L + R) / 2 83
6.                   Jika (Data[m] = x) maka ketemu ← true
7.                   Jika (x < Data[m]) maka R ← m – 1 Jika (x > Data[m]) maka L  ← m + 1
8.                  Jika (ketemu) maka m adalah indeks dari data yang dicari, jika tidak data tidak ditemukan.
·                      Contoh
int binary_search(int cari){
int l,r,m;
 l = 0;
   r = n-1;
 int ktm = 0;
 while(l<=r && ktm==0){
                m = (l+r)/2;
               if(data[m] == cari) ktm=1;
               else if (cari < data[m]) r=m-1;
               else l=m+1; {
 if(ktm==1) return 1; else return 0;
}         
}                     
}
1.1  Interpolation Search
·         Pengertian
Teknik ini dilakukan pada data yang sudah terurut  berdasarkan kunci Tertentu. Teknik searching ini dilakukan dengan perkiraan letak data.
Contoh ilustrasi: jika kita hendak mencari suatu nama di dalam buku telepon, misal yang berawalan dengan huruf T, maka kita tidak akan mencarinya dari awal buku, tapi kita langsung membukanya pada  2/3 atau ¾ dari tebal buku. Jadi kita mencari data secara relatif terhadap jumlah data. Rumus posisi relatif kunci pencarian dihitung dengan rumus:
Posisi =       kunci – data[low]       x (hight – low) + low
              Data[hight] – data[low]

Misal terdapat data sebagai berikut:

Kode
Judul Buku
Pengarang
025
The C++ Programming
James Wood
034
Mastering Delphi 6
Marcopolo
041
Professional C#
Simon Webe
056
Pure JavaScript v2
Michael Bolton
063
Advanced JSP & Servlet
David Dunn
072
Calculus Make it Easy
Gunner Christian
088
Visual Basic 2005 Express
Antonie
096
Artificial Life : Volume 1 Gloria
Virginia


Kunci Pencarian ? 088
Low ? 0 
High ? 7
Posisi = (088 - 025) / (096 - 025) * (7 - 0) + 0 = [6]
Kunci[6] = kunci pencarian, data ditemukan : Visual Basic 2005
Kunci Pencarian ? 060
Low ? 0
High ? 7
Posisi = (060 – 025) / (096 – 025) * (7 – 0) + 0 = [3]
Kunci[3] < kunci pencarian, maka teruskan
Low = 3 + 1 = 4
High = 7
Ternyata Kunci[4] adalah 063 yang lebih besar daripada 060.
Berarti tidak ada kunci 060.
·         Contoh Program
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
int interpolationsearch(int a[],int low,int high,int x){
      int mid;
      while(low<=high){                            
                  mid=low+(high-low)*((x-a[low])/(a[high]-a[low]));
                  if(x==a[mid])
                              return mid+1;
                  if(x<a[mid])
                              high=mid-1;
                  else
                              low=mid+1;
      }
       return -1;
}

In
t main(){
      int arr[MAX];
      int i,n;
      int val,pos;
       
     printf("\nEnter total elements (n < %d) : ",MAX);
      scanf("%d",&n);
       printf("Enter %d Elements : ",n);
       for(i=0;i<n;i++)
                  scanf("%d",&arr[i]);
                  printf("\nLIST : ");          
        for(i=0;i<n;i++)
                   printf("%d\t",arr[i]);
                  printf("\nSearch For : ");
                  scanf("%d",&val);
                  pos=interpolationsearch(&arr[0],0,n,val);
                  if(pos==-1)
                              printf("\nElement %d not found\n",val);
                              else
                                          printf("\nElement %d found at position %d\n",val,pos);
           return 0;
}

Pencarian Biner (Binary Search) Pada Array Yang Sudah Terurut
Pencarian Biner (Binary Search) dilakukan untuk :
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.
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).
Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.
Algoritmanya :

Contoh Nilai-Nilai data yang sudah terurut :

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.

Comments

Post a Comment

Popular posts from this blog

Sejarah Roti Swiss Klaian harus tau

-
Sejarah Roti Swiss Roti saat ini merupakan makanan yang sudah sangat di kenal luas di masyarakat dan berkembang pesat . Perkembangan sejarah roti konon merupakan perjalanan yang sangat panjang yang di mulai sejak 10,000 -12,000 tahun yang lalu. Dari catatan sejarah roti berkembang dari daerah mesopotamia dan mesir , saat manusia mengetahui cara mengkonsumsi gandum. Pada awalnya mereka mengkonsumsi gandum secara langsung, namun setelah diketemukan cara yang lebih baik yaitu dengan di lumat dengan air menjadi pasta serta di panaskan di atas api dan di keringkan,maka sejak itu sejarah roti mulai . Tehnik membuat roti seperti ini masih di kembangkan hingga saat ini di berbagai negara walaupun dengan teknologi yang beragam. Contoh beberapa produk yang di kembangkan dengan tehnik tersebut hingga sekarang seperti : tortila meksiko, roti canai di India,roti pita di timur tengah   serta di negara-negara lainnya. Pada umumnya roti –roti jenis ini dikenal dengan istilah flat brea...
Read more

coding vb untuk membuat form nama pegawai, kode, jabatan, gaji pokok, tunjangan gaji dll, Conditional Statement (if.... else) vb 2010

-
Image
Buat Form pengolahan Gaji BAB III   Hasil dan Pembahasan 1.Desain form     2.form hasil eksekusi Hasil eksekusi setelah Form dijalankan Semua object dalam keadaan Tidak Aktif dan Bersih   Hasil eksekusi setelah   Ketika diklik tombol Tambah maka semua object Aktif dan Bersih  Hasil eksekusi setelah nama pegawai di inputkan pada projek serta setelah kode jabatan dipilih pada comboBox     Hasil eksekusi setelah dihitung melalui status,Tunjangan gaji dan hasil total gaji   Setelah data dieksekusi maka akan muncul hasil data tersebut, jika ingin mengakhiri maka tekan selesai secara otomatis akan keluar perintah “Yakin akan keluar (Y/N)?     3.property setiap objek dalam form Property Keterangan Nama Pegawai Label Kode ComboBox Jabatan Label Gaji Pokok Label Status Label Laja...
Read more

visual basic 2010,, form soal kuis 1 operator aritmatika, operator perbandingan, dll

-
BAB 1 Pendahuluan Latar Belakang Didalam sebuah software ada beberapa komponen yang harus kita ketahui, bukan hanya di ketahui tetapi kita juga harus mengerti apa fungsi dari komponen yang terdapat di software tersebut. Salah satu komponen yang ada di dalam software adanya visual basic. Visual Basic memungkinkan pembuatan aplikasi Grapichal User Interface (GUI) atau pemrograman yang menggunakan tampilan grafis sebagai alat komunikasi dengan pemakainya.   Tujuan Praktikum Untuk mengetahui definisi Data, Variabel, konstanta dan operator pada pembuatan sistem basis data, Untuk mengetahui penggunaan Data, Variabel, konstanta dan operator. BAB II Dasar Teori Tipe Data         Tipe data merupakan suatu bentuk penggolongan jenis data berdasarkan kategori data, ukuran dan kegunaan data yang dapat ditampung oleh sebuah variabel. Konversi Tipe Data         Konversi Tipe data adalah sebuah fungsi ya...
Read more