Sabtu, 06 Juni 2015

BINARY SEARCH

BINARY SEARCH

  • Pengertian

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 :
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.
Beban komputasi juga lebih kecil karena pencarian dilakukan dari depan, belakang, dan tengah.
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.


Kekurangan binary search yaitu data harus disorting dahulu dan Algoritma lebih rumit. Berikut ilustrasi pencarian menggunakan binary search dengan bantuan tabel. Misalkan kita mempunyai data sebagai berikut : {-5, -3, -1, 0, 1, 3, 5, 7}. Data yang kita cari adalah 5. Untuk menyelesaikan soal diatas, maka diselesaikan dengan cara berikut :
Diketahui nilai kiri=0 (nilai awal array) dan nilai kanan = 8. Rumus posisi tengah adalah (kanan + kiri)/2. Jadi Nilai tengah pada langkah pertama yaitu (8+0)/2=4. Jika dimasukkan kedalam tabel akan menunjuk nilai 0 (berwarna orange). Kemudian dibandingkan dengan nilai yang dicari (3), karena nilai yang dicari lebih besar dari data ditengah maka pencarian di alihkan ke sebelah kanan dengan batas kiri (awal pencarian) merupakan nilai tengah yakni 4.
Nilai tengah pada langkah kedua yaitu (8+4)/2=6. Jika dimasukkan ke dalam tabel maka akan menunjuk nilai 3 (berwarna orange). Kemudian dibandingkan lagi dengan nilai yang dicari (5), karena nilai yang dicari masih lebih besar dari nilai tengah, maka pencarian dialihkan lagi ke kanan dengan batas kiri (awal pencarian) merupakan nilai tengah yakni 6.
Nilai tengah pada langkah ketiga yaitu (8+6)/2=7. Jika dimasukkan ke dalam tabel maka akan menunjuk nilai 5 (berwarna orange). Kemudian dibandingkan lagi dengan nilai yang dicari (5), setelah dibandingkan nilainya sama, maka pencarian selesai dengan keterangan data ditemukan.
Untuk lebih jelasnya lagi perhatikan algoritma deskriptif binary search berikut :
Input seluruh data kedalam array
Input data yang dicari
Tentukan nilai kiri, kanan, dan tengah dengan rumus :
Kiri sama dengan nol
Kanan lebih kecil dari jumlah data
Tengah sama dengan hasil kanan dikurangi hasil kiri dibagi dua.
Jika elemen tengah tidak sama dengan data yang dicari, maka :
Jika elemen tengah lebih besar dari data yang dicari, maka pencarian dilakukan pada setengah array pertama. Caranya dengan menggunakan perintah kiri sama dengan tengah ditambah satu.
Jika elemen tengah lebih kecil dari data yang dicari, maka pencarian dilakukan pada setengah array berikutnya. Caranya dengan menggunakan perintah kanan sama dengan tengah dikurangi satu.
Tengah sama dengan kiri ditambah (kanan - kiri) dibagi dua.
Jika elemen tengah sama dengan data yang dicari, maka data ditemukan. Sedangkan jika elemen tengah tidak sama dengan data yang dicari, maka data tidak ditemukan.

  • Contoh Program dalam bahasa C++ :

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

void main()
{
int data[10] = {1,2,3,4,5,6,7,8,9,10};
   int tengah, kiri, kanan;
   bool ketemu;
   int cari;

   kiri = 0;
   kanan = 9;
   ketemu = false;

   cout<<"Masukan Data yg di cari : ";
   cin>>cari;

   tengah = (kiri + kanan) /2;

   while (ketemu==false && kanan>=kiri)
   {
    if (data[tengah] == cari)
      {
      ketemu = true;
      }
      else
      {
      if (data[tengah] < cari)
         {
          kiri = tengah + 1;
         }
         else
         {
          kanan = tengah - 1;
         }
         tengah = (kiri + kanan) / 2;
      }

   }
   if (ketemu == true)
   {
    cout<<"Data ketemu, pd index ke="<<tengah;
   }
   else
   {
    cout<<"\nData tidak ketemu";

   getch();
   }
}
  • Ini hasil dari contoh coding diatas :











Semoga bermanfaat untuk kita semua :) Sekian dan Terimakasih sampai jumpa dipost selanjutnya :) 

Salam STIKOMERS www.stikom-bali.ac.id
Diposting oleh di Tidak ada komentar:

SEQUENTIAL SEARCH

SEQUENTIAL SEARCH

  • Pengertian

Sequential Search adalah teknik pencarian data dimana data dicari secara urut dari depan ke belakang atau dari awal sampai akhir. berdasarkan key yang di cari Kelebihan dari proses pencarian secara sequential ini
jika data yang dicari terletak didepan, maka data akan ditemukan dengan cepat.
Tetapi dibalik kelebihannya ini, teknik ini juga memiliki kekurangan.
jika data yang dicari terletak dibelakang atau paling akhir, maka akan membutuhkan waktu yang lama dalam proses pencariannya.
beban komputer akan semakin bertambah jika jumlah data dalam array sangat banyak.
Proses:
Mulai dari awal(atau dari akhir) cek seluruh record dalam array atau list, baca satu persaru
Temukan record sesuai dengan key yang dicari.
Proses Searching berhenti karena salah satu alasan.
Success – Found the target key
End of List – No more records to compare
Diaplikasikan pada Array (sorted &unsorted) atau Linked List.
  • Sequential Search Analysis

Bagaimana worst case dan average case untuk metode sequential search?
Kita harus mendefinisikan O-notation untuk nilai dari operasi yang dibutuhkan dalam pencarian
Jumlah operasi pencarian bergantung pada nilai n, yaitu jumlah elemen dalam list.
Worst Case Time for Sequential Search:
Untuk sebuah array dengan elemen, makaworst case time untuk sequential search  requires n array accesses: O
Kondisi yang mengharuskan pengecekanterhadap semua elemen array (record) adalah:  Record yang dicari berada pada posisiterakhir dari array.
Setelah pengecekan seluruh elemen array,ternyata record yang dicari tidak berhasilditemukan dalam array tersebut.

  • Algoritma Sequential Search

i ? 0
ketemu ?false
Selama (tidak ketemu) dan (i < N) kerjakan baris 4
Jika (Data[i] = key) maka
ketemu ?true
jika tidak
i ?i+1
Jika (ketemu) maka
i adalah indeks dari data yang dicari
jika tidak
data tidak ditemukan
  • Contoh Program dalam bahasa C++ :

#include <iostream>
#include <conio>

void main(){
const int n = 5;
   int A[n]={24,1,25,40,50};
   int B=0;
   int C;
   cout<<"Masukkan angka yang di cari : "; cin>>C;
   for(int i=0;i<n;i++)
   {
    if(A[i]==C)
    {
    for(int k=i;k<n;k++){
            A[k]=A[k+1];
    }
    }
   }
   for(int i=0;i<n;i++){
   cout<<"isi array ke-"<<i+1<<" adalah : "<<A[i]<<endl;
   }
getch();
}
  • Ini hasil dari contoh coding diatas :











Semoga bermanfaat untuk kita semua :) Sekian dan Terimakasih sampai jumpa dipost selanjutnya :) 

Salam STIKOMERS www.stikom-bali.ac.id
Diposting oleh di Tidak ada komentar:

BUBBLE SORT

BUBBLE SORT
  • Pengertian

Diberi nama “Bubble” karena proses pengurutannya secara berangsur-angsur bergerak/berpindah ke posisi yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda. Bubble sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya.
Pengurutan ascending : jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar.
Pengurutan descending : jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar.
Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau ke kanan, tergantung jenis pengurutannya. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya dari 0 sampai dengan iterasi sebanyak n-1.

 Pengurutan akan berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai pengurutan yang diinginkan.
  • Contoh Program dalam bahasa C++ :

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

void main()
{
int i,j,data[5],temp;
   for (i=0; i<5; i++)
   {
    cout<<"Masukan data index ke-"<<i<<" : ";
      cin>>data[i];
   }
   for (i=0; i<5; i++)
   {
    for (j=0; j<5; j++)
      {
      if (data[j]>data[j+1])
         {
          //tuker datanya
            temp = data[j];
            data[j] = data[j+1];
            data[j+1] = temp;

         }
      }
   }

   cout<<"Data hasil pengurutan : ";
   for (i=0; i<5; i++)
   {
    cout<<" "<<data[i];
   }
   getch();

}
  • Ini hasil dari contoh coding diatas :












Semoga bermanfaat untuk kita semua :) Sekian dan Terimakasih sampai jumpa dipost selanjutnya :) 

Salam STIKOMERS www.stikom-bali.ac.id

Diposting oleh di Tidak ada komentar:

INSERTION SORT

INSERTION SORT

  • Pengertian

Insertion sort adalah sebuah metode pengurutan data dengan menempatkan setiap elemen data pada pososinya dengan cara melakukan perbandingan dengan data – data yang ada.
a.       Cara kerja insertion sort mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya.
b.       Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (di-insert) diposisi yang seharusnya.
c.       Pada penyisipan elemen, maka elemen- elemen lain akan bergeser ke belakang.
d.       Algoritma ini akan mudah anda kuasi jika sering bermain Game Remi, Domino, Main Minum, dll
e.       Ide algoritma dari metode insertion sort ini dapat dianalogikan sama seperti mengurutkan kartu.

f.       Jika suatu kartu dipindah tempatkan menurut posisinya, maka kartu yang lain akan bergeser mundur atau maju sesuai kondisi pemindahanan kartu tersebut.
  • CONTOH :
  • Contoh Algoritma

Data awal sebelum di urutkan, asumsi pertama anggaplah data indek ke- sudah benar .
 Data awal sebelum di urutkan, asumsi pertama anggaplah data indek ke-0 sudah benar.
 Bandingkan data index ke 0 dan ke 1, Jika data index ke 1 lebih kecil, datanya ditukar 
       Bandingkan data index ke 2 dengan ke 1 dan 0, Jika lebih kecil, selipkan pada posisi yang tepat.
 Bandingkan data index ke 3 dengan data didepannya, Jika lebih kecil, selipkan pada posisi yang tepat. Jika tidak biarkan data tersebut.
       Bandingkan data index ke 4 dengan data didepannya, Jika lebih kecil, selipkan pada posisi yang tepat. Data yang lain akan mundur posisinya, karena ada data yang maju.
       Bandingkan data index ke 5 dengan data didepannya, Jika lebih kecil, selipkan pada posisi yang tepat. Data yang lain akan mundur posisinya, karena ada data yang maju.
  •  Contoh Program dalam bahasa C++ :

 #include <iostream>
#include <conio>

int arr[]={8,6,9,3,5};
void insertion_sort (int arr[], int length){
int j, temp;

for (int i = i; i < length; i++){
j = i;

while (j > 0 && arr[j] < arr[j-1]){

 temp = arr[j];

 arr[j] = arr[j-1];

 arr[j-1] = temp;
 j--;

}

}
}

void main(){
insertion_sort(arr,5);
for(int i=0;i<5;i++){
cout<<arr[i]<<", ";
}

getch();

}
  •  Ini hasil dari contoh coding diatas :












Semoga bermanfaat untuk kita semua :) Sekian dan Terimakasih sampai jumpa dipost selanjutnya :) 

Salam STIKOMERS www.stikom-bali.ac.id

Diposting oleh di Tidak ada komentar:

SELECTION SORT

SELECTION SORT

  • Pengertian

      a.  Merupakan sebuah metode pengurutan.
        b. Memindahkan elemen dengan cara membandingkan elemen sekarang dengan                 elemen yang berikutnya sampai dengan elemen terakhir.
         c. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat             posisinya dan kemudian ditukar dan begitu seterusnya.

  •  Proses 
         a.Mencari data terkecil dari data pertama sampai dengan data yang terakhir. kemudian     ditukar posisinya dengan data pertama.
         b.Mencari data terkecil dari data kedua sampai dengan data terakhir, kemudian ditukar posisinya dengan data kedua.
        c.Mencari data terkecil dari data ketiga sampai dengan data terakhir, kemudian ditukar    posisinya dengan data ketiga.
       d.Begitu seterusnya sampai semua data terurut naik. Apabila terdapat n buah data yang    akan diurutkan, maka membutuhkan (n-1) langkah pengurutan, dengan data terakhir,    yaitu data ke n tidak perlu diurutkan karena hanya tinggal data satu-satunya.

  • Contoh
         Terdapat suatu variable array dimana nilai dalam array tersebut : NILAI[8]
      = { 44, 55, 12, 42, 94, 18, 6, 67 }
  • Penyelesaian

  • Contoh Program dalam bahasa C++ :

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

void main()
{
   //Buat variable
int data[5];
   int temp, i, j, temp_index;

   //Inputin data
   for (i=0; i<5; i++)
{
    cout<<"Masukan data index ke-"<<i<<" : ";
cin>>data[i];
   }

   //Metode Selection Sort
   for(i=0; i<5; i++)
   {
      temp = data[i];
      temp_index = i;
for (j=i+1; j<5; j++)
      {
      if (temp > data[j])
         {
          temp = data[j];
            temp_index = j;
         }
      }
      data[temp_index] = data[i];
      data[i] = temp;
   }

   cout<<"Hasil Pengurutan : ";
   for(i=0; i<5; i++)
   {
    cout<<data[i]<<" ";
   }

   getch();
}
  • Ini hasil dari contoh coding diatas :

Semoga bermanfaat untuk kita semua :) Sekian dan Terimakasih sampai jumpa dipost selanjutnya :) 

Salam STIKOMERS www.stikom-bali.ac.id

Diposting oleh di Tidak ada komentar:

QUEUE

QUEUE

  • Queue Dengan Array

a.       Bersifat FIFO
b.       Elemen yang pertama masuk ke antrian akan keluar pertama kalinya
c.       DEQUEUE adalah mengeluarkan satu elemen dari suatu Antrian
d.       Antrian dapat dibuat dengan menggunakan: Liniear Array dan Circular Array 
  • Queue Linier Array
a.       Terdapat satu buah pintu masuk di suatu ujung dan satu buah pintu keluar di ujung satunya
b.       Sehingga membutuhkan 2 variabel : Head dan Tail
  • Operasi-operasi:
Create()
a.       Untuk menciptakan dan menginisialisasi Queue
b.       Dengan cara membuat Head dan Tail  = -1 
  • IsEmpty()

a.       Untuk memeriksa apakah Antrian sudah penuh atau belum
b.       Dengan cara memeriksa nilai Tail, jika Tail = -1 maka empty
c.       Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah
d.       Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian kebelakang, yaitu menggunakan nilai Tail.
  • Fungis IsFull

a.       Untuk mengecek apakah Antrian sudah penuh atau belum
b.       Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1 adalah batas elemen array pada C) berarti sudah penuh.
  • Enqueue

a.       Untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu ditambahkan di elemen paling belakang
b.       Penambahan elemen selalu menggerakan variabel Tail dengan cara increment counter Tail terlebih dahulu.
  • Dequeue()

a.       Digunakan untuk menghapus elemen terdepan/pertama (head) dari Antrian
b.       Dengan cara menggeser semua elemen antrian kedepan dan mengurangi Tail dgn 1
c.       Penggeseran dilakukan dengan menggunakan looping.

  • Clear()


a.       Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan Head = -1
b.       Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai -1 sehingga elemen-elemen Antrian tidak lagi terbaca.
  • Tampil()

a.       Untuk menampilkan nilai-nilai elemen Antrian
b.       Menggunakan looping dari head s/d tail 
  • Dari penjelasan diatas mari kita rubah kedalam bahasa pemograman C++ :

#include <iostream>
#include <conio>

int tail, max, head;
int data[5];
int menu;
void create()
{
tail = -1;
   head = 0;
   max = 4;
}

bool isfull()
{
if (tail==max)
   {
    return true;
   }
   else
   {
    return false;
   }
}
bool isempty()
{
if (tail<head)
   {
    return true;
   }
   else
   {
    return false;
   }
}
void clear ()
{
tail=-1;
}
void main()
{
create(); // panggil prosedur create
   home:
clrscr();
   cout<<"Silahkan pilih salah satu"<<endl;
   cout<<"1. EnQueue"<<endl;
   cout<<"2. DeQueue"<<endl;
   cout<<"3. Print"<<endl;
   cout<<"4. Clear"<<endl;
   cout<<"Pilih salah satu (1-4) : ";
   cin>>menu;
   switch(menu)
   {
    case 1:
      if (isfull()==true)
         {
          cout<<"Antrian Penuh";
         }
         else
         {
          tail++;
            cout<<"Masukan data ke antrian : ";
            cin>>data[tail];
         }
         getch();
         goto home;
      break;

      case 2:
      if(isempty()==true)
         {
          cout<<"Antrian kosong";
         }
         else
         {
          cout<<"Data yg keluar adalah : ";
            cout<<data[head];
            for (int i=0; i<tail; i++)
            {
            data[i] = data[i+1];
            }
            tail--;
         }
         getch();
         goto home;
      break;
      if(isempty()==true)
         {
          cout<<"Antrian kosong";
         }
         else
         {
      cout<<"Isi data pada antrian : ";
            for(int i=head; i<=tail; i++)
            {
            cout<<data[i]<<" ";
            }
         }
         getch();
         goto home;
      break;
   }
getch();
}

  • Setelah pengcodingan berhasil maka akan tampi seperti dibawah ini :

Semoga bermanfaat untuk kita semua :) Sekian dan Terimakasih sampai jumpa dipost selanjutnya :) 

Salam STIKOMERS www.stikom-bali.ac.id



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