Minggu, 07 Juni 2015

SEARCHING (Sequential Search dan Binarry Search)

Searching adalah metode pencarian informasi dalam suatu aplikasi, dengan suatu kunci( key ). Pencarian diperlukan untuk mencari informasi khusus dari table pada saat lokasi yang pasti dari informasi tersebut sebelumnya tidak diketahui. Pencarian selalu dinyatakan dengan referensi pada adanya sekelompok data yang tersimpan secara terorganisasi, kelompok data tersebut kita sebut table.

Pada metode searching (pencarian) ada 2 teknik yang digunakan yaitu : 
a. Pencarian sekuensial (sequential search)
b. Pencarian biner (Binary search).

a. Sequential Search

Pencarian sekuensial (sequential search) atau sering disebut pencarian linier menggunakan prinsip sebagai berikut : data yang ada di bandingkan satu persatu secara berurutan dengan yang dicari. Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah data. Pada setiap perulangan , di bandingkan data ke-i dengan yang dicari. Apabila sama , berarti data telah ditemukan . Sebaliknya apabila sampai akhir pengulangan , tidak ada yang sama berarti data tidak ada.

Pencarian Sekuensial memiliki beberapa kelebihan dan kekurangan yaitu :

1.       Kelebihannya :
·         Relatif lebih cepat dan efisien untuk data yang terbatas
·         Algoritma sederhana
2.       Kekuranganya :
·         Kurang cepat untuk data dalam jumlah besar
·         Beban komputasi cenderung lebih besar

Contoh Program Sequential Search pada bahasa C++ :

#include <iostream>
#include <conio.h>
#include <iomanip>

int main()
{
      int data[10] = {12, 24, 5, 30, 28, 50, 48, 76, 32,9};
      int caridata, i, flag = 0;

            cout<<"\n\t\t *************************************** \n";
   cout<<"\t\t | \t\t\t\t       | \n";
   cout<<"\t\t | \t     Proses Pencarian \t       | \n";
   cout<<"\t\t | Menggunakan Algoritma Sequential Search | \n";
   cout<<"\t\t | \t\t\t\t       | \n";
   cout<<"\t\t *************************************** \n\n\n";

   cout<<"Data   : ";
            for(int n=0; n<10; n++)
                  cout<<setw(4)<<data[n];
      cout<<endl;

      cout<<"\nMasukkan data yang ingin Anda cari : ";
      cin>>caridata;

      //cari dengan metode sequential search()
      for(i = 0; i<10; i++)
      {
            if(data[i]==caridata)
            {
                  flag = 1;
                  break;
            }
      }

      //cetak hasil
      if(flag==1)
      cout<<" Keterangan    : Terimakasih ! Data Telah Ditemukan pada Indeks ke - ";
      else
      cout<<" Keterangan    : Maaf ! Data yang dicari Tidak Ditemukan";

      getch();

}

Tampilan ketika Contoh Program Sequential Search dijalankan :




b. Binarry Search

Binary search adalah sebuah algoritma pencarian dengan cara membagi data menjadi dua bagian setiap kali terjadi proses pencarian untuk menemukan nilai tertentu dalam sebuah larik (array) linear. Sebuah pencarian biner mencari nilai tengah (median), melakukan sebuah pembandingan untuk menentukan apakah nilai yang dicari ada sebelum atau sesudahnya, kemudian mencari setengah sisanya dengan cara yang sama. Pencarian Biner (Binary Search) dilakukan untuk :

a)      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.
b)      Beban komputasi juga lebih kecil karena pencarian dilakukan dari depan, belakang, dan tengah.
c)      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).
d)     Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut.

Langkah dalam pencarian biner adalah :

1.      Mula-mula diambil dari posisi awal=1 dan posisi akhir = n
2.      Kemudian kita cari posisi data tengah dengan rumus posisi tengah = (posisi awal + posisi akhir ) div 2
3.      Kemudian data yang di cari dibandingkan dengan data tengah
a.       Jika sama, data ditemukan, Proses selesai
b.      Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah -1
c.       Jika lebih besar , proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah +1.
4.      Ulangi langkah kedua hingga data ditemukan , atau tidak ditemukan.
5.       Pencarian biner ini akan berakhir jika data ditemukan posisi awal lebih besar dari pada posisi akhir. Jika posisi awal sudah lebih besar dari posisis akhir berarti data tidak diketemukan.

 Pencarian Biner :
a.       Kelebihannya :
o   Untuk data dalam jumlah besar, waktu searching lebih cepat
o   Beban komputasi lebih kecil
b.      Kekuranganya :
o   Data harus sudah di-sorting lebih dulu ( dalam keadaan terurut )

Contoh Program Binary Search pada Bahasa C++ :

#include <iostream.h>
#include <conio.h>
#include <conio.h>

void main ()
{
    int jml_data, cari,no, kiri,kanan,tengah,data[100];

   cout<<"\n\t\t *************************************** \n";
   cout<<"\t\t | \t\t\t\t       | \n";
   cout<<"\t\t | \t     Proses Pencarian \t       | \n";
   cout<<"\t\t | Menggunakan Algoritma Binary Search | \n";
   cout<<"\t\t | \t\t\t\t       | \n";
   cout<<"\t\t *************************************** \n\n\n";

   cout<<" Inputkan Jumlah Data  : ";
   cin>>jml_data;

   cout<<endl;
   for (no=0;no<jml_data;no++)
    {
            cout<<" Inputkan Data Ke-"<<(no+1)<<"    : ";
            cin>>data[no];
    }
cout<<endl;
            cout<<" Inputkan Nilai Yang Ingin Dicari : ";
            cin>>cari;
kiri=0;
            kanan=jml_data-1;
            tengah=(kanan-kiri)/2;
while ((data[tengah]!=cari) && (kiri>=0)&& (kanan<jml_data) && (kanan>=kiri))
            {
                        if (cari>data[tengah])
                        {
                                     kiri=tengah+1;
                        }
                                     else if (cari<data[tengah])
                                    {
                                                kanan=tengah-1;
                                    }
                        tengah=kiri+(kanan-kiri)/2;
            }

            cout<<endl;
             if (data[tengah]==cari)
            {
                         cout<<" Keterangan         : Terimakasih ! Data Telah Ditemukan";
             }
             else
             {
                         cout<<" Keterangan         : Maaf ! Data Tidak Tersedia";
             }

    getch();
}

Tampilan ketika Contoh Program Binarry Search dijalankan :



DAFTAR PUSTAKA



  • Mita, S. 2014. Binarry Search. Diakses pada tanggal 06 Juni 2015 di mita.staff.gunadarma.ac.id/Downloads/files/.../BINARY-SEARCH.doc
  • Anonim. 2014. Binary Search. Diakses tanggal 06 Juni 2015 pada www.informatika.unsyiah.ac.id/tfa/ds/binarysearch.pdf
  • Anonim. 2014. Struktur Data pencarian berurut sequential seacrh. Diakses tanggal 06 Juni 2015 pada  http://xbasicpro.com/struktur-data/pencarian/struktur-data-pencarian-berurut-sequential-search-vbnet.aspx

TERIMAKASIH !!!


Selamat Mencoba :)
Selain materi diatas terdapat juga beberapa materi struktur data, silahkan klik link di bawah ini :


http://tria-swandewi.blogspot.com/2015/06/sorting-selection-sort-dan-insertion.html






Diposting oleh di Tidak ada komentar:

SORTING (Selection Sort dan Insertion Sort)

a. Selection Sort

Metode selection sort merupakan perbaikan dari metode bubble sort dengan mengurangi jumlah perbandingan. Selection sort merupakan metode pengurutan dengan mencari nilai data terkecil dimulai dari data diposisi 0 hingga diposisi N-1. Jika terdapat N data dan data terkoleksi dari urutan 0 sampai dengan N-1 maka algoritma pengurutan dengan metode selection sort adalah sebagai berikut:

Ø  Cari data terkecil dalam interval j = 0 sampai dengan j = N-1
Ø  Jika pada posisi pos ditemukan data yang terkecil, tukarkan data diposisi pos dengan data di posisi i jika k.

Ø  Ulangi langkah 1 dan 2 dengan j = j+i sampai dengan j = N-1, dan seterusnya sampai j = N - 1.

Contoh Program Selection Sort  :

#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <iomanip.h>

void main()
{
int x[5];
int i;
int temp;
int minindex;
int j;

clrscr();
cout<<" >> SELAMAT DATANG di CONTOH PROGRAM SELECTION SORT <<" <<endl;
cout<<"=======================================================\n"<<endl;
cout<<"masukkan nilai x :\n";
for(i=0; i<5; i++)
{
cout<<"x["<<i<<"] = ";cin>>x[i];
cout<<"\n";
}
cout<<"Data sebelum di sort :";
for(i=0; i<5;i++)
{
cout<<setw(4)<<x[i];
}
for(i=0; i<5-1; i++) //perulangan iterasi
{
minindex=i;
for(j=i+1; j<5; j++) //perulangan membandingkan data
{
if(x[minindex]>x[j])
{
minindex=j;
}
}
temp=x[i];
x[i]=x[minindex];
x[minindex]=temp;
}
cout<<"\n\nData setelah di sort :";
for(i=0; i<5; i++)
{
cout<<setw(4)<<x[i];
}
getch();
}

Tampilan sederhana ketika program selection sort dijalankan :




b. Insertion Sort

Metode penyisipan (Insertion sort) yang bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array berhasil diurutkan. Metode ini mengurutkan bilangan-bilangan yang telah dibaca dan berikutnya secara berulang akan menyisipkan bilangan-bilangan dalam array yang belum terbaca ke sisi kiri array yang telah terurut.


Contoh program insertion sort:

#include <iostream.h>
#include <conio.h>

int data[10],data2[10];
int n;

void tukar(int a, int b)
{
    int t;
    t = data[b];
    data[b] = data[a];
    data[a] = t;
}
void insertion_sort()
{
    int temp,i,j;
    for(i=1;i<=n;i++)
    {
        temp = data[i];
        j = i -1;
        while(data[j]>temp && j>=0)
            {
                data[j+1] = data[j];
                j--;
            }
        data[j+1] = temp;
    }
}
void main()
{
    cout<<">> SELAMAT DATANG di PROGRAM INSERTION SORT <<"<<endl;
    cout<<"=============================================="<<endl;
    cout<<"\n"<<endl;
    cout<<"Masukkan Jumlah Data : ";    cin>>n;
    cout<<"\n"<<endl;
    for(int i=1;i<=n;i++)
    {
        cout<<"Masukkan data ke "<<i<<"   : ";    cin>>data[i];
        data2[i]=data[i];
    }
    insertion_sort();
    cout<<"Data Setelah di Sort : ";
    for(int i=1; i<=n; i++)
    {
        cout<<" "<<data[i];
    }
getch();
}

Tampilan sederhana ketika program insertion sort dijalankan :



DAFTAR PUSTAKA


  • Anonim. 2014. Insertion Sort. Diakses tanggal 05 Juni 2015 pada  http://arna.lecturer.pens.ac.id/Modul_ASD/8.1%20Insertion-Sort.pdf
  • Anonim. 2013. Algoritmaa Selection Sort. Diakses tanggal 05 Juni 2015 pada  http://www.sepertinya.com/algoritma-c-selection-sort-lengkap.html


THANKYOU!!!

Selamat Mencoba :)
Selain materi diatas terdapat juga beberapa materi struktur data, silahkan klik link di bawah ini :

http://tria-swandewi.blogspot.com/2015/06/searching-sequential-search-dan-binarry.html



Diposting oleh di Tidak ada komentar:

Materi QUEUE

QUEUE

Karakteristik yang membedakan queue (antrian) dari stack adalah cara menyimpan dan mengambil data dengan struktur first in first out (FIFO). Hal ini berarti elemen pertama yang ditempatkan pada queue adalah yang pertama dipindahkan. Contoh yang paling populer untuk membayangkan sebuah queue adalah antrian pada kasir sebuah bank. Ketika seorang pelanggan datang, akan menuju ke belakang dari antrian. Setelah pelanggan dilayani, antrian yang berada di depan akan maju. Pada saat menempatkan elemen pada ujung (tail) dari queue disebut dengan enqueue, pada saat memindahkan elemen dari kepala (head) sebuah queue disebut dengan dequeue.


Karakteristik penting dari antrian adalah :

1. Elemen antrian yaitu item-item data yang terdapat di elemen antrian

2. Front (elemen terdepan dari antrian)

3. Rear (elemen terakhir dari antrian)

4. Jumlah elemen pada antrian (Count)
5. Status antrian


a. Linear Queue (Antrian Lurus)





Keterangan :
F = Front (depan)
R = Rear (belakang)
F menunjuk pengantri paling depan, yaitu pengantri yang siap dilayani.
R menunjuk pengantri paling belakang, yaitu pengantri yang paling terakhir masuk.


PROSES DALAM ANTRIAN LURUS

Prinsip / Konsep Proses :
 FIFO (First In First Out)
 FIFS (First In First Serve)

Proses :
AWAL (Inisialisasi)
INSERT (Sisip, Masuk, Simpan, Tulis)
DELETE (Hapus, Keluar, Ambil/Dilayani, Baca)
RESET (Kembali ke AWAL)

Kondisi Antrian Lurus

Kondisi Antrian
Ciri
a.
b.
c.
d.
e.
KOSONG
PENUH
BISA DIISI
ADA ISINYA
PERLU DIRESET
F = R + 1 dimana saja
R = n – 1
R < n – 1
F < R + 1
F = R + 1 dan R = n - 1














ALGORITMA INSERT
•         Periksa apakah Antrian BISA DIISI
           
                        if ( R < n – 1)
                        {
                                    R = R + 1;
                                    Q[R] = x;
                        }
                        else
                                    cout<<“Antrian Penuh”;

ALGORITMA DELETE

•         Periksa apakah Antrian ADA ISINYA
                        if ( F < R + 1)
                        {
                                    x = Q[F];
                                    F = F + 1;
                                    if ((F=R+1) && (R=n-1))
                                    { F = 0;
                                      R = -1; }
                        }
                        else
                                    cout<<“Antrian Kosong”;


b. Double Ended Queue (Dequeue)

Ilustrasi Deque (Antrian dengan Ujung Ganda)





Keterangan :
L = Left (kiri)
R = Right (kanan)
L menunjuk pengantri yg terakhir masuk di sebelah kiri dan siap dilayani.
R menunjuk pengantri yg terakhir masuk di sebelah kanan dan siap dilayani.

Proses dalam Deque
Prinsip / Konsep Proses :
bukan FIFO, bukan juga LIFO, tergantung kesempatan yang ada.

Proses :
AWAL (Inisialisasi)
INSERT (Sisip, Masuk, Simpan, Tulis)
DELETE (Hapus, Keluar, Ambil/Dilayani, Baca)

Algoritma Lengkap INSERT KIRI
•              Periksa apakah Deque BISA DIISI DARI KIRI
                 void INSERT_KIRI()
                 {      if ( L > 0)
                        {
                                    L = L - 1;
                                    Q[L] = x;
                        }
                        else
                                    cout<<“Antrian Kiri Penuh”;

Algoritma Lengkap INSERT KANAN
•         Periksa apakah Deque BISA DIISI DARI KANAN
                 void INSERT_KANAN()           
                 {      if ( R < n - 1)
                        {
                                    R = R + 1;
                                    Q[R] = x;
                        }
                        else
                          cout<<“Antrian Kanan Penuh”;
                 }

Algoritma Lengkap DELETE KIRI
•         Periksa apakah Deque ADA ISINYA
                 void DELETE_KIRI()
                 {      if (L < R + 1)
                        {
                                    x = Q[L];
                                    L = L + 1;
                        }
                        else
                                    cout<<“Antrian Kosong”;
                 }
Algoritma Lengkap DELETE KANAN
Periksa apakah Deque ADA ISINYA
                 void DELETE_KANAN()
                 {     if (L < R + 1)
                        {
                                    x = Q[R];
                                    R = R - 1;
                        }
                        else
                                    cout<<“Antrian Kosong”;
                 }


Contoh Program QUEUE pada bahasa C++ :

#include<iostream.h>
#include<conio.h>
#include<stdio.h>

#define max 50

typedef struct
{
   int data[max];
   int head;
   int tail;
}Queue;

Queue antrian;

void create()
{
                 antrian.head=antrian.tail=-1;
}

int IsEmpty()
{
                 if(antrian.tail==-1)
   return 1;
   else
   return 0;
}

int IsFull()
{
                 if(antrian.tail==max-1)
   return 1;
   else
   return 0;
}

void Enqueue(int data)
{
                 if(IsEmpty()==1)
   {
                 antrian.head=antrian.tail=0;
      antrian.data[antrian.tail]=data;
      cout<<"Data: "<<antrian.data[antrian.tail]<<" Masuk ke Antrian!!!";
   }
   else if(IsFull()==0)
   {
                 antrian.tail++;
      antrian.data[antrian.tail]=data;
      cout<<"Data: "<<antrian.data[antrian.tail]<<" Masuk ke Antrian!!!";
   }
   else if(IsFull()==1)
   {
                 cout<<"Ruangan Penuh !!"<<endl;
      cout<<data<<"Silahkan tunggu !!!";
   }
}
void Dequeue()
{
                 int i;
   int e = antrian.data[antrian.head];
   if(antrian.tail==-1)
   {
                 cout<<"Data kosong, Tidak ada antrian!"<<endl;
   }
   else
   {
                 for(i=antrian.head;i<antrian.tail-1;i++)
      {
                 antrian.data[i]=antrian.data[i+1];
      }
      antrian.tail--;
      cout<<"Data yang keluar lebih dulu = "<<e<<endl;
   }
}
void clear()
{
                 antrian.head=antrian.tail=-1;
   cout<<"Akhirnyaaa, Ruangan sepi :) "<<endl;
   cout<<"Data Clear";
}
void tampil()
{
                 if(IsEmpty()==0)
   {
    cout<<"Data Dalam Antrian"<<endl;
      cout<<"==================";
      cout<<endl;
      for(int i=antrian.head;i<=antrian.tail;i++)
      {
                 cout<<"| " <<antrian.data[i]<<" |";
      }
   }
   else
   {
                 cout<<"Data kosong, tidak ada antrian!";
   }
}
void main()
{
                 int pil;
   int data;
   create();
   do
   {
                 clrscr();
      cout<<"Implementasi Antrian dengan Struct"<<endl;
      cout<<"==================================";
      cout<<endl;
      cout<<"1. Enqueue"<<endl;
      cout<<"2. Dqueue "<<endl;
      cout<<"3. Print "<<endl;
      cout<<"4. Clear "<<endl;
      cout<<"5. Exit "<<endl;
      cout<<"Masukkan pilihan anda : ";
      cin>>pil;
      switch(pil)
      {
                 case 1:
         {
                 cout<<endl;
            cout<<"Data = ";
            cin>>data;
            Enqueue(data);
            break;
         }
         case 2:
         {
                 cout<<endl;
            Dequeue();
            break;
         }
         case 3:
         {
                 cout<<endl;
            tampil();
            break;
         }
         case 4:
         {
                 cout<<endl;
            clear();
            break;
         }
      }
      getch();
   }
   while(pil!=5);
}


Tampilan setelah progam dijalankan!!



DAFTAR PUSTAKA



  • Anonim. 2014. Queue antrian di Struktur Data. Diakses tanggal 05 Juni 2015 pada http://masiyak.com/queue-antrian-di-struktur-data/
  • Syaviri, Ananda Putri. 2014. Laporan ASD 5 Queue. Diakses tanggal 05 Juni 2015 pada https://www.academia.edu/6668456/LAPORAN_ASD_5_QUEUE

SELAMAT MENCOBA !!!



Diposting oleh di Tidak ada komentar:
Langganan: Postingan (Atom)