Senin, 25 April 2011

struktur data | bab searching atau pencarian

BINARY SEARCH

Metoda Pencarian Biner ( Binary Search) hanya bisa diterapkan jika data array sudah terurut. pengurutan Array bisa menggunakan jenis sorting descending atau asscending. Kelebihan dari Searching dengan metode Binary Sort adalah Untuk Pencarian data yang jumlahnya banyak, waktu pencarian relatif cepat. selain itu beban komputasi juga lebih kecil karena pencarian dilakukan dari depan, belakang, dan tengah. namun ada pula kekurangannya, yaitu data harus disorting dahulu dan Algoritma lebih rumit, tidak baik untuk data berangkai.

Algoritma dari Binary Sort

Proses yang terjadi pada pencarian dengan metode ini adalah sebagai berikut :
1. Membaca Array data
2. Apabila Array belum terurut maka array diurutkan terlebih dahulu.
3. Menentukan data yang akan dicari
4. Menentukan elemen tengah dari array
5. Jika nilai elemen tengah sama dengan data yang dicari, maka pencarian berhenti.
6. Jika elemen tengah tidak sama dengan data yang dicari maka :
      a. Jika nilai elemen tengah > data yang dicari maka pencarian dilakukan pada setengah array pertama.
      b. Jika nilai elemen tengah lebih kecil dari pada data yang dicari maka pencarian dilakukan pada setengah array berikutnya.










Misalkan saya mempunyai data sebagai berikut : 3,1,4,7,25,12,40,78,90,65. Maka data tersebut akan dicek, ternyata setelah dicek datanya belum terurut, maka dengan menggunakan metoda sorting yang sudah ada, maka kita bisa mengurut data tersebut, menjadi : 1,3,4,7,12,25,40,65,78,90
Setelah data tersebut diurutkan maka fungsi binary sort baru mulai bekerja mencari data. berikut cara dari Binary sort mencari data tersebut. misalnya data yang dicari adalah 65. maka pencariannya dijelaskan pada tabel berikut ini :











KETERANGAN :

Pada data range diberi warna Hijau. Pencarian dimulai dari tengah,Kiri dan kanan. rumus untuk Posisi tengahnya adalah ( Posisi Akhir + Posisi Awal )/2. jadi Nilai tengah pada langkah pertama yaitu adalah 12 (berwarna merah) dan nilai targetnya adalah 65 (kuning). Karena nilai data yang dicari > dari data yang ditengah, maka pencarian menjadi dikanan dari nilai tengah. Setelah itu, Maka nilai 12 menjadi awal pencarian, selanjutnya dicari kembali nilai tengah pada range nilai 12 ke kanan sampai pada array dengan nilai 90. ternyata nilai tengahnya adalah 40. kemudian array dari nilai 40 dibandingkan dengan target, ternyata lebih besar, maka pencarian kembali mengarah ke kanan nilai tengah. Array dengan nilai 40 menjadi titik awal pencarian sekarang. dan sekarang nilai tengah nya adalah 65. maka dibandingkan dengan target ternyata sama, maka data sudah Ditemukan.

contoh source code tentang  program  untuk mensimulasikan searching pada sebuah deretan angka menggunakan algoritma Binary Search


#include<stdio.h>

void main()
{
      int bil[50];
      int i, k, n, x,j,temp;k=0;
      printf("Masukkan banyaknya elemen yang diinginkan : ");
      scanf("%d", &n);
      for(i=1; i<=n; i++)
      {
            printf(" Masukkan bilangan ke %d : ", i);
            scanf("%d", &bil[i]);
      }
      printf("\nMasukkan nilai yang akan dicari : ");
      scanf("%d", &x);
      printf("\n");
      printf("\tPROSES SIMULASI\n\n");
      printf("bilangan sebelum di urutkan:\n");
      for(i=1;i<=n;i++)
            printf("%3d",bil[i]);
            printf("\n\n");
      for(i=0;i<=n;i++)
      {
            temp=bil[i];
            for(j=i-1;bil[j]>temp&&j>=1;j--)
            {
                  bil[j+1]=bil[j];
            }
      bil[j+1]=temp;
      }
printf("bil setelah diurutkan :\n");
for(i=1;i<=n;i++)
printf("%3d",bil[i]);
printf("\n\n");
      while ((k<n) && (bil[k]!= x-1))
      {
            printf("bilangan %d tidak sama\n",bil[k+1]);k++;
      }
      while ((k<n) && (bil[k]!= x))
      {
            k++;
      }
      if(bil[k] == x)
      {
            printf("bilangan %d sama\n",x);
            printf(" \nBilangan ditemukan , ");
      }
      else
      {
            printf(" Bilangan tidak ditemukan");
      }
      printf("\n\n");



semoga bermanfaat



Kamis, 14 April 2011

struktur data tentang sorting atau pengurutan

Metode seleksion sort (selection sort) melakukan pengurutan dengan cara mencari data yang terkecil kemudian menukarkannya dengan data yang digunakan sebagai acuan atau sering dinamakan pivot.
Proses pengurutan dengan metide selection dapat dijelaskan sebagai berikut: mula-mula dilakukan pengulangan dari 1  sampai dengan (N-1). Pada tiap-tiap pengulangan dicari data yang paling kecil diantara data yang ke(i+1) sampai dengan data terakhir (=N). data yang terkecil ini kemudian ditukarkan  dengan pivot, yaitu data ke i. tentu saja , apabila data terkecil tersebut lebih besar daripada data ke-I,proses penukaran tidak perlu dilakukan.

untuk lebih jelasnya perhatikan proses pengurutan dengan metode selection yang disajikan pada table di bawah
Proses pengurutan pada table diatas dijelaskan sebagai berikut :
• Pada saat i=1, data yang terkecil dari antara data ke-2 sampai dengan 9 adalah data ke-5,yaitu 3. Dengan demikian data ke-1,yaitu 12, ditukar dengan data ke-5 yaitu 3.
• Pada saat i=2, data yang terkecil dari antara data ke-3 sampai dengan 9 adalah data ke-3,yaitu 9. Dengan demikian data ke-2,yaitu 35, ditukar dengan data ke-3 yaitu 9.
• Pada saat i=3, data yang terkecil dari antara data ke-4 sampai dengan 9 adalah data ke-4,yaitu 11. Dengan demikian data ke-3,yaitu 35, ditukar dengan data ke-4 yaitu 11.
• Demikian seterusnya

Dari algoritma dan program diatas ,dapat disimpulkan bahwa jumlah pembandingan (=C) untuk metode seleksi adalah sebagai berikut:


Jumlah penukaran (=M) yang dilakukan untuk metode seleksi tergantung pada keadaan datanya. Jumlah penukaran minimum dan maksimum dapat dirumuskan sebagai berikut:
Jumlah penukaran minimum terjadi bila data sudah dalam keadaan terurut, sebaliknya jumlah penukaran maksimum terjadi bila  data dalam keadaan urut terbalik.


contoh source code tentang simulasi sorting dengan algoritma selection sort. Dengan banyaknya angka ditentukan oleh inputan user. Catatan: simulasi berarti menampilkan perubahan secara terurut secara tahap demi tahap





#include "stdio.h"


void tampil(int data[], int n)
{
      int i;
      for (i=0;i<n;i++)
      printf("%3d",data[i]);
      printf("\n\n");
}


void urutan(int data[], int n)
{
int akhir, awal, j, tmp;
printf("\n");
printf("    Proses Pengurutannya \n\n");
for(awal=0;awal<n-1;awal++)
    {
      akhir=awal;
      for (j=awal+1;j<n;j++)
       if(data[akhir]>data[j])
          akhir=j;

       
           tmp=data[awal];
         data[awal]=data[akhir];
         data[akhir]=tmp;

      printf(" ke %d =" ,awal+1);
      tampil(data,n);

   }
}

void main ()
{
      int data[50],n;
      printf(" PENGURUTAN DATA DENGAN SELECTION SORT \n\n");
      printf("      masukkan banyak data : ");
      scanf("%d",&n);
      for (int a=0;a<n;a++)
    {
            printf("masukkan data ke %d   = ",a+1);
            scanf("%d",&data[a]);
      }
      urutan(data,n);
      printf("\n\n  hasil pengurutan : \n\n");
      tampil(data,n);

}

semoga bermanfaat..

Jumat, 08 April 2011

struktur data tentang struct

Struct adalah tipe data turunan yang didalamnya terdapat beberapa data/variable yang mempunyai tipe data yang berbeda-beda.
Dengan struct, kita bisa mengelompokkan berbagai nama dan tipe variable tersebut sesuai dengan kelompoknya. Hal ini tentunya bisa berguna untuk memudahkan dalam mengelompokkan sebuah variable. Sebagai contoh umum, ada terdapat berbagai nama variable : nama, npm, alamat, dll. Variabel – variable tersebut dapat kita kelompokkan menjadi satu dengan namadata_mahasiswa. Kemudian jika terdapat variable mata_kuliah, nilai, sks, kelas, dll dapat kita kelompokkan menjadi satu dengan nama krs. Itulah sebagian gambaran umum tentang struct.
Menggunakan operator titik (.) untuk mengakses tiap elemennya.
Variable-variabel yang membentuk suatu struktur ini selanjutnya disebut dengan elemen-elemen atau anggota struktur.dalam sustu struktur dimungkinksn berisi dengan elemen-elemen data bertipe int, float, char, dll.
Dalampemrograman C++, jikakitamembuatsuatu program yang memerlukanberbagaitipe data yang akandigunakan. Tentunyadengannama variable yang banyak pula. Dalam program yang sederhana, jikakitamanggunakansedikit variable tentutidakjadimasalah. Akan tetapijikakitaakanmembuatsebuah program yang lebihkompleks, denganberbagaimacamnamadantipe variable dalampendeklarasianya. Denganstruct, kitabisamengelompokkanberbagainamadantipe variable tersebutsesuaidengankelompoknya. Hal initentunyabisabergunauntukmemudahkandalammengelompokkansebuah variable.
Suatu struktur dapat dideklarasikan dengan menggunakan kata kunci struct. Contoh:
 Struct merk 
{
               Char kode[5];
int harga[35];
            }persediaan_barang




contoh source code program tentang Klinik sehat mengnginkan pendaftaran pasiennya dilakukan oleh computer.
Tugas :
Buatlah program yang mempunyai menu untuk melakukan :
a. Penambahan record baru
b. Penghapusan record tertentu berdasarkan isi datanya(lakukan dulu sequensial search).
c. Merubah (update) record tertentu berdasarkan isi datanya.
d. Menampilkan data
        Tiap record berisi tanggal lahir, nama, usia, jenis kelamin,alamat ,telepon,dan pekerjaan.
        Gunakan tipe data STRUCT




#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"conio.h"

struct DATA
{
      char nomorpasien[10];
      char tgldaftar[8];
      char nama[50];
      char usia[5];
      char jenkel[5];
      char alamat[50];
      char telp[50];
      char pekerjaan[50];
};

DATA pasien[100];

source code lengkapnya bisa klik DISINI
semoga bermanfaat

Share

Twitter Delicious Facebook Digg Stumbleupon Favorites More