Searching

NAMA : PUTU ERIK RUSBIANTARA

NIM : 060010061

KELAS : F081

METODE SEARCHING (Sequential Search & Binary Search)

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).

1. Pencarian sekuensial (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();

}

2. Pencarian Biner (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 )

- Algoritma lebih rumit, tidak baik untuk data berangkai

Tinjauan Materi :

1. Antony, Pranata, 2000, Algoritma dan Pemrograman, J&J Learning, Yogyakarta.

2. http://74.125.153.132/search?q=cache:k-qZ0Kank5AJ:mti.ugm.ac.id/~yudhistira/ResourceMTI/Tutorial/Yudhistira/Modul%25202.doc+searching+(sequential-binary+search)&cd=10&hl=id&ct=clnk&gl=id

Sorting

Pengimplementasian metode Sorting (Algoritma & Struktur data) pada bahasa C

Sorting / pengurutan biasanya dilakukan untuk tujuan mempermudah pencarian. Pengurutan data baik dari segi ascending (dari nilai terkecil ke terbesar) atau descending (dari nilai terbesar ke terkeci).Ketika akan melakukan sortir di computer , maka hal-hal yang akan dipertimbangkan ,meliputi :
1. Perlu tidaknya data disortir
2. Besarnya atau banyaknya data yang akan disortir
3. Kemampuan atau kapasitas computer atau media penyimpanan data
4. Metode sortir
Pada garis besarnya, ada tiga teknik sortir :
1. Insertion sort (sortir penyisipan)
2. Selection sort (sortit pemilihan)
3. Exchange short (sortir penukaran)
Teknik sortir sangat erat kaitannya dengan proses perbandingan dan penukaran tempat antarelemen data. Kita tidak dapat menentukan dengan pasti , mana dari ketiga teknik sortir tersebut yang merupakan teknik terbaik (melakukan perbandingan dan penukaran tempat antarelemen dan yang paling sedikit). Banyaknya proses perbandingan dan penukaran tempat antar elemen data tersebut juga terkait dengan susunan elemen – elemen datanya.
Sehingga , kecepatan dalam melakukan sortir juga ditentukan atas tiga kondisi susunan elemen-elemen datanya. Waktu terbaik akan diperoleh ketika susunan elemen datanya sudah sama dengan susunan yang diinginkan melalui sortirnya. Waktu terburuk akan didapatkan ketika susunan elemen – elemen datanya terbalik dari susunan yang dikehendaki sortirnya. Waktu rata-rata diperoleh dengan memperhitungkan berbagai susunan bentuk elemen-elemen datanya.
1. Insertion sort
Teknik ini adalah dengan membandingkan elemen ke n (n mulai dari 2 hingga elemen terakhir) dengan elemen – elemen sebelumnya. Bila elemen yang dibandingkan bernilai lebih kecil , maka tukar posisinya.
Contoh : 8,3,7,4
Pada langkah pertama, elemen kedua akan dibandingkan dengan elemen pertama, 3 dibandingkan dengan 8 , karena 3 lebih kecil dari 8, maka kedua elemen tersebut saling ditukar tempatnya yang menghasilkan urutan 3,8,7,4 (dua elemen pertama sudah diurut). Pada langkah kedua , elemen ketiga akan dibandingkan dengan 8 , terjadi penukaran tempat yang menghasilkan urutan 3,7,8,4. Selanjutnya 7 tersebut dibandingkan dengan elemen pertama, yaitu 3. Tidak terjadi penukaran tempat (3 elemen pertama sudah diurut).
Pada langkah ketiga , elemen keempat yaitu 4 dibandingkan dengan elemen ketiga. Angka 4 lebih kecil dari 8, terjadi penukaran tempat, hasil sementara adalah 3,7,4,8. Angka 4 tadi dibandingkan dengan elemen kedua,4 lebih kecil dari 7, terjadi penukaran tempat, hasil sementara adalah 3,4,7,8. Selanjutnya angka 4 tadi dibandingkan dengan elemen pertama, yaitu 3. Karena 4 lebih besar dari 3, maka tidak terjadi penukaran tempat lagi (empat elemen pertama sudah urut=hasil akhir).
Sub-sub langkahnya ketiganya : 3,7,8,4 (awal) -> 4 dibandingkan 8, ditukar
hasilnya : 3,7,4,8 -> 4 banding 7, tukar,
hasilnya : 3,4,7,8 -> 4 banding 3,tetap
hasilnya : 3,4,7,8 (akhir)
Sintak Implementasi insertion sort dalam bhs C adalah sbb:
void insertionsort(int arr[]) {
int i,j;
for (i = 1; i <>
int temp = arr[i];
int pos = i;
for (j = i; j > 0; j--) {
if (temp <>
arr[j] = arr[j-1];
pos--;
}
}
arr[pos]=temp;
}
}
void insertion_sort()
{
int temp, i, j;
for (i=1; i
{
temp = data[i];
j = i-1;
while (data[j] > temp && j>=0)
{
data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
cout<<"insertion sort selesai!"< } 2. Selection sort Teknik ini adalah mencari nilai elemen terkecil kemudian letakkan dan tukar dengan posisi n (n mulai dari 1 hingga elemen terakhir -1). Contoh : 8,3,7,4 Pada langkah pertama, hasil sortirnya 3, 8,7,4 (mulai dari elemen pertama, elemen terkecil = 3, letakkan dan tukarkan dengan elemen pertama). Pada langkah kedua , hasil sortirnya 3,4,7,8 (mulai dari elemen kedua, elemen terkecil = 4, letakkan dan tukarkan dengan elemen kedua). Pada langkah ketiga , hasil sortirnya 3,4,7,8 (mulai dari elemen ketiga, elemen terkecil =7, letakkan dan tukarkan dengan elemen ketiga, hasilnya ternyata tetap). Sintak Implementasi selection sort dalam bhs C adalah sbb: void selection_sort() { int pos, i, j; for (i=0; i { pos = i; for (j=i+1; j { if (data[j] < pos =" j; } if (pos != i) tukar(pos,i); } cout<<" i =" 0;">
int min = arr[i];
int pos = i;
for (j = i; j <>
/* Cari nilai yang terkecil */
if (arr[j] <>
min = arr[j];
pos = j;
}
}
/* Tukar nilai terkecil ke arr[i] jika pos tdk sama i */
if(i!=pos) {
int temp = arr[i];
arr[i] = arr[pos];
arr[pos] = temp;
}
}
}

3. Exchange sort
Contoh sortir umum yang menggambarkan exchange sort adalah bubble sort. Algoritma dari teknik ini adalah dengan melakukan proses perbandingan sebanyaknya n elemen dimulai dari n=1 (selanjutnya disebut mulai=1). Bandingkan seluruh elemen diawali dari elemen sebelah kanan hingga ke n. Bila elemen tersebut < 1="n." i="0;" j="(i+1);"> data[j]) tukar(i,j);
}
}
cout<<"Exchange sort selesai!"< } Exchange sort->Bubble sort pada bahasa C :
void bubble_sort()
{
For (int i=1;i=i;j–)
{
If (data[j] < temp =" data[a];">
data[j-1]) //data descending

Tinjauan Materi :
1. Struktur Data 2, Author: Taufik Fuadi Abidin, M.Tech Ph.D
2. Bambang,Wahyudi,2003,PengantarStrukturDataDan Algoritma,Andi,Yogyakarta.
3. http://genduet.wordpress.com/2009/03/19/bubble-sort/

Linked List Dalam Bahasa C

Linked List Dalam Bahasa C++

I. Pengertian

Dalam masa sekarang ini kita dituntut untuk berpikir cerdas dalam menentukan metode yang kita butuhkan sebelum merancang sebuah program, termasuk dalam hal pengefisienan data. Kebutuhan yang kompleks menuntut semakin bertambahnya data pada sebuah system. jika diumpamakan, pada sebuah system yang memiliki jumlah record yang banyak, dan setiap record memiliki data yang cukup besar,kita tidak mungkin mengedit satu data kedata lainnya, cara tersebut sangat rumit dan banyak menghabiskan waktu user, maka dari itu diperlukan suatu metode dalam mengurutkan jumlah data agar menjadi satu kesatuan dan tentunya saling berhubungan,salah satu metodenya ialah linked list. Linked List atau yang sering dikenal dengan senari berantai merupakan salah satu metode pembelajaran dalam bahasa C,linked list dapat diartikan sebagai rantai data yang saling berhubungan antara satu dengan yang lainnya agar mempermudah dalam mengedit field data yang tersimpan dalam jumlah yang sangat kompleks. Dalam linked list terdapat istilah node” yang berarti kumpulan elemen-elemen dan terkait yang terdapat pada linked list. Sebelum memahami linked list kita hendaknya terlebih dahulu memahami apa itu node, node pada linked list dibagi menjadi 2 bagian yaitu bagian data dan penghantar data atau yang di kenal dengan nama pointer”. Untuk lebih jelasnya, node terlihat pada gambar di bawah ini:

Dari gambar diatas diilustrasikan beberapa node, setiap node memiliki masing-masing data dan terdapat pointer yang dijadikan sebagai penghubung atau penunjuk arah dari satu data ke data yang lainnya. Null berarti menunjukan suatu elemen tidak menunjukan kondisi apapun.

II. Perancangan Linked list

a. Single Linked list

Tahapan pertama ialah membuat struct (karena setiap node akan berbentuk struct) Dan memiliki satu buah fungsi pointer juga bertype struct yang akan menghubungkan setiap node .

Contoh Rancangan sintaknya seperti berikut :

struct tnode

{

int cobalink;

struct tnode *next;

}

Penjelasannya :

*Pendeklrasian next sebagai pointer yang dijadikan penghubung antar node yang saling berkaitan.

Tahapan selanjutnya mendeklarasikan variable yang bertype struct tnode yang berfungsi sebagai head,node aktif, linked list,dan node sementara. Pendeklrasiannya sbb:

struct tnode *head=NULL, *curr=NULL,

*node=NULL;

Untuk membuat single linked list,kita terlebih dahulu harus mengisikan field dengan nilai tertentu(cobalink),

Sintaknya sbb :

for (i=0; i<6;>

{

node = (struct tnode *)

malloc (sizeof(struct tnode));

node -> cobalink = i;

if (head == NULL)

{

head = node;

curr = node;

}else

{

curr -> next = node;

curr = node;

}

}

curr -> next = NULL;

curr = head;

while (curr != NULL)

{

printf(“%d “, curr -> cobalink);

curr = curr -> next;

}

printf(“\n”);

#include

#include

int main()

{

struct tnode

{

int cobalink;

struct tnode *next;

};

struct tnode *head=NULL,

*curr=NULL, *node=NULL;

int i;

for (i=0; i<5;>

{

node = (struct tnode *)

malloc (sizeof(struct tnode));

node -> x = i;

if (head == NULL)

{

head = node;

curr = node;

}else

{

curr -> next = node;

curr = node;

}

}

curr -> next = NULL;

curr = head;

while (curr != NULL)

{

printf(“%d “, curr -> x);

curr = curr -> next;

}

printf(“\n”);

return 0;

}

Penjelasannya :

Kita membuat perulangan dari 0 – 5,perulangan tersebut akan membentuk 6 node yang setiap fieldnya (cobalink) akan bernilai 0 – 5,pada sintak tersebut terdapat perintah “malloc” ,fungsi dari perintah tersebut ialah memesan alokasi penempatan memori pada program. Setelah itu program akan menguji apakah head bernilai null (bernilai Null jika head hanya memiliki satu node), jika keadanya lain ( else ) maka kita akan menghubungkan pointer next dari node aktif ke node yang baru (menghubungkan node lama dengan node baru), tahapan berikutnya ialah menghubungkan pointer next terakhir ke Null,jika sintak sucses di jalankan maka terbentuklah single list baru, agar lebih jelas dari pembuktian dari kode tersebut kita mengeceknya dilihat dengan kode yang berisikan perintah print’.pada sintak tersebut dijelaskan node aktif diletakkan pada posisi head,setelah itu node aktif di pindahkan ke posisi sebelumnya dan tahap terakhir kita hanya menambahkan sintak pemanggilan untuk melakukan dealokasi (ditunjukan dengan sintak à#include …dst hingga selesai..

b. Double Linked List

Lain Halnya dengan single List, double Linked List adalah suatu linked list yang mempunyai 2 penunjuk ke data sebelumnya dan berikutnya, memiliki 2 buah pointer, setiap node akan terhubung dengan pointer kanan dan kiri , contoh sintak dari metode double linked list ialah sebagai berikut :

struct tnode

{

int cobalink;

struct tnode *prev;

struct tnode *next;

};

struct tnode *head=NULL,

*curr=NULL, *node=NULL,

*tail=NULL;

int i;

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

{

node = (struct tnode *)

malloc (sizeof(struct tnode));

node -> cobalink = i;

if (head == NULL)

{

head = node;

head -> prev = NULL;

curr = node;

}else

{

curr -> next = node;

node -> prev = curr;

curr = node;

}

}

curr -> next = NULL;

tail = curr;

if (head == NULL)

{

head = node;

head -> prev = NULL;

curr = node;

}else

{

curr -> next = node;

node -> prev = curr;

curr = node;

}

curr = head;

while (curr != NULL)

{

printf(“%d “, curr -> cobalink);

curr = curr -> next;

}

printf(“\n”);

curr = tail;

while (curr != NULL)

{

printf(“%d “, curr -> cobalink);

curr = curr -> prev;

}

printf(“\n”);

#include

#include

int main()

{

struct tnode

{

int cobalink;

struct tnode *prev;

struct tnode *next;

};

struct tnode *head=NULL,

*curr=NULL, *node=NULL,

*tail=NULL;

int i;

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

{

node = (struct tnode *)

malloc (sizeof(struct tnode));

node -> cobalink = i;

if (head == NULL)

{

head = node;

head -> prev = NULL;

curr = node;

}else

{

curr -> next = node;

node -> prev = curr;

curr = node;

}

}

curr -> next = NULL;

tail = curr;

curr = head;

while (curr != NULL)

{

printf(“%d “, curr -> cobalink);

curr = curr -> next;

}

printf(“\n”);

curr = tail;

while (curr != NULL)

{

printf(“%d “, curr -> cobalink);

curr = curr -> prev;

}

printf(“\n”);

return 0;

}

Perintah yang ada pada linked list :

• Free

Yaitu sintak yang berfungsi untuk mengosongkan memori yang telah teralokasikan sebelumnya, sehingga dalam keadaan tersebut keadaan memori telah terbebas.

• Malloc

Yaitu salah satu sintak yang berfungsi untuk meminta pengalokasian memori pada sebuah system.

Beberapa operasi yang ada pada linked list :

1. Insert

Menambahkan suatu simpul baru ke dalam suatu linked list

2. IsEmpty

Menentukan apakah linked list kosong atau masih berisi data

3. Find First

Pencaharian elemen pertama dari sebuah linked list

4. Find Next

Pencaharian elemen sesudah elemen yang muncul sebelumnya

5. Retrieve

Mengambil elemen yang ditunjukan

6. Update

Menambah isi dari elemen yang ada sebelumnya

7. Delete head

Menghapus elemen yang ditunjukan oleh head

8. Clear

Menghapus linked list yang telah ada sebelumnya

Tinjauan Materi :

- www.infolinux.web.id

- http://herison.pinkynet.web.id/2009/05/linked-list/

- Andi, Penerbit, (2004). Pemrograman C++, Abdul Kadir, semarang.