Struktur Data Searching

Pengertian 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. Jika diketahui ada sebuah array / barisan data bernama A yang menampung 10 data yang bertipe integer sebagai berikut  :

            A={1,2,3,4,8,5,7,9,6,0} 
kita diberi tugas untuk mencari beberapa data misal :
Jika data yang akan dicari dalam array A adalah 6, maka dengan cepat dapat kita ketahui bahwa data 6 ada dalam array A pada index ke-9 (index pada array dimulai dari 0). Sedangkan jika data yang akan dicari dalam array A adalah 12, maka dapat disimpulkan bahwa array A tidak memiliki data 12 tersebut. Permasalahannya adalah bagaimana mengimplementasikannya kedalam program?
Pada umumnya dikenal dua metode searching antara lain :

1. Sequensial search 
Disebut juga sebagai metode pencarian urut adalah metode pencarian yang paling mudah. Suatu teknik pencarian data dalam array ( 1 dimensi ) yang akan menelusuri semua 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 dapat dilakukan pada kumpulan data yang sudah diurutkan terlebih dahulu. 

Prinsip dari Binary Search

·         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.

·         Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah –1.

·         Jika lebih besar, proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah +1.

·         Jika data sama, berarti data ditemukan

Contoh 

Contoh Program Searching (Sequensial)

#include<stdio.h>
#include<iostream.h>
#include<conio.h>
void main()
{
 //deklarasi variabel
 int A[10],index[10], i,j,k,n;

 //proses penginputan data
   cout<<"Masukkan jumlah data [Max 10] : ";
   cin>>n;

 for(i=0;i<n;i++)
 {
    cout<<"Masukkan Data ke - "<<(i+1)<<" = ";
      cin>>A[i];
 }

 //memasukkan data yang akan dicari ke dalam K
   cout<<"Masukkan data yang anda akan cari : ";
   cin>>k;

 //proses pencarian data
 j=0;
 for (i=0;i<n;i++)
 {
  if(A[i]==k)
  {
   index[j]=i;
   j++;
  }
   }

 //jika data ditemukan dalam array
 if (j>0)
 {
  cout<<"Data" <<k<< "yang dicari ada" <<j<< "buah"<<endl;
      cout<<"Data tersebut terdapat dalam index ke : ";
    for(i=0;i<j;i++)
  {
         cout<<index[i]<<" ";
  }
      cout<<endl;
 }

 //jika tidak ditemukan
 else
 {
      cout<<"Data tidak ditemukan dalam array"<<endl;;
 }
  getch();
}

Screenshot Program Searching (Squensial)

Contoh Program Searching (Binary)

#include<stdio.h>
#include<conio.h>
#include<iostream.h>
void main()
{
 //deklarasi variabel
 int A[10],n, i,j,k,tkr,right,left,middle,tm;

 //proses penginputan data
   cout<<"Masukkan jumlah data = ";
   cin>>n;
 for(i=0;i<n;i++)
 {
    cout<<"Masukkkan data ke - "<<(i+1)<<" = ";
      cin>>A[i];
 }
   cout<<"Masukkan data yang akan anda cari :";
   cin>>k;

 //proses pengurutan data
 for(i=0;i<n;i++)
 {
  for(j=i+1;j<n;j++)
  {
   if (A[i]>A[j])
   {
    tkr=A[i];
    A[i]=A[j];
    A[j]=tkr;
         }
      }
   }

 //proses pencarian data
 tm=0;
 right=n;
 left=0;
 while(right>=left)
 {
  middle=(right+left)/2;
  if(A[middle]==k)
  {
   tm++;
  }
  if(A[middle]<k)
  {
   left=middle+1;
  }
  else
  {
   right=middle-1;
  }
   }
 if (tm>0)
   {
    cout<<"Data " << k << " yang dicari ada dalam array"<<endl;
   }
 //jika tidak ditemukan
 else
 {
    cout<<"Data tidak ditemukan dalam array"<<endl;
   }
   getch();
}

Screenshot Program Searching (Binary)

Selection sort dan Insertion sort

SELECTION SORT

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

Proses pada 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

Insertion sort adalah sebuah metode pengurutan data dengan menempatkan setiap elemen data pada pososinya dengan cara melakukan perbandingan dengan data – data yang ada. Algoritma ini akan mudah anda kuasi jika sering bermain Game Remi, Domino, Main Minum, 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 Algoritmanya:

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

Step 1

Bandingkan data index ke 0 dan ke 1, Jika data index ke 1 lebih kecil, datanya ditukar

Step 2

Bandingkan data index ke 2 dengan ke 1 dan 0, Jika lebih kecil, selipkan pada posisi yang tepat

Step 3

Bandingkan data index ke 3 dengan data didepannya. Jika lebih kecil, selipkan pada posisi yang tepat. Jika tidak biarkan data tersebut

Step 4

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.

Step 5

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 Sorting

#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 selection_sort()
{
 int pos,i,j;
   for(i=0;i<n-1;i++)
   {
    pos=i;
      for(j=i+1;j<n;j++)
      {
       if(data[j]<data[pos])pos=j;
      }
      if(pos!=i) tukar(pos,i);
   }
   cout<<"selection sort selesai !"<<endl;
   cout<<"Data : "<<endl;
   for(int i=0;i<n;i++)
   {
    cout<<data[i]<<" ";
   }
   cout<<endl;
}

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;
   }
   cout<<"insertion sort selesai ! "<<endl;
   cout<<"Data : "<<endl;
   for(int i=0;i<n;i++)
   {
    cout<<data[i]<<" ";
   }
   cout<<endl;
}

void input()
{
 cout<<"Masukkan jumlah data = ";
   cin>>n;
   for(int i=0;i<n;i++)
   {
    cout<<"Masukkan data ke - "<<(i+1)<<" = " ;
      cin>>data[i];
      data2[i]=data[i];
   }
}


void main()
{
 int pil;
   clrscr();
   do
   {
      clrscr();
    cout<<"1. Input Data"<<endl;
    cout<<"2. Selection Sort"<<endl;
    cout<<"3. Insertion Sort"<<endl; //tambahkan
    cout<<"4. Exit"<<endl;
      cout<<"Masukkan Pilihan anda = ";
      cin>>pil;

    switch(pil)
    {
       case 1: input();break;
       case 2: selection_sort();break;
       case 3: insertion_sort();break;  //tambahkan
    }
    getch();
   }
   while(pil!=4);
}

Screenshot program Sorting

Struktur Data Queue

Pengrtian Queue

Queue (antrian ) adalah sekumpulan data yang mana penambahan elemen hanya bisa dilakukan pada suatu ujung disebut dengan sisibelakang(rear), dan penghapusan(pengambilan elemen) dilakukan lewat ujung lain (disebut dengan sisi depan atau front).

Data yang pertama masuk dalam antrian, akan keluar terlebih dahulu.

Queue atau antrian prinsip yang digunakan adalah “Masuk Pertama Keluar Pertama” atau FIFO (First In First Out). 

Jenis-jenis Queue :

–        Linear Queue

–        Double Ended Queue (Dequeue)

LINEAR QUEUE

Ilustrasi Antrian Lurus 

Keterangan :

F = Front (depan)

R = Rear (belakang)

F menunjuk pengantri paling depan, yaitu pengantri yg siap dilayani.

R menunjuk pengantri paling belakang, yaitu pengantri yg paling terakhir masuk.

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	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 lengkap INSERT

 Periksa apakah Antrian BISA DIISI

                                if ( R < n – 1)

                                {

                                                R = R + 1;

                                                Q[R] = x;

                                }

                                else

                                                cout<<“Antrian Penuh”;

Algoritma lengkap 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”;

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.

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)

Kondisi Double Ended Queue

	Kondisi Antrian	Ciri
a. b. c. d. e. f.	KOSONG PENUH KIRI PENUH KANAN BISA DIISI DARI KIRI BISA DIISI DARI KANAN ADA ISINYA	L = R + 1 dimana saja L = 0 R = n – 1 L  > 0 R < n – 1 L  < R + 1

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

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

#define max 10

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 !!!";
   }
   else if(IsFull()==0)
   {
            antrian.tail++;
      antrian.data[antrian.tail]=data;
      cout<<"Data "<<antrian.data[antrian.tail]<<"Masuk !!!";
   }
   else if(IsFull()==1)
   {
            cout<<"Ruangan Penuh !!"<<endl;
      cout<<data<<"Ga Bisa Masuk !!!";
   }
}
void Dequeue()
{
            int i;
   int e = antrian.data[antrian.head];
   if(antrian.tail==-1)
   {
            cout<<"Ga Ada antrian... Data Kosong"<<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<<"Duh Lega, Ruangan jadi ga sumpek... "<<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<<"Ga ada antrian... Data kosong";
   }
}
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);
}

Screenshot Program Queue