Searching (Sequential dan Binary Search)

Searching

Searching adalah suatu proses pencarian data dengan cara menelusuri data-data tersebut. Tempat pencarian data bisa dari array dalam memori, bisa juga pada file pada external storage.

Contoh searching :

·         Jika diketahui ada sebuah array / barisan data bernama A yang menampung 10 data yang bertipe integer sebagai berikut  : A={1,9,13,23,7,12} 

·         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 7 ada dalam array A pada index ke-4 (index pada array dimulai dari 0).

·         Sedangkan jika data yang akan dicari dalam array A adalah, maka dapat disimpulkan bahwa array A tidak memiliki data 2 tersebut.

Pada umumnya dikenal dua metode searching antara lain :

1. Sequensial search
2. Binary Search

Sequensial sort(pencarian berurutan)

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.

Sequensial search memiliki 2 kemungkinan. Best case dan worst case.

·         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  mendekati akhir atau malah yang terakhir (elemen array terakhir) sehingga waktu yang dibutuhkan untuk pencarian data sangat lama (maksimal).

Contoh koding sequensial search

#include <iostream> using namespace std; #include <conio.h> #include <iomanip> int main() {       int data_c[10] = {7,9,2,10,15,4,5,6,13,11};       int caridata, i, flag = 0;       cout<<"PENCARIAN DENGAN SEQUENTIAL SEARCH"<<endl;       cout<<"----------------------------------"<<endl;       cout<<"Data   : ";             for(int n=0; n<10; n++)                   cout<<setw(4)<<data_c[n];       cout<<endl;       cout<<"\nMasukkan data yang ingin Anda cari : ";       cin>>caridata;            for(i = 0; i<10; i++)       {             if(data_c[i]==caridata)             {                   flag = 1;                   break;             }       }           if(flag==1)       {             cout<<"Data ditemukan pada indek ke-"<<i<<endl;       }       else       {             cout<<"Data tidak ditemukan"<<endl;       }       getch();       return EXIT_SUCCESS; }

Binary Search

Proses pencarian binary search hanya dapat dilakukan pada kumpulan data yang sudah diurutkan terlebih dahulu, karena array yang menyimpan data tersebut akan di bagi 2 dengan 3 variabel yaitu tengah, awal dan akhir.

Algoritma 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

Keuntungan dari binary search ini adalah dapat pencarian dapat dilakukan dengan mudah, apalagi jika data yang dihandle jumlah nya banyak.

Sedangkan kelemahannya adalah data harus diurutkan terlebih dahulu sebelum dilakukan pencarian, sehingga proses yang diperlukan lebih banyak.

Contoh koding C++ binary search

#include<iostream> #include<stdio> int main ()  {  int n, angka[12], awal, akhir, tengah, temp, key;  bool ketemu = false;  cout<<"Masukan jumlah data : ";  cin>>n;  for(int i=0; i<n; i++)  {   cout<<"Angka ke - ["<<i<<"] : ";   cin>>angka[i];  }  for (int i=0; i<n; i++)  {   for(int j=0; j< n-i-1; j++)   {    if(angka [j] > angka [j+1])    {     temp=angka[j];     angka[j]=angka[j+1];     angka[j+1]=temp;    }   }  }  cout<<"Data yang telah diurutkan adalah : ";  for(int i=0; i<n; i++)  {   cout<<angka[i]<<" ";  }  cout<<"\n Masukan angka yang dicari : ";  cin>>key;  awal=0;  akhir=n-1;  while(awal<=akhir)  {   tengah=(awal + akhir)/2;   if(key == angka[tengah])   {    ketemu=true;    break;   }   else if (key < angka [tengah])   {    akhir = tengah -1;   }   else   {    awal = tengah +1;   }  }  if (ketemu == true)   cout<<"Angka ditemukan!";  else   cout<<"Angka tidak ditemukan";   return 0;  }

Source : Presentasi Matakuliah Struktur Data Stikom Bali

Sequensial Search

Binary Search

Read More

Sorting (selection sort dan insertion sort)

Sorting adalah 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 pengurutan data :

·         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

Selection Sort

1. Merupakan kombinasi antara sorting dan searching
2. 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
3. Selama proses pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

Untuk ilustrasi bisa di lihat di gambar di bawah

Data : 5, 1, 12, -5, 16, 2, 12, 14

Contoh coding  selection sort

#include <iostream.h> #include <stdio> #include <conio.h> int selectionsort (int array[], const int size)  {     int i, j, kecil, temp;     for (i=0; i<size; i++)     {         kecil=i;         for (j=i; j<size; j++)         {              if (array[kecil]>array[j])              {                   kecil = j;              }         }         temp = array [i];     array[i] = array[kecil];     array[kecil] = temp;     }  } int main() {     int NumList[8] = {5, 34, 32, 25, 75, 42, 22, 2};     int temp;     cout<<"Data sebelum diurutkan: \n";     for (int d=0; d<8; d++)     {          cout<<setw(3)<<NumList[d];     }     cout<<"\n\n";     selectionsort(NumList,8);     cout<<"Data setelah diurutkan:\n";     for (int iii=0; iii<8; iii++)     cout<<setw(3)<<NumList[iii]<<endl<<endl;     getch(); }

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

#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<<"INSERTION SORT PROGRAM"<<endl;     cout<<"Jumlah Data : ";    cin>>n;     for(int i=1;i<=n;i++)     {         cout<<"Data ke "<<i<<"   : ";    cin>>data[i];         data2[i]=data[i];     }     insertion_sort();     cout<<"Data Setelah di Sort : ";     for(i=1; i<=n; i++)     {         cout<<" "<<data[i];     } }

Source : Presentasi Matakuliah Struktur Data Stikom Bali “Sorting”

Selection sort

Insertion sort

Read More

Queue

Queue atau antrian. Pengertian antrian pada system computer sama dengan antrian yang kita alami sehari-hari seperti antrian pelanggan yang ingin membayar barang di kasir, antrian kendaraan yang ingin melewati jalan tol. Aturan dasar pada antrian adalah hanya pelanggan yang ada di depan meja kasir lah yang akan dilayani dan jika ada pelanggan yang baru datang maka dia harus mengantri dari belakang antrian, sehingga queue memiliki sifat FIFO(First In First Out).

Queue adalah sebuah array yang bertipe data yang sama yang memiliki 2 buah variable yaitu ‘head’ dan ‘tail’ yang berfungsi sebagai penanda ujung-ujung dari sebuah queue. Proses penambahan data pada queue dinamakan ‘Enqueue’ dan pengurangan data di sebut ‘Dequeue’. Dan sama juga seperti stack, dimana ada proses pengecekan apakah queue itu kosong sebelum di ambil(IsEmpty) atau queue itu penuh sebelum ditambahkan data baru(IsFull).

Contoh coding queue

#include<iostream.h> #include <stdio.h> #include <conio.h> typedef struct { int data [6]; int head; int tail; } Queue; Queue antri; void Create() { antri.head=antri.tail=-1; } int kosong() { if(antri.tail==-1) return 1; else return 0; } int penuh() { if(antri.tail==6-1) return 1; else return 0; } void Enqueue(int data) {             if(kosong()==1)             {                         antri.head=antri.tail=0;                         antri.data[antri.tail]=data;                         void show();                         {                                     if(kosong()==0)                                                                        {                                                 for(int i=antri.head;i<=antri.tail;i++)                                                 {                                                             cout<<antri.data[i];                                                 }                                     }                                     else                                                 cout<<"Data Anda Kosong !\n";                                                                         }             }             else             if(penuh()==0)                        {                         antri.tail++;                         antri.data[antri.tail]=data;             } } int Dequeue() {             int i;             int e=antri.data[antri.head];             for(i=antri.head;i<=antri.tail-1;i++)                         {                         antri.data[i]=antri.data[i+1];                                     }             antri.tail--;                         return e;             } void clear() { antri.head=antri.tail=-1; cout<<"Data sudah diclearkan"; } void show() {             if (kosong()==0)             {                         for (int i=antri.head;i<=antri.tail; i++)                         {                                     cout<<antri.data[i]<<" ";                         }             }             else             {                         cout<<"Data Anda Kosong\n";             } } void main() { int pil; int data; Create();  do { clrscr(); printf ("\n======== MENU ========\n"); printf ("  1. Enqueue\n"); printf ("  2. Dequeue\n"); printf ("  3. show\n"); printf ("  4. Destroy\n"); printf ("  5. Keluar\n"); printf ("======================\n"); printf ("Masukkan Pilihan Anda : "); cin>>pil; switch(pil) {             case 1:                         cout<<"Masukan Data : ";                         cin>>data;                         Enqueue(data);                         break;                                    case 2:                         cout<<"Elemen yang keluar : "<< Dequeue();                         break;                             case 3:                         show();                                           break;             case 4:                         clear();                         break;             case 5:                         clrscr();                         break; } getch(); } while(pil!=5); }

Source : Data Structures Using C++ by DS Malik

Read More

Array

Array adalah sekumpulan variable yang bertipe data dan bernama sama, namun satu-satu nya yang membedakannya adalah indeks nya. Jika diibaratkan array itu adalah loker tempat penyimpanan maka nomor loker tersebut sama dengan nomor indeks dari array, dan no indeks array selalu di awali dari ‘0’.

 Array ada yang berdimensi satu yang hanya memiliki 1 nomor indeks.

Contoh array Dimensi 1

1         9  13

#include <iostream> #include <stdio> int main() {         int array[2];         array[0] = 1;         array[1] = 9;         array[2] = 13;         cout<< array[0];         cout<< array[1];         cout<< array[2];         getch(); }

Sama dengan array 1 dimensi, array 2 dimensi juga memiliki nomor indeks, namun yang berbeda adalah jumlah nya. Array 2 dimensi memiliki 2 nomor indeks dan juga memiliki susunan yang berbeda dengan array 1 dimensi. Array 2 dimensi memiliki bentuk yang sama dengan matriks pada matematika

Contoh array dimensi 2

23   7

7   12

#include <conio> #include <stdio> #include <iostream> int main() { int matrix[10][10],i,j,k; int baris;//batas jumlah baris //input session cout<<"------------------------------------------------------"<<endl; cout<<"Masukkan jumlah baris (Max 10 baris) : ";cin>>baris; cout<<"------------------------------------------------------"<<endl; for(i=0;i<baris;i++)                 {                 cout<<"Masukkan Data ["<<i<<"]"<<"["<<j<<"] = ";cin>>matrix[i][j];                          } cout<<"------------------------------------------------------"<<endl; //printing session cout<<"Matrix anda inputkan"<<endl; cout<<"------------------------------------------------------"<<endl; for(i=0;i<baris;i++)                 {                 for(j=0;j<kolom;j++)                 } //cout<<"Hello World"; getch(); }

Read More