BINARY SEARCH & SEQUENSIAL SEARCH

SEARCHING

Searching adalah pencarian data dengan cara menelusuri data-data tersebut. Tempat pencarian data dapat berupa array dalam memori, bisa juga pada file pada External Storage.

Pada umumnya dikenal dua metode Searching antara lain

1.    Sequensial Search

2.    Binary Search

1.    SEQUENSIAL SEARCH

Disebut juga sebagai metode pencarian urut adalah metode pencarian yang paling mudah. Suatu teknik pencarian data dalam arry (1 dimensi) yang akan menelusuri smua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.

Ada 2 Kemungkinan dalam SEQUENSIAL SEARCH

• Kemungkinan terbaik (Best Case) Adalah jika data yang dicari terletak di indeks array terdepan (elemen array pertama) sehingga waktu yang dibutuhkan untuk pencarian data sangat sebentar (Minimal).
•  Kemungkinan terburuk (Worst Case) adalah jika data yang dicari terletak di indeks array terakhir (elemen array terakhir) sehingga waktu yang dibutuhkan untuk pencarian data sangat lama (Maksimal).

2.    BINARY SEARCH

Proses pencarian Binary Search hanya satu dapat dilakukan pada kumpulan data yang sudah di urutkan terlebih dahulu.

 Prinsip dari BINARY SEARCH

1.  Mula-mula diambil posisi awal 0 dan posisi akhir = N-1, kemudian dicari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2. Kemudian data yang dicari dibandingkan dengan data tengah.
2. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah –1.
3. Jika lebih besar, proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah +1.
4. Jika data sama, berarti data ditemukan

CONTOH PROGRAM SEQUENSIAL SEARCH

#include <iostream.h>

#include <conio.h>

void main()

{

    int i;

    int cari,ketemu;

    int A[100];

   cout<<"PROGRAM SEARCHING\n";

   cout<<"masukkan 7 buah data : \n\n";

   for (i=1;i<=7;i++)

   {

   cout<<"masukkan data ke-"<<i<<endl;

   cin>>A[i] ;

   }

   cout<<endl;

    cout<<"Input bilangan yang dicari : ";

    cin>>cari;

    ketemu=0;

    for(i=0;i<=7;i++)

    {

        if (A[i]==cari)

        {

            ketemu=1;

            cout<<"Data ditemukan pada indeks ke-"<<i;

        }

    }

   if (ketemu==0){

       cout<<"Data tidak ditemukan";

    }

 getch();

}

      CONTOH PROGRAM BINARY SEARCH  

#include <iostream.h>

#include <conio.h>

int binary_search(int array[],int size, int elemen);

void main()

{

  const int size = 10;

  int array[size]={0,6,9,12,20,23,29,32,47,79};

  cout<<"Isi dari array: "<<endl;

  for(int i=0;i<size;i++)

  cout<<" "<<array[i];

int elemen;

  int tanda;

  cout<<"\n\n";

  cout<<"Masukkan data yang dicari: ";

  cin>>elemen;

  cout<<"\n\n";

  tanda= binary_search(array,size,elemen);

  if (tanda!=-1)

  cout<<"Data "<<elemen<<" ditemukan pada posisi : array["<<

  tanda<<"],"<<" atau deret ke-"<<(tanda+1);

  else

  cout<<"\n data tersebut tidak ditemukan ";

  getch();

}

int binary_search(int array[],int size,int elemen)

{

  int start=0;

  int end=size - 1;

  int middle;

  int posisi=-1;

  middle=(start + end ) / 2;

  do

  {

   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)

  posisi=middle;

  return posisi;

  }

Referensi : Searching, Menjelaskan tentang searching dan algoritmanya keterangan, I KOMANG SETIA BUANA, S.Kom., MT

SELECTION SORT & INSERTION SORT

SORTING

Suatu proses pengurutan data yang sebelumnya disusun secara acak atau tidak teratur menjadi urut dan teratur menurut suatu aturan tertentu.

Pada umumnya ada 2 macam pengurutan :

1. Pengurutan secara ascending ( urutan naik)
2. Pengurutan secara descending (urutan turun)

Contoh :

Data Acak : 5 6 8 1 3 25 10

Ascending : 1 3 5 6 8 10 25

Descending : 25 10 8 6 5 3 1

Algoritma untuk melakukan Sorting :

1.    Selection Sort

2.    Insertion Sort

3.    BubbleSort

4.    Quick Sort

Selection Sort

Merupakan kombinasi antara sorting dan searching. Untuk setiap proses, akan dicari elemen elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array. Selama proses pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

PROSES SELECTION SORT

• Mencari data terkecil dari data pertama sampai dengan data yang terakhir. kemudian ditukar posisinya dengan data pertama.
• Mencari data terkecil dari data kedua sampai dengan data terakhir, kemudian ditukar posisinya dengan data kedua.
• Mencari data terkecil dari data ketiga sampai dengan data terakhir, kemudian ditukar posisinya dengan data ketiga.
• 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

Insertion Sort

Mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan ke tempat yang seharusnya. Pengurutan dimulai dari data ke 2 sampai dengan data terakhir , jika ditemukan data yang lebih kecil, maka akan di tempatkan (diinsert) di posisiyang seharusnya. Pada penyisipan elemen maka elemen – elemen lain akan bergeser ke belakang.

PROSES INSERTION SORT

• Algoritma ini akan mudah anda kuasi jika sering bermain Game Remi, Domino, dll
• Ide algoritma dari metode insertion sort ini dapat dianalogikan sama seperti mengurutkan kartu.
• Jika suatu kartu dipindah tempatkan menurut posisinya, maka kartu yang lain akan bergeser mundur atau maju sesuai kondisi pemindahanan kartu tersebut.

CONTOH PROGRAM SELECTION SHORT

#include <iostream.h>

#include <conio.h>

#include <stdio.h>

#include <iomanip.h>

main()

{

int x[5];

int i;

int temp;

int minindex;

int j;

clrscr();

cout<<" >>Program Selection Sort << \n" <<endl;

cout<<"masukkan nilai x :\n";

for(i=0; i<5; i++)

{

cout<<"x["<<i<<"] = ";cin>>x[i];

}

cout<<"\n 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();

}

HASIL

CONTOH PROGRAM INSERTION SHORT

#include <iostream>

#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;

 }

}

int main()

{

 cout<<"\t\t\t===PROGRAMINSERTION SORT===\n\n"<<endl;

 //Input Data

 cout<<"Masukkan Jumlah Data : ";

 cin>>n;

 cout<<"\n";

 for(int i=1;i<=n;i++)

 {

  cout<<"Masukkan data ke "<<i<<" : ";

  cin>>data[i];

  data2[i]=data[i];

 }

 insertion_sort();

 cout<<"\n\n";

 //tampilkan data

 cout<<"Data Setelah di Sort : ";

 for(int i=1; i<=n; i++)

 {

  cout<<" "<<data[i];

 }

 cout<<"\n\nSorting Selesai";

 getch();

}

HASIL

Referensi :Sorting, Menjelaskan tentang sorting dan algoritmanya keterangan , I KOMANG SETIA BUANA, S.Kom.,MT

STACK

INISIALISASI STACK

Pada mulanya isi top dengan  -1, karena array dalam C dimulai dari  0, yang berarti stack adalah kosong. 

Top  adalah suatu  variabel  penanda  dalam  STACK  yang  menunjukkan elemen  teratas  Stack  sekarang.

Top  Of  Stack  akan  selalu  bergerak hingga mencapai MAX of STACK sehingga menyebabkan stack penuh.

Fungsi IsFull

Untuk memeriksa apakah stack sudah penuh, maka dapat dilakukan dengan cara memeriksa top of stack jika sudah sama dengan MAX_STACK-1 maka full. Jika belum (masih lebih kecil dari MAX_STACK-1) maka belum full.

FUNGSI PUSH

Untuk memasukkan elemen ke stack, selalu menjadi elemen teratasstack. Tambah satu (increment)   nilai top of stack terlebih dahulu setiap kaliada penambahan elemen stack, asalkan stack masih belum penuh, kemudianisikan  nilai  baru  ke  stack  berdasarkan  indeks  top  of  stack  setelahditambah satu (diincrement).Seperti gambar di berikut ini.

FUNGSI POP

Untuk mengambil elemen teratas dari stack. Ambil dahulu nilai elemen teratas stack dengan mengakses top of stack, tampilkan nilai yang akan diambil terlebih dahulu, baru diincrement nilai Top of Stack sehingga jumlah elemen stack berkurang.

FUNGSI IS EMPTY
Untuk memeriksa apakah stack masih kosong. Dengan cara memeriksa Top of STACK, jika masih -1 maka berarti stack masih osong.


CONTOH PROGRAM STACK

#include <stdio.h>

#include <conio.h>

#include <iostream.h>

#include <iomanip.h>

judul()

{

cout<<"Name :  \nClass : \nNim : "<<endl<<"\n\n";

return 0;

}

main()

{

int plh;

int top=0, i;

int sisa;

char nm[20][20],nim[20][20],kls[20][20];

do{

clrscr();

judul();

cout<<"===================================\n";

cout<<" MENU OPTIONS\n";

cout<<"===================================\n";

cout<<"1.PUSH\n";

cout<<"2.POP\n";

cout<<"3.ISFULL/ISEMPTY\n";

cout<<"4.CLEAR \n";

cout<<"5.VIEW \n";

cout<<"6.EXIT\n";

cout<<"===================================\n";

cout<<"Input Options : "; cin>>plh;

if (plh<=6)

{

switch(plh)

{

case 1:

if(top==10)

{

clrscr();

judul();

cout<<"sory,data is full";

getch();

}

else

{

cout<<"\nInput name : "; gets(nm[top+1]);

cout<<"Input NIM : "; cin>>nim[top+1];

cout<<"Input Class : "; cin>>kls[top+1];

clrscr();

judul();

cout<<"data has been entered";

getch();

top++;

}

break;

case 2:

if(top<1)

{

clrscr();

judul();

cout<<"Data is Empty";

}

else

{

cout<<"\nDeleted data :"<<top<<"\n\n";

cout<<"Name : "<<nm[top]<<endl;

cout<<"NIM : "<<nim[top]<<endl;

cout<<"Class : "<<kls[top]<<endl;

top--;

getch();

clrscr();

judul();

cout<<"data has been Deleted";

}

getch();

break;

case 3:

if(top==10)

{

clrscr();

judul();

cout<<"Data has been Full";

}

else if(top>=1)

{

sisa=10-top;

clrscr();

judul();

cout<<"Now Data is still not fully, you have a "<<sisa<<" data space";

}

else if(top==0)

{

clrscr();

judul();

cout<<"Now Data is Empty";

}

getch();

break;

case 4:

clrscr();

judul();

top=0;

cout<<"Data has removed all";

getch();

break;

case 5:

cout<<"NO || NAME || NIM || CLASS ||\n";

if (top==0)

cout<<"Data Is Empty";

else

for(i=1; i<=top; i++)

{

cout<<setiosflags(ios::left)<<setw(8)<<i;

cout<<setiosflags(ios::left)<<setw(17)<<nm[i];

cout<<setiosflags(ios::left)<<setw(17)<<nim[i];

cout<<setiosflags(ios::left)<<setw(10)<<kls[i]<<endl;

}

getch();

break;

case 6:

cout<<"\n\nEXIT.........";

getch();

break;

}

}

else

{

cout<<"incorrect Option , Please Input 1-9";

getch();

}

}

while(plh!=6);

}

Hasil 

Referensi :Stack, Menjelaskan tentang definisi dan operasi dasar dari stack keterangan , I KOMANG SETIA BUANA, S.Kom.,MT