Jumat, 05 Juni 2015

struktur data : searching

Struktur Data : Searching

Pada suatu data seringkali dibutuhkan pembacaan kembali informasi (retrieval information) dengan cara searching. Searching adalah pencarian data dengan cara menelusuri data-data tersebut. Tempat pencarian data dapat berupa array dalam memori(pencarian internal), bisa juga pada file pada external storage(pencarian external).

Ada dua macam teknik pencarian yaitu pencarian sekuensial dan pencarian biner. Perbedaan dari dua teknik ini terletak pada keadaan data. Pencarian sekuensial digunakan apabila data dalam keadaan acak atau tidak terurut (contoh: sequential search). Sebaliknya, pencarian biner digunakan pada data yang sudah dalam keadaan urut (contoh: Binary serach dan interpolation search). Pada Kesempatan ini kita hanya akan membahas tentang pencarian internal menggunakan Array dinamis (pointer).
Berikut adalah metode-metode yang digunakan dalam Searching

1. Sequential Search (Pencarian berurutan)
Adalah 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. 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.

Contoh Program :
#include <iostream>
using namespace std;
main()
{
            int data[8] = {8,10,6,-2,11,7,1,100};
            int cari;
            int tanda=0;
            cout<<"masukkan data yang ingin dicari = "; cin>>cari;
            for(int i=0;i<8;i++)
    {
            if(data[i] == cari) tanda=1;
    }
            if(tanda==1) cout<<"Data ada!\n";
            else cout<<"Data tidak ada!\n";
};
Hasilnya


2. Binary Search
Salah satu syarat agar binary search dapat dilakukan adalah data sudah dalam keadaan urut. Dengan kata lain, apabila data belum dalam keadaan urut, binary search tidak dapat dilakukan.
Prinsip dari binary search dapat dijelaskan sebagai berikut :
a.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.
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. Jika data sama, berarti ketemu.

Contoh Program:
#include<iostream>


using namespace std;
int main () {
 int n, angka[12], kiri, kanan, 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;

 kiri=0;
 kanan=n-1;

 while(kiri<=kanan)
 {
  tengah=(kiri + kanan)/2;
  if(key == angka[tengah])
  {
   ketemu=true;
   break;
  }
  else if (key < angka [tengah])
  {
   kanan = tengah -1;
  }
  else
  {
   kiri = tengah +1;
  }
 }
 if (ketemu == true)
  cout<<"Angka ditemukan!";
 else
  cout<<"Angka tidak ditemukan";
  return 0;
 };

hasilnya :

referensi :
http://blognapibelog.blogspot.com/2010/08/struktur-data-searching.html ,
http://hellomonname.blogspot.com/2014/03/contoh-program-binary-search-dalam-c.html


Diposting oleh di Tidak ada komentar:

SELECTION SORT

Selection Sort (Metode Seleksi) 
  • One of the simplest sorting algorithms
  • Merupakan kombinasi antara sorting dan searching
  • Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil (Ascending) atau terbesar (Descending) 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])/ data pertama, pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1])/ data kedua atau selanjutnya.
Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses. 

 Ascending

Cek seluruh elemen array, temukan nilai terkecil (1) dan tukarkan posisinya dengan posisi nilai yang tersimpan pada posisi pertama dari array (3)


Temukan nilai terkecil kedua (2), dan tukarkan posisinya dengan nilai yang berada pada posisi kedua (10).

Dua elemen biru pertama tidak akan berubah lagi sebab mereka sudah merupakan nilai terkecil pertama dan kedua dalam array tsb.

Sekarang, ulangi dengan cara/proses “pilih dan tukar” 



  • Pengurutan Selesai.

Contoh Program Selection Sort menggunakan bahasa pemrograman C++
berikut kode programnya :
#include<iostream>
using namespace std;
int main()
{   int a,k,c,d,g;
    k=4;
    int b[4];
    cout<<"SELECTION SORT BY ZEFTAADETYA.BLOGSPOT.COM"<<endl;
    cout<<"mengurutkan nilai dari besar ke kecil"<<endl<<endl;
    for(a=0;a<k;a++)
    {
        cout<<"Masukkan nilai "<<a+1<<" : ";cin>>b[a];
    }
    for(a=0;a<k-1;a++)
    {
    c=a;
        for(d=a+1;d<k;d++)
        {
            if(b[c]<b[d])
            {
                c=d;
            }
        }
        g=b[c];
        b[c]=b[a];
        b[a]=g;
    }
    cout<<"\n setelah diurutkan akan menjadi : \n";
    for(a=0;a<k;a++)
    {
        cout<<b[a]<<" \n";
    }
};









Program Setelah dieksekusi :

referensi :
http://sisinform-aaf1231072.blogspot.com/2013/02/selection-sort.html





Diposting oleh di Tidak ada komentar:

INSERTION SORT


INSERTION SORT
Insertion Sort (Metode Penyisipan)


  • Insertion Sort merupakan algoritma yang efisien untuk mengurutkan angka yang mempunyai jumlah elemen sedikit. Dimana:- Input : deretan angka sejumlah n buah
    - Output : permutasi (pengurutan) sejumlah n angka dari input yang sudah terurut secara ascending maupun descending 
  • Metode penyisipan (Insertion sort) bertujuan untuk menjadikan bagian sisi kiri array terurutkan sampai dengan seluruh array berhasil diurutkan.
  • Metode ini mengurutkan bilangan-bilangan yang telah dibaca; dan berikutnya secara
    berulang akan menyisipkan bilangan-bilangan dalam array yang belum terbaca ke sisi kiri array yang telah terurut. 
Insertion Sort bekerja seperti banyak orang yang sedang mengurutkan kartu di tangan. Dimulai dengan tangan kiri yang kosong dan kartunya tertumpuk di meja. Selanjutnya kita ambil satu persatu kartu di meja dan diletakkan di tangan kiri dengan posisi yang benar (terurut). Untuk menemukan posisi yang banar, maka kita harus membandingkan satu persatu kartu yang ada (di tangan kiri) secara berurutan.
Contoh Insertion Sort :


  • Bagian biru/abu-abu (dua bilangan pertama) sekarang dalam keadaan terurut secara relatif.
 

Berikutnya, kita perlu menyisipkan bilangan ketiga (4) ke dalam bagian biru/abu-abu sehingga
setelah penyisipan tersebut, bagian biru/abu-abu tetap dalam keadaan terurut secara relatif;
CARANYA :
pertama : Ambil bilangan ketiga (4).
  • Kedua : Geser bilangan kedua (10) shg ada ruang untuk disisipi.




    • Ketiga : Sisipkan bilangan 4 ke posisi yang tepat

    • Sekarang, tiga bilangan pertama sudah terurut secara relatif dan kita sisipkan bilangan keempat kepada tiga bilangan pertama tsb.  Setelah penyisipan, empat bilangan pertama haruslah dalam keadaan terurut secara relatif.

    •  Ulangi proses tsb sampai bilangan terakhir disisipkan


    •  Proses Sorting Selesai

     Contoh koding Insertion sort

    #include <iostream>
    #include <conio.h>
    using namespace std ;
    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===PROGRAM INSERTION 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 :
    http://sisinform-aaf1231072.blogspot.com/2013/02/insertion-sort.html










    Diposting oleh di Tidak ada komentar:

    Perbedaan stack dan queue

    PERBEDAAN STACK DENGAN QUEUE

    A.STACK
    -       Pada stack menggunakan prinsip LIFO (Last In First Out). yang masuk paling belakang akan memiliki prioritas untuk keluar paling depan.
    -       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 operasIpenghapusan, elemen teratas tersebut akan dihapus paling awal
    -       Stack hanya mempunyai satu pointer yang selalu menunjuk ke arah top.

    B.QUEUE
    -       Queue (antrian) beroperasi dalam cara FIFO (First-In-First-Out). elemen yang pertama masuk merupakan elemen yang pertama ke luar.
    -       Pada queue,operasi tersebut dilakukan di tempat yang berbeda.Penambahan elemen selalu dilakukan melalui salah satu ujung, menempati posisi dibelakang 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.
    -       dalam Queue mempunyai dua pointer yang menunjuk ke arah head dan tail.
    2.PERSAMAAN STACK DENGAN QUEUE

    -       Sama-sama menunggu panggilan data
    -       Sama-sama  diproses pada saat ada data yang masuk tetapi dilihat menurut waktu masuk data tersebut
    Diposting oleh di 1 komentar:

    Materi QUEUE c++

    QUEUE (ANTRIAN)
     Definisi Queue
    Queue berarti antrian, queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering kita temui dalam kehidupan sehari-hari,
     Kelemahan
    1) Pemborosan tempat (memori) ketika menggunakan jumlah data yang lebih sedikit dari alokasi memori
    2) Tidak dapat menambahkan data melebihi maksimal ukuran array yang telah dideklarasikan
    3) Waktu yang tidak efisiensi


    Contoh Queue
    misalnya saat Anda mengantri di loket untuk membeli tiket. Istilah yang cukup sering dipakai seseorang masuk dalam sebuah antrian adalah enqueue. Dalam suatu antrian, yang dating terlebih dahulu akan dilayani lebih dahulu. Istilah yang sering dipakai bila seseorang keluar dari antrian adalah dequeue. Walaupun berbeda implementasi, struktur data queue setidaknya harus memiliki operasi-operasi sebagai berikut :
    1) PUSH X (yaitu menambahkan data X ke dalam antrian)
    2) POP (yaitu mengambil elemen paling depan dari antrian)

    3) EMTPY (yaitu mengosongkan antrian)
    Contoh Program Queue

    #include "stdio.h"
    #include "conio.h"
    int main()
    {
      int cek=0, data[20], x, hapus;
      char pil;
      do {

          printf("1. Tambah Antrian\n");
          printf("2. Hapus Antrian\n");
          printf("3. Lihat Antrian\n");
          printf("4. Keluar\n");
          printf("Silahkan masukkan pilihan anda...  ");
          pil=getche();


      if(pil!='1' && pil !='2' && pil !='3' && pil!='4' )
          printf("\n\nAnda salah mengetikkan inputan...\n");
          else
          {
        if(pil=='1')   //PUSH
        {
          if(cek==20)
            printf("\nAntrian Penuh\n\n");
            else
            {
              printf("\nMasukkan nilai-->");scanf("%i",&x);
              data[cek]=x;
              cek++;
            }}
            else
            {
              if(pil=='2')     //POP
              {
            if(cek==0)
              printf("\nAntrian kosong\n\n");
              else
              {
                hapus=data[0];
                for(int v=0;v<cek;v++)
                data[v]=data[v+1];
                data[cek-1]=NULL;
                cek--;
                printf("\nData dgn nilai=%i terhapus.",hapus);
              }
              getch();
              }
            else
            {
              if(pil=='3')   //CEK DATA
              {
                if(cek==0)
                printf("\nAntrian Kosong.\n\n");
                else
                {
                  printf("\n");
                  for(int z=0;z<cek;z++)
                  {
                printf(" | ");
                printf("%i",data[z]);
                printf(" | ");
                  }
                }
                getch();
                }
              }
            }
              }
        }while(pil!='4');
    };

    hasilnya :

    Diposting oleh di Tidak ada komentar:
    Langganan: Postingan (Atom)