MATERI SEARCHING DAN CONTOH PROGRAMNYA

   1.    SEARCHING

Pencarian data sering disebut juga dengan istilah table look-up atau storage and retrieval information, adalah suatu proses untuk mengumpulkan sejumlah informasi di dalam pengingat computer dan kemudian mencari kembali informasi yang diperlukan. Searching merupakan proses yang sangat penting dalam pengolahan data. Proses pencarian adalah menemukan nilai (data) tertentu didalam sekumpulan data yang bertipe sama.Sebuah algoritma pencarian dijelaskan secara luas adalah sebuah algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi. Algoritma pencarian (searching algorithm) adalah algoritma yang menerima sebuah Kata kunci dan dengan  langkah-langkah tertentu akan mencari rekaman dengan kata kunci tersebut.  Setelah proses pencarian dilaksanakan, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang dicari ditemukan atau tidak ditemukan. Metode pencarian data dapat dilakukan dengan dua cara yaitu pencarian internal

(internal searching) dan pencarian eksternal (external searching). Pada pencarian internal, semua rekaman yang diketahui berada dalam pengingat komputer sedangakan pada pencarian eksternal, tidak semua rekaman yang diketahui berada dalam pengingat komputer, tetapi ada sejumlah rekaman yang tersimpan dalam penyimpan luar misalnya pita atau cakram magnetis.

Macam-macam Algoritma (searching)

a.    Sequential Searching

Pencarian berurutan sering disebut pencarian linear merupakan metode pencarian yang paling sederhana. Pencarian berurutan menggunakan prinsip sebagai berikut : data yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data tersebut ditemukan atau tidak ditemukan. Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah data. Pada setiap pengulangan, dibandingkan data ke-i dengan yang dicari. Apabila sama, berarti data telah ditemukan. Sebaliknya apabila sampai akhir pengulangan tidak ada data yang sama, berarti data tidak ada. Pada kasus yang paling buruk, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula.

Algoritma pencarian berurutan dapat dituliskan sebagai berikut :

1.     i ← 0

2.     ketemu ← false

3.     Selama (tidak ketemu) dan (i <= N) kerjakan baris 4

4.     Jika (Data[i] = x) maka ketemu ← true, jika tidak i ← i + 1

5.     Jika (ketemu) maka i adalah indeks dari data yang dicari, jika tidak data tidak ditemukan.

CONTOH PROGRAM

#include <iostream.h>

#include <conio.h>

void main()

{

    int i;

    int cari,ketemu;

  int A[100]  ;

   cout<<"SEQUENSIAL SEARCHING\n";

   cout<<"Masukkan 5 Buah Data : \n\n";

   cout<<"----------------------------------------\n";

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

   {

   cout<<"Masukkan data ke-"<<i<<" = "; cin>>A[i];

   }

   cout<<endl;

    cout<<"Input bilangan yang dicari : ";

    cin>>cari;

    ketemu=0;

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

    {

        if (A[i]==cari)

        {

            ketemu=1;

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

        }

    }

    if (ketemu==0){

       cout<<"Data tidak ditemukan";

    }

 getch();

}

a.    Binary Search

Salah satu syarat agar pencarian biner dapat dilakukan adalah data sudah dalam keadaan urut. Dengan kata lain, apabila data belum dalam keadaan urut, pencarian biner tidak dapat dilakukan. Dalam kehidupan sehari-hari, sebenarnya kita juga sering menggunakan pencarian biner. Misalnya saat ingin mencari suatu kata dalam kamus. Prinsip dari pencarian biner dapat dijelaskan sebagai berikut : 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, porses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah + 1. Demikian seterusnya sampai data tengah

sama dengan yang dicari.

Algoritma pencarian biner dapat dituliskan sebagai berikut :

1.     L ← 0

2.     R ← N - 1

3.     ketemu ← false

4.     Selama (L <= R) dan (tidak ketemu) kerjakan baris 5 sampai dengan 8

5.     m ← (L + R) / 2

6.    Jika (Data[m] = x) maka ketemu ← true

7.     Jika (x < Data[m]) maka R ← m – 1

8.    Jika (x > Data[m]) maka L ← m + 1

9.    Jika (ketemu) maka m adalah indeks dari data yang dicari, jika tidak data tidak ditemukan.

CONTOH PROGRAM

#include <iostream.h>

#include <conio.h>

#include <string.h>

main ()

{

    int jd,no,kiri,kanan,center;

    char data[20][50],cari[20];

   cout<<"\n\t\t *************************************** \n";

   cout<<"\t\t | \t\t\t\t       | \n";

   cout<<"\t\t | \t     Proses Pencarian \t       | \n";

   cout<<"\t\t | Menggunakan Algoritma Binary Search | \n";

   cout<<"\t\t | \t\t\t\t       | \n";

   cout<<"\t\t *************************************** \n\n\n";

    cout<<" Input Jumlah Data  : ";

    cin>>jd;

   cout<<endl;

    for (no=0;no<jd;no++)

    {

        cout<<" Input Data Ke-"<<(no+1)<<"    : ";

       cin>>data[no];

    }

   cout<<endl;

    cout<<" Input Nilai Dicari : ";

    cin>>cari;

    kiri=0;

    kanan=jd-1;

   center=(kanan-kiri)/2;

    while ((strcmp(data[center],cari)!=0) && (kiri>=0)&& (kanan<jd) && (kanan>=kiri))

    {

        if (strcmp (cari,data[center])>0)

       {

           kiri=center+1;

       }

       else if (strcmp (cari,data[center])<0)

       {

           kanan=center-1;

       }

       center=kiri+(kanan-kiri)/2;

    }

   cout<<endl;

    if (strcmp(data[center],cari)==0)

    {

        cout<<" Keterangan         : Data Ditemukan";

    }

    else

    {

        cout<<" Keterangan         : Data Tidak Ditemukan";

   }

    getch();

}

MATERI SORTING DAN CONTOH PROGRAMNYA

1.    SORTING

Sorting merupakan suatu proses untuk menyusun kembali himpunan obyek menggunakan aturan tertentu. Sorting disebut juga sebagai suatu algoritma untuk meletakkan kumpulan elemen data kedalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen. Pada dasarnya ada dua macam urutan yang biasa digunakan dalam suatu proses sorting: 

1. Urutan Naik
Mengurutkan dari data yang mempunyai nilai paling kecil sampai besar.

2. Urutan Turun

Mengurutkan dari data yang mempunyai nilai paling besar sampai paling kecil.

Ada banyak alasan dan keuntungan dengan mengurutkan data. Data yang terurut mudah untuk dicari, mudah untuk diperiksa, dan mudah untuk dibetulkan jika terdapat kesalahan. Data yang terurut dengan baik juga mudah untuk dihapus jika sewaktu-waktu data tersebut tidak diperlukan lagi. Selain itu, dengan mengurutkan data maka kita semakin mudah untuk menyisipkan data atapun melakukan penggabungan data.

Insertion Sort (Metode Penyisipan) 

Straight Insertion Sort (Metode Penyisipan langsung)  Proses pengurutan dengan metode penyisipan langsung dapat dijelaskan sebagai berikut Data dicek satu per satu mulai dari yang kedua sampai dengan yang terakhir. Apabila ditemukan data yang lebih kecil daripada data sebelumnya, maka data tersebut disisipkan pada posisi yang sesuai. Akan lebih mudah apabila membayangkan pengurutan kartu. Pertama-tama anda meletakkan kartu-kartu tersebut di atas meja, kemudian melihatnya dari kiri ke kanan. Apabila kartu di sebelah kanan lebih kecil daripada kartu di sebelah kiri, maka ambil kartu tersebut dan sisipkan di tempat yang sesuai.

CONTOH PROGRAM

#include<iostream.h>
#include<conio.h>
main()
{
 int x,a[100],i,t,j,k;

 cout<<"Insertion Sort - Desc\n";
   cout<<"Masukkan banyak bilangan = ";cin>>x;
   for(i=1;i<=x;i++)
   {
    cout<<"\n Bilangan ke-"<<i<<" : ";cin>>a[i];
   }
   cout<<"\n\n data Sebelum diurutkan :";
   for(i=1;i<=x;i++)
   {
    cout<<"  "<<a[i];
   }
   cout<<endl;
   for(i=1;i<=x;i++)
   {
    for(j=1;j<=i;j++)
    {
       if(a[i]>a[j])
         {
          t=a[i];
            a[i]=a[j];
            a[j]=t;
         }
      }
      cout<<"\n # "<<i<<" : ";
      for(k=1;k<=i;k++)
      {
       cout<<"  "<<a[k];
      }
   }
   cout<<"\n\n data Setelah diurutkan secara descending : ";
   for(i=1;i<=x;i++)
   {
    cout<<"  "<<a[i];
   }
 getch();

}

Selection Sort (Metode Seleksi)

     Metode seleksi melakukan pengurutan dengan cara mencari data yang terkecil kemudian menukarkannya dengan data yang digunakan sebagai acuan atau sering dinamakan pivot. Proses pengurutan dengan metode seleksi dapat dijelaskan sebagai berikut :

Langkah pertama dicari data terkecil dari data pertama sampai data terakhir. Kemudian data terkecil ditukar dengan data pertama. Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding data yang lain. Langkah kedua, data terkecil kita cari mulai dari data kedua sampai terakhir. Data terkecil yang kita peroleh ditukar dengan data kedua dan demikian seterusnya sampai semua elemen dalam keadaan terurutkan. 

CONTOH PROGRAM

#include <iostream.h>

#include <conio.h>

int main(){

int a[10];

int cur,z,temp,cur2,temp2;

cout<<"Banyak Data: ";

cin>>z;

cout<<endl;

for(int i=0;i<z;i++){

cout<<"Data ["<<i+1<<"]: ";

cin>>a[i];

}

cout<<"\nData Awal  :";

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

cout<<a[i]<<" ";

cout<<endl;

for(int i=0;i<z;i++){

cur=i;

cur2=z;

for(int k=i+1;k<z;k++){

if(a[cur]>a[k]){

cur=k;

}}

for(int t=z;t<z;t--){

if(a[cur2]<a[t]){

cur2=t;

}

temp2=a[t];

a[t]=a[cur2];

a[cur2]=temp2;

}

temp=a[i];

a[i]=a[cur];

a[cur]=temp;

}

cout<<"\nData Akhir :";

for(int i=0;i<z;i++){

cout<<" "<<a[i];

}

cout<<endl;

getch ();

return 0;

}

MATERI STACK DAN CONTOH PROGRAMNYA

STACK

STACK (tumpukan) dapat di katakan sebagai list yang operasi penghapusan dan penyisipan elemennya dilakukan di satu ujung. atau bisa juga di artikan sebagai suatu kumpulan data yang seolah-olah ada data yang di letakkan di atas data yang lain. Satu hal yang perlu kita ingat adalah bahwa kita bisa menambah (menyisipkan) data, dan mengambil (menghapus) data lewat ujung yang sama, yang disebut sebagai ujung atas tumpukan (top of stack). Dalam kehidupan sehari-hari terdapat banyak kejadian yang mempunyai sifat seperti stack, untuk lebih memahami pengertian stack kita ambil contoh sebagai berikut:

Perhatikan sebuah tumpukan piring di sebuah warung makan. Piring-piring tersebut tersusun rapat dari atas ke bawah (membentuk barisan beruruntan). Setiap kali ada pembeli datang, maka iring yang paling atas akan di ambil (menghapus elemen) yang berarti mengurangi jumlah piring dalam tumpukan. Bila tumpukan itu sudah habis atau tinggal sedikit, maka pegawai warung akan menambahkan piring lain yang masih bersih (menambah elemen). Piring yang terakhir kali dimasukan pasti akan terletak ditumpukan paling atas dan piring yang terletak paling atas dalam tumpukan itu pasti merupakan piring yang terakhir kali dimasukan.

Kesimpulannya adalah penambahan dan penghapusan elemen hanya dapat di lakukan di ujung atas tumpukan piring. Proses seperti ini biasa disebut Last In Firts Out (LIFO).

Operasi Pada Tumpukan (stack)

Ada dua operasi dasar yang bisa  digunakan pada sebuah tumpukan, yaitu operasi menyisipkan data atau memPush data dan operasi menghapus data atau memPop data.

·         Operasi Push

Dengan penyajian tumpukan seperti diatas, maka operasi Push dapat diimplementasikan, yaitu:

Procedure PUSH (var T : Tumpukan; X : integer);

Begin T.Atas := T.Atas + 1 T.Isi [T.Atas] := X

       End;

Prosedur diatas akan menyiapkan tempat untuk X yang akan diPush kedalam tumpukan, yaitu dengan menambah nilai medanT. Atas dengan 1 dan kemudian menyisipkan X kedalam larik T.Isi. tetapi jika suatu saat nilai T.Atas sama dengan MaxElemen dan kita akan memPush lagi, maka akan terjadi overflow pada larik T.Isiberhubung deklarasi banyaknya elemen larik tidak mencukupi .

Pada proseur diatas perlu ditambahkan dengan testing untuk memastikan bahwa sebelum suatu data diPush nilai T.Atas belum mencapai MaxElemen. Prosedure diatas perlu diubah menjadi:

Procedure PUSH (var T : Tumpukan; X : integer); Begin if T.Atas = MaxElemen then writeln (‘TUMPUKAN SUDAH PENUH’)

           else

               begin 

                    T.Atas := T.Atas + 1; T.Isi [T.Atas] := X

          End

       end;

Dengan ditambahnya testing untuk mencetak nilai T.Atas, maka prosedur di atas menjadi lebih sempurna.

            Kita juga bisa mengubah pesan yang ditampilkan mengunakan statemen writelndengan kata lain yang bertipe boolean, sehingga pesan salahnya kita letakkan pada program utama .

Pemanggilan prosedur diatas dari program utama atau dari bagian lain dilaksanakan dengan:

PUSH (T, Penuh, X);

Dengan T adalah perubah bertipe tumpukan, penuh bertipe boolean dengan X bertipe integer. Berdasarkan nilai perubah penuh bisa ditentukan langkah selanjutnya yang perlu diambil.

Operasi Pop

        Operasi popAdalah operasi untuk menghapus elemen yang terletak pada posisi  paling atas dari sebuah tumpukan.  Sama halnya dengan operasi Push, maka dengan deklarasi tumpukan di atas prosedur untuk operasi Pop bisa diimplementasikan, yaitu:

Prosedure Pop (var T : Tumpukan ); Begin T.Atas := T.Atas – 1 end;

       Timbul pertanyaan, seandainya tumpukan sudah kosong lalu apa yang akan diPop? Jawabannya tentu saja adalah tidak mungkin memPop suatu tumpukan jika tumpukan tersebut sudah kosong. prosedur diatas perlu ditambah testing untuk mencetak kosong tidaknya sebuah tunpukan sebelum proses memPop suatu elemen tumpukan dilaksanakan.

Tumpukan yang kosong ditunjukan dengan nilai T.Atas sama dengan 0. Sehingga kita bisa melengkapi prosedur diatas menjadi:

Prosedur Pop (var T : Tumpukan);

Begin

            if  T.Atas = 0 then writeln (‘TUMPUKAN SUDAH KOSONG’)

           else

            T.Atas : = T.Atas – 1

End;

            Cara lain untuk melihat kosong tidaknya tumpukan adalah dengan membuat suatu fungsi yang menghasilkan suatu data yang bertipe boolean. Cara ini lebih disarankan dari cara di atas, karena dengan mengetahui nilai fungsi tersebut kita segera bisa tahu kosong tidaknya suatu tumpukan. alasan lain adalah supaya sifat modularitas program tetap dijalankan.  Kecuali itu sering akli kita juga perlu mengetahui nilai data yang baru saja diPop.

CONTOH PROGRAM DENGAN STACK

#include<iostream.h>

#include<conio.h>

main()

{

char stack1[9];

int i;

//Inputan Data

cout<<"\nCONTOH PROGRAM PEMBALIKAN DATA DENGAN STACK";

cout<<"\n";

cout<<"================================================";

cout<<"\nData Masukkan : ";

cin>>stack1;

cout<<endl;

//Menampilkan data

cout<<"\nPembalikan Data :";

for(i=9;i>=0;i--)

{

cout<<stack1[i]<<"";

}

cout<<"";

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

cout<<"\n";

cout<<"\nAndreas Teresna";

cout<<endl;

getch();

} 

DAFTAR PUSTAKA

1. SismoroHeri, Iskandar Kusrini. 2004  Struktur data dan Pemograman dengan PASCAL.Yogyakarta: ANDI Yogyakarta.
2. Santosa, Insap. P. Ir. 1992 Struktur data menggunakan TURBO PASCAL 6.0 Yogyakarta : ANDI yogyakarta.