Rangkuman Materi Searching

Searching

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 : Pencarian sekuensial (sequential search) dan Pencarian biner (Binary search).

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.

a. Sekuensial versi berdampingan dengan sintak C:

Contoh listing fungsi dalam bahasa C++ :

Int SequensialSearch(List_type list, Key_type target)

{ int location; // penempatan data

for (location=0;location

if (EQ(list.entry[location].key,target))

return location;

return –1

b. Sekuensial versi berangkai dengan sintak C:

Node_type* SequentialSearch (List_type list, Key_type target)

{ Node_type* location;

for (location=list.head;location!=NULL;locatioan->next)

if(EQ(location->info.key,target))

return location;

return NULL

}

Pengimplementasian sintak sekuensial search pada bahasa C :

#include

#include

void main()

{

clrscr();

int data[8] = {3,9,7,-3,11,5,2,18};

int cari,index;

int ketemu=0;

cout<<"Inputkan data yang ingin di cari = ";

cin>>cari;

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

{

if(data[i] == cari)

{

ketemu=1;

index=1;

break;

}

}

if(ketemu == 1)

{

cout<<"Data tersedia!"<

cout<<"Data Terletak di index ke - "<

}

else cout<<"Data tidak tersedia!"<

getch();

}

 Binary Search

Salah satu syarat pencarian biner (binary search) dapat dilakukan adalah data sudah dalam keadaan terurut. Dengan kata lain, apabila data belum dalam keadaan terurut , pencarian biner tidak dapat dilakukan . Dalam kehidupan sehari-hari, sebenarnya kita juga serig menggunakan pencarian biner. Misalnya saat kita ingin mencari suatu kata dalam kamus.

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.

Contoh sintak Binary search pada bahasa C:

#include

#include

int data[10] = {1,4,6,8,18,23,35,49,60,75};

int binary_search(int cari)

{

int l,r,m;

int n = 10;

l = 0;

r = n-1;

int ketemu = 0;

while(l<=r && ketemu==0)

{

m = (l+r)/2;

if ( data[m] == cari )

ketemu = 1;

else

if (cari <>

r = m-1;

else l = m+1;

}

if(ketemu == 1) return 1; else return 0;

}

void main()

{

clrscr();

int cari,hasil;

cout<<"Masukan data yang ingin dicari = ";

cin>>cari;

hasil = binary_search(cari);

if(hasil == 1)

{

cout<<"Data tersedia!"<

}

else

if(hasil == 0)

cout<<"Data tidak tersedia!"<

getch();

}

· Pencarian Sekuensial :

a. Kelebihannya :

- Relatif lebih cepat dan efisien untuk data yang terbatas

- Algoritma sederhana

b. Kekuranganya :

- Kurang cepat untuk data dalam jumlah besar

- Beban komputasi cenderung lebih besar

- Pencarian Biner :

a. Kelebihannya :

- Untuk data dalam jumlah besar, waktu searching lebih cepat

- Beban komputasi lebih kecil

b. Kekuranganya :

- Data harus sudah di-sorting lebih dulu ( dalam keadaan terurut )

Read More

Rangkuman Materi Sorting

Sorting

Sorting atau pengurutan adalah proses menyusun elemen – elemen dari masukan awal acak menjadi keluaran akhir tertata dengan urutan tertentu. Proses tersebut diimplementasikan dalam bermacam aplikasi. Contoh penerapannya antara lain berupa rincian transaksi sesuai urutan tanggal dan jam pada perbankan, daftar hadir yang diurutkan berdasarkan nomor induk dan daftar pustaka yang diurutkan sesuai abjad pengarang ataupun katalog buku di perpustakaan. Fungsi-fungsi statistik seperti median dan pembuatan kuartil data (quarter), desil dan percentil (percentile) mensyaratkan data untuk diurutkan terlebih dahulu. Beberapa macam algoritma sorting telah dibuat karena proses tersebut sangat mendasar dan sering digunakan. Oleh karena itu, pemahaman atas algoritma – algoritma yang ada sangatlah berguna. Selain menjadi suatu 2 aplikasi yang berdiri sendiri, pengurutan juga biasanya menjadi suatu bagian dari algoritma  yang lebih besar.

Insertion Sort

       Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Insertion Sort disebut-sebut sebagai metode pertengahan. Artinya, metode ini memiliki kecepatan ratarata antara metode primitif (bubble dan selection) dan modern (merge dan quick) . Metode ini, didasarkan pada sebuah kunci yang diambil pada elemen ke-2 pada sebuah larik, lalu menyisipkan elemen tersebut jika kondisi percabangan terpenuhi. Metode penyisipan (insertion) bertujuan untuk menjadikan bagian sisi kiri larik terurutkan sampai dengan seluruh larik berhasil diurutkan. 

Pseudocode untuk algoritma insertion sort adalah sebagai berikut: 

                   insertionsort(data[],n) 

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

                  pindahkan seluruh elemen data[j] yang lebih besar daripada data[i] sebanyak satu posisi; 

                  geser data[ i ] pada posisi yang tepat;

Sintaks program fungsi Insertion Sort
void insertion_sort()
{
int temp;
for(int 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;
}
}

Selection 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. Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]). Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses. 

Sintaks program fungsi Selection Sort
void selection_sort()
{
for(int i=0;i<n-1;i++)
   {
pos = i;
for(int j=i+1;j<n;j++)
      {
if(data[j] < data[pos])
pos = j; //ascending
}
   if(pos != i) tukar(pos,i);
}
}


Daftar Pustaka
ANALISIS ALGORITMA INSERTION SORT DAN IMPLEMENTASINYA DALAM BAHASA PEMROGRAMAN C++
BAB 2 SORTING (PENGURUTAN)

Read More

Rangkuman Materi Queue

Queue

Secara  harfiah  queue  dapat  diartikan  sebagai  antrian.  Queue  merupakan  kumpulan  data  dengan  penambahan  data  hanya melalui  satu  sisi,  yaitu  belakang (tail)  dan  penghapusandata hanya melalui sisi depan (head). Berbeda dengan stack yang bersifat LIFO maka queue  bersifat  FIFO(First  In  First  Out),  yaitu  data  yang  pertama  masuk  akan  keluar  terlebih  dahulu  dan  data  yang  terakhir masuk  akan  keluar  terakhir.  Berikut ini  adalah  gambaran  struktur data queue.

Elemen  yang  pertama  kali  masuk  ke  dalam  queue  disebut  elemen  depan  (front/head  of  queue),  sedangkan  elemen  yang  terakhir  kali  masuk  ke  queue  disebut  elemen  belakang  (rear/tail of queue). Perbedaan antara stack dan queue terdapat pada aturan penambahan  dan  penghapusan  elemen.  Pada  stack,  operasi  penambahan  dan  penghapusan  elemen  dilakukan di satu ujung. Elemen yang  terakhir kali dimasukkan akan berada paling dekat  dengan  ujung  atau  dianggap  paling  atas  sehingga  pada  operasi  penghapusan,  elemen  teratas tersebut akan dihapus paling awal, sifat demikian dikenal dengan LIFO. Pada queue,  operasi tersebut dilakukan di tempat yang berbeda. Penambahan elemen selalu dilakukan  melalui salah satu ujung, menempati posisi di belakang elemen‐elemen yang sudah masuk  sebelumnya  atau  menjadi  elemen  paling  belakang.  Sedangkan  penghapusan  elemen  dilakukan  di  ujung  yang  berbeda,  yaitu  pada  posisi elemen  yang  masuk  paling awal atau  elemen terdepan. Sifat yang demikian dikenal dengan FIFO. 

Operasi‐operasi standar pada queue adalah: 

1. membuat queue atau inisialisasi. 

2. mengecek apakah queue penuh. 

3. mengecek apakah queue kosong.

4. memasukkan elemen ke dalam queue atau InQueue (Insert Queue). 

5. Menghapus elemen queue atau DeQueue (Delete Queue). 

Disebut juga queue dengan model fisik, yaitu bagian depan queue selalu menempati posisi  pertama  array.  Queue  dengan  linear  array  secara  umum  dapat  dideklarasikan  sebagai  berikut:

            Const   

            MaxQueue = {jumlah};

Type   

TypeQueue = byte; 

Var   

 Queue : Array[1..MaxQueue] of TypeQueuel   

 Head, Tail   : Byte; 

1.      Create 

berguna untuk menciptakan queue yang baru dan kosong yaitu  dengan cara memberikan nilai awal (head) dan nilai akhir (tail) dengan nol (0). Nol  menunjukan bahwa queue masih kosong. 

Procedure Create;   

Begin     

                 Head := 0; Tail := 0;   

End; 

2.      Empty 

Function empty berguna untuk mengecek apakah queue masih kosong atau sudah  berisi data. Hal ini dilakukan dengan mengecek apakah tail bernilai nol atau tidak,  jika ya maka kosong. 

Function Empty : Boolean;   

Begin     

If Tail = 0 then     

                             Empty := true     

                 Else       

Empty := False;   

End;

3.      Full 

Function Full : Boolean; 

Begin   

If Tail = MaxQueue then

Full := true

Else

Full := False

End; 

4.      EnQueue 

Procedure EnQueue berguna untuk memasukkan 1 elemen ke dalam queue. 

Procedure Enqueue(Elemen : Byte);   

Begin     

If Empty then     

Begin       

Head := 1;       

Tail := 1;       

Queue[head] := Elemen;     

 End     

Else 

              If Not Full then 

Begin     

Inc(Tail);       

            Queue[tail] := Elemen;   

End;   

End; 

5.      DeQueue 

Procedure  DeQueue  berguna  untuk  mengambil  1  elemen  dari  Queue,  operasi  ini  sering  disebut  juga  SERVE.  Hal  ini  dilakukan  dengan  cara  memindahkan  semua  elemen satu langkah ke posisi di depannya, sehingga otomatis elemen  yang paling  depan akan tertimpa dengan elemen yang terletak dibelakangnya. 

Procedure DeQueue;    Var I : Byte;   

     Begin   

                 If Not Empty then 

                 Begin 

                             For I := Head to Tail‐1 do     

                             Queue[I] := Queue[I+1];       

 Dec(Tail);     

                 End;   

  End;

6.      Clear 

Procedure  clear  berguna  untuk  menghapus  semua  elemen  dalam  queue  dengan  jalan  mengeluarkan  semua  elemen  tersebut  satu  per  satu  sampai  kosong  dengan  memanfaatkan procedure DeQueue. 

Procedure Clear; 

Begin     

While 

Not Empty then     

DeQueue; 

End; 

Coding 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<<"Gak Bisa MAsuk!!!";

   }

}

void Dequeue()

{

            int i;

   int e = antrian.data[antrian.head];

   if(antrian.tail==-1)

   {

            cout<<"Gak 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 gak 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. Dequeue"<<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);

}

Hasil Output Queue

Daftar Pustaka
Algoritma dan  Struktur Data II

Read More