Selasa, 30 Juni 2009

Searching

Pengertian Searching beserta pencarian binari dan sekuensial 

Pencarian (searching) 

Dalam istilah bahasa inggris biasanya searching tuh artinya adalah pencarian sesuatu hal. Nah, kalau dalam bahasa pemograman, pencarian (searching) merupakan suatu tindakan untuk mendapatkan suatu data dalam kumpulan data. Kita bisa cari contoh yang simple aja dalam kehidupan sehari-hari kamu, mungkin kamu ingin mencari suatu kata dalam kamus bahasa inggris, jika dicari satu persatu mungkin kamu akan kewalahan kali yah, bahkan bisa saja seharian kata yang kamu cari tuh nggak ditemukan, capek banget kan?? hal itu akan menguras banyak waktu mu. Dengan adanya abjad A sampai dengan Z di pinggir kamus, maka kamu-kamu dengan mudah dapat mencari kata tersebut. Hal itu kita bisa sebut dengan “Searching”. Dengan mengibaratkan “Searching” dalam kehidupan sehari-hari mu, maka kamu akan lebih mudah memahami kata searching atau pencarian. 

Dalam keperluan nya untuk mencari data, terdapat beragam algoritma pencarian (search algorithm). Mungkin, kalian bertanya-tanya, apa sih algoritma pencarian itu. Algoritma pencarian adalah “algoritma yang menerima sebuah argumen ‘a’ dan mencoba untuk menemukan sebuah rekaman yang memiliki kunci ‘a’. Pencarian dapat dilakukan terhadap data yang secara keseluruhan berada dalam memory komputer ataupun yang berada dalam penyimpanan ekternal (hardisk). Pencarian yang dilakukan terhadap data yang berada dalam komputer di kenal dengan pencarian internal sedangkan pencarian yang dilakukan pada media penyimpanan eksternal disebut pencarian ekternal. Pencarian internal meliputi Pencarian sekuensial (sequential search) dan pencarian biner (binary search). 



Pencarian Sekuensial 

“Sequential search atau Pencarian sekuensial” bisa disebut dengan pencarian linear yang merupakan model pencarian yang paling simpel dan sederhana banget deh yang dapat dilakukan terhadap suatu kumpulan data. Suatu tekhnik pencarian dalam array (1 dimensi) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu. 

Biar kalian lebih paham secara konsep, penjelasannya adalah sebagai berikut : 
Keunggulan dari pencarian sekuensial ini adalah jika data yang dicari terletak di indeks array terdepan maka waktu dalam pencarian nya sangat cepat, dalam artian waktu yang minim sekali. Keburukannya adalah kalau jika data indeks array nya yang dicari paling belakang, maka waktu yang dicari tuh lama banget (maksimal). 

Terdapat L yang merupakan larik yang berisi n buah data ( L[0],L[1]…….L[n-1]) dan k adalah data yang akan dicari. Pencarian dilakukan untuk menemukan L[i] = k dengan i adalah bilangan indeks terkecil yang memenuhi kondisi 0<= k <=n-1. Tentu saja bahwa data yang di cari tidak ditemukan. 
Jika misalnya terdapat angka 4, maka ditulis ada, sedangkan jika dimunculkan angka 6, namun angka 6 tidak ada maka akan muncul tulisan tidak ada. 
Berikut merupakan program yang telah dibuat sebelumnya : 

L = {4,12,9,-2,12,7,1,100} 

Tahukah kamu dimana posisi 12 yang pertama ? 

Nah, dalam hal ini k adalah 12 dan k ditemukan berupa indeks 2. Angka 12 yang pertama akan dipilih oleh program, karena secara logika angka 12 merupakan data yang pertama muncul. Coba deh kamu bayangin aja misalnya dalam antrian, orang yang mengantri di depan akan duluan mendapatkan giliran. 

Berikut merupakan contoh program Pencarian Sekuensial (Sequential Search): 

//Sequential searching 
#include 
#include 
void main() 

clrscr(); 
int data[8] = {4,12,9,-2,12,7,1,100}; 
int cari,index; 
int ketemu=0; 
cout<<"masukkan data yang ingin dicari = "; 
cin>>cari; 
for(int i=0;i<8;i++) 

if(data[i] == cari) 

ketemu=1; 
index = i; 
break; 


if(ketemu == 1) 

cout<<"Data ada!"<
cout<<"Data terletak di index ke - "<

else cout<<"Data Tidak ada!"<
getch(); 


tampilannya jika program ini dijalankan : 


 







Pencarian terhadap data urut “ Pencarian Binari ( Binary Search)” : 

“Pencarian Sekuensial” akan memakan banyak waktumu apabila mencari data indeks array yang paling akhir dan ditambah lagi kalau datanya tu banyak banget Apalagi kumpulan data udah dalam keadaan urut, Untuk mengatasi masalah ini dan untuk menyingkat waktu terdapat algoritma yang dirancang agar pencarian data dilakukan secara efesien. Metode yang digunakan dikenal dengan sebutan “pencarian biner atau binary search”. Metode ini merupakan tekhnik pencarian data dalam dengan cara membagi dua bagian setiap kali terjadi proses pengurutan. 

Data yang dicari harus diurutkan terlebih dahulu berdasarkan suatu urutan tertentu yang dijadikan kunci pencarian. Pencarian biner dilakukan dengan membagi larik menjadi dua bagian dengan jumlah yang sama besar atau berbeda 1 jika jumlah data semula ganjil. Data yang dicari kemudian dibandingkan dengan data terakhir pada bagian pertama, jika lebih besar dari data tengah maka akan diulang dari awal dengan +1, jika lebih kecil maka sebaliknya, dari data tengah maka -1. Dalam hal ini ada empat kemungkinan yang terjadi yaitu : 

1. Data yang dicari sama dengan elemen terakhir pada bagian pertama dalam larik. Jika kondisi ini terpenuhi, data yang dicari berarti ditemukan. Data dicari dari posisi satu sampai posisi akhir N. jika tidak diketemukan maka data akan terus mencari sampai menemukan data yang sama. 
2. Data yang dicari bernilai kurang dari nilai elemen terakhir pada bagian pertama dalam lari. Pada keadaan ini, pencarian diteruskan pada bagian pertama. 
3. Data yang dicari bernilai lebih dari nilai elemen terakhir pada bagian pertama dalam larik. Pada keadaan ini, pencarian diteruskan pada bagian kedua. 
4. Pada pengurutan biner, data akan dibandingkan dengan data yang ditengahnya, data tengah dicari dengan menjumlahkan posisi awal dengan posisi akhir kemudian hasil jumlah data tersebut dibagi menjadi 2. Data tersebut akan dibandingkan dengan data yang ditengah apakah akan lebih besar atau lebih kecil. 

Berikut merupakan contoh program Pencarian Binari ( Binary search) : 

//Pencarian Binari 
#include 
#include 

int data[10] = {1,3,4,7,12,25,40,65,78,90}; //variabel global 

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 < data[m]) 
r = m-1; 
else l = m+1; 

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


void main() 

clrscr(); 
int cari,hasil; 
cout<<"masukkan data yang ingin dicari = "; 
cin>>cari; 
hasil = binary_search(cari); 
if(hasil == 1) 

cout<<"Data ada!"<

else 
if(hasil == 0) 
cout<<"Data Tidak ada!"<
getch(); 


Berikut contoh program yang udah di jalankan: 


 




Untuk mengetahui kekurangan dan kelebihan masing-masing metode, saya akan mengambi kesimpulan dari penjelasan diatas semoga bermanfaat banget buat kamu. 

“Pencarian Sekuensial (sequential search)” : 

1. Relatif lebih cepat dan efisien, dapat menghemat waktumu karena pencarian datanya cepat. 
2. Untuk data yang terbatas tetapi kurang cepat untuk data dalam jumlah besar (pencarian datanya lama banget, apalagi mencari indeks array yang paling akhir) 
3. Algoritma-Nya agak sederhana 
4. Beban komputasi nya cenderung lebih besar 


“Pencarian Biner (binary search)” : 

1. Sangat rumit, membutuhkan waktu yang lebih banyak. 
2. Untuk data dalam jumlah besar, waktu searching lebih cepat tetapi data harus sudah di-sorting lebih dulu ( dalam keadaan terurut ), jadi mesti mengurutkan data terlebih dulu. 
3. Algoritma-Nya agak rumit, tapi hasilnya bisa memuaskan kamu lho, soalnya agak cepat dalam pencarian datanya 
4. Beban komputasi-nya lebih kecil, tidak baik untuk data berangkai. 

Pengertian Sorting

Pengurutan Data (Sorting)

Dalam Bahasa pemograman C++ pengurutan disebut juga dengan “Sorting“. Pengurutan atau “Sorting“ adalah suatu proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga tersusun secara teratur menurut aturan tertentu ( untuk data yang bertipe numerik atau karakter).Misalkan dalam kehidupan sehari-hari qta dihadapkan dalam memilih pakaian dalam lemari lebih sulit kalau pakaian tersebut berantakan tempatnya tentunya pakaian yang sudah terurut akan lebih cepat untuk dicari.Berdasarkan atas pemilahan warna/jenis pakaian.
Pengurutan data dalam pemograman biasanya dan pada umumnya untuk data yang bertipe data numerik ataupun karakter. Pada bahasa pemograman terdapat 2 macam pengurutan yaitu, ascending (urut naik) dan descending urut turun. Ascending (urut naik) merupakan pengurutan dari angka yang nilainya lebih kecil kemudian menuju ke nilainya yang lebih besar. Sedangkan descending (urut turun) adalah sebaliknya, yaitu pengurutan dari nilainya yang lebih besar kemudian menuju ke nilainya yang lebih kecil.

Contoh:
• Data dipilih secara acak : 14 8 10 12 2 6 4
• Ascending (urut naik) : 2 4 6 8 10 12 14
• Descending (urut turun) : 14 12 10 8 6 4 2


Berikut ini merupakan Metode Pengurutan Data (Sorting)

1. Bubble Sort

Nah, penjelasan awal adalah Metode bubble sort. Buble Sort merupakan metode yang sangat simpel dan mudah untuk melakukan pengurutan data , namun setiap metode tersebut pasti memiliki kelemahan dan keunggulan. Walaupun sangat sederhana namun, Metode ini mempunyai kelemahan yaitu, pada saat mengurutkan data yang sangat besar akan mengalami kekacuan, atau kinerja nya kurang baik. Mungkin kalian bingung ya, knapa sih namanya Buble, knapa nggak Circle Sort atau Soda sort aja (maav ney bukannya ngubah-ngubah metode). Berikut ini penjelasannya, “Bubble” karena proses pengurutan data nya tersebut secara bertahap bergerak/berpindah ke posisinya sesuai urutannya, misalkan saja anda meniup segelas air dengan menggunakan sedotan , tentunya akan mengeluarkan gelembung yang saling berurutan keluar dalam pipet. Pengurutan data Buble Sort dilakukan dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Penukaran tersebut baru dilakukan kalau kriterianya tersebut sudah terpenuhi.

Pengurutan Ascending (urut naik) : Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar. Pengurutan Descending ( urut turun): Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar. Nah, Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, Sekarang tergantung jenis pengurutannya, ascending (urut naik) atau descending (urut turun). Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya sampai dengan iterasi sebanyak n-1. Bubble Sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.

2. Exchange Sort

Pembahasan yang kedua mengenai Metode Exchange Sort. Metode ini merupakan metode pengurutan data yang hampir mirip dengan Bubble Sort ( Mirorr-Nya buble sort), bahkan mungkin juga metode Bubble Sort sama dengan Exchange Sort. Namun setiap metode pasti memiliki perbedaan, perbedaan antara Exchange Sort dan Bubble Sort terletak dalam hal bagaimana membandingkan antar elemen-elemennya.
Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi elemen pusat (pivot). Sedangkan Bubble sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen tersebut itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi,dan begitu seterusnya.

3. Selection Sort

Metode yang ketiga adalah Selection Sort merupakan metode pengurutan data kombinasi antara sorting dan searching. Kinerja metode ini sebagai berikut ini : Mula – mula suatu petunjuk (diberi nama posAwal ) yang menunjuk lokasi awal pengurutan data diatur agar berisi indeks pertama dalam larik. Selanjutnya dicari bilangan terkecil yang terletak antara posisi sesudah yang ditunjuk oleh penunjuk tersebut element yang terakhir dalam larik. Lokasi bilangan ini di tunjuk oleh posMin. Lalu tukarkan nilai bilangan terkecil tersebut dengan nilai yang di tunjukkan posAwal. Proses seperti ini di ulang dari posAwal bernilai 0 hingga n-2 , dengan n menyatakan jumlah element larik

4. Insertion Sort

Kamu pernah bermain kartu gak?? pastilah kamu tau kartu remi kan, pastinya kamu-kamu pernah mengkocok kartunya atau sebagai Bandarnya. Metode insertion sort ini merupakan metode pengurutan data yang mirip dengan cara orang mengurutkan kartu, selembar demi selembar kartu diambil dan disisipkan (insert) ke tempat yang seharusnya sehinggan penambahan kartu tersebut akan membuat semua kartu tetap terurutkan.
Pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya. Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang

5. Quick Sort

Pada tahun 1962, C. AR Hoare merupakan orang yang mengemukakan pertama kali Metode Quick sort. Metode ini merupakan metode pengurutan data yang agak rumit namun, sangat mudah jika ada data yang nilainya sangat besar, seperti yang saya katakan sebelumnya, jika metode tersebut simpel pastilah ada juga kekurangannya, begitu juga sebaliknya jika metode ini rumit maka kelebihannya juga ada, kira-kira seperti itu. Metode ini menggunakan strategi “pecah-belah” dengan mekanisme seperti berikut : Larik L[p..r] dengan indeks terkecil adalah p dan indeks terbesar adalah r disusun ulang (dipartisi) menjadi dua buah larik A[p..p] dan A[q+1…r] sehingga setiap elemen dalam A[p..q] selalu bernilai lebih kecil daripada A[q+1…r]. Selanjutnya kedua larik tersebut di urut secara rekursif. Dengan sendirnya kombinasi kedua larik tersebut membentuk larik dengan data yang telah di urut.