SEARCHING DAN SORTING
SEARCHING
Pencarian (Searching) merupakan proses yang
fundamental dalam pemrograman, guna menemukan data (nilai) tertentu di dalam
sekumpulan data yang bertipe sama. Fungsi pencarian itu sendiri adalah untuk
memvalidasi (mencocokkan) data.
Sequintal Search
Sequential Search adalah teknik pencarian
data dimana data dicari secara urut dari depan ke belakang atau dari awal
sampai akhir. Kelebihan dari proses pencarian secara sequential ini jika data
yang dicari terletak didepan, maka data akan ditemukan dengan cepat. Tetapi
dibalik kelebihannya ini, teknik ini juga memiliki kekurangan. Pertama, jika
data yang dicari terletak dibelakang atau paling akhir, maka akan membutuhkan
waktu yang lama dalam proses pencariannya. Kedua, beban komputer akan semakin
bertambah jika jumlah data dalam array sangat banyak.
Contoh programnya :
// Program sequential search#include <iostream.h>
int tabInt[10]= {34,67,23,28,98,15,89,67,28,18};
void main()
{
int i,bil_cari,ketemu;
i=0;
bil_cari=89;
ketemu = 0;
while((i<10) && (ketemu==0))
{
if(tabInt[i] == bil_cari)
ketemu=1;
else
i=i+1;
}
if(ketemu == 1)
cout<<”data ada dalam larik”;
else
cout<<”data tidak ada dalam larik”;
}
Binary
Search
Adalah teknik pencarian data dalam array dengan cara membagi
array menjadi dua bagian setiap kali terjadi proses pengurutan. Prinsip
pencarian biner adalah:
·
Data diambil dari posisi 1 sampai posisi
akhir N
·
Kemudian cari posisi data tengah dengan
rumus (posisi awal + posisi akhir) / 2
·
Kemudian data yang dicari dibandingkan
dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?
·
Jika lebih besar, maka proses pencarian
dicari dengan posisi awal adalah posisi tengah + 1
·
Jika lebih kecil, maka proses pencarian
dicari dengan posisi akhir adalah posisi tengah – 1
·
Jika data sama, berarti ketemu.
Contoh
Data:
Misalnya
data yang dicari 17
0 1 2 3
4 5 6
7 8
3 9 11 12 15 17 23 31 35
A B C
Karena
17 > 15 (data tengah), maka: awal = tengah + 1
0 1 2 3
4 5 6
7 8
3 9 11 12 15 17 23 31 35
A B C
Karena
17 < 23 (data tengah), maka: akhir = tengah – 1
0 1 2 3
4 5 6
7 8
3 9 11 12 15 17 23 31 35
A=B=C
Karena
17 = 17 (data tengah), maka KETEMU!
Programnya:
int
binary_search(int cari){
int l,r,m;
l = 0;
r = n-1;
int ktm = 0;
while(l<=r && ktm==0){
m = (l+r)/2;
if(data[m] == cari) ktm=1;
else if (cari < data[m]) r=m-1;
else l=m+1;
}
if(ktm==1) return 1; else return 0;
}
Sorting
Pengurutan data
dalam struktur data sangat penting terutama untuk data yang bertipe data
numerik ataupun karakter. Pengurutan dapat dilakukan secara ascending (urut
naik) dan descending (urut turun). Pengurutan (Sorting) adalah proses
pengurutan data yang sebelumnya disusun secara acak sehingga tersusun secara
teratur menurut aturan tertentu
Contoh:
Data
Acak : 5, 6, 8, 1, 3, 25, 10
Ascending : 1, 3, 5, 6, 8, 10, 25
Descending
: 25, 10, 8, 6, 5, 3, 1
Deklarasi
Array Untuk Sorting
Deklarasikan
secara global:
int
data[100];
int
n; //untuk jumlah data
Prosedur Tukar 2 Buah Data
void tukar(int a,int b){
int tmp;
tmp = data[a];
data[a] = data[b];
data[b] = tmp;
}
BUBBLE
SORT
Metode sorting termudah. Diberi nama
“Bubble” karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke
posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda. Bubble
Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen
berikutnya. Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua
elemen tersebut ditukar, jika pengurutan ascending. Jika elemen sekarang lebih
kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar, jika
pengurutan descending. Algoritma ini seolah-olah menggeser satu per satu elemen
dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya. Ketika
satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian
seterusnya. Kapan berhentinya? Bubble sort berhenti jika seluruh array telah
diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai
perurutan yang telah diinginkan.
Proses
1
22 10 15 3 8 2
22 10 15 3 2↔ 8
22 10 15 2↔ 3 8
22 10 2↔15 3 8
22 2↔10 15 3 8
2 ↔22 10 15 3 8
Pada
proses diatas, pegecekan dimulai dari data yang paling akhir, kemudian dibandingkan
dengan data di depannya, jika data di depannya lebih besar maka akan ditukar.
Proses
2
2 22 10 15 3 8 à Tidak ada penukaran, karena 3 <8
2 22 10 15 3 8
2 22 10 3↔15 8
2 22 3↔10 15 8
2 3↔22 10 15 8 à
Pengurutan berhenti di sini!
2 3 22
10 15 8
Pada
proses kedua, pengecekan dilakukan sampai dengan data ke-2 karena data pertama
pasti sudah paling kecil.
Proses
3
2 3 22 10 15 8
2 3 22 10 8↔15
2 3 22 8↔10 15
2 3 8↔22 10 15 à
Pengurutan berhenti di sini!
2 3 8 22 10 15
2 3 8 22 10 15
Proses
4
2 3 8 22 10 15 à Tidak ada penukaran, karena 10 < 15
2 3 8 22 10 15
2 3 8 10↔22 15 à
Pengurutan berhenti di sini!
2 3 8 10 22 15
2 3 8 10 22 15
2 3 8 10 22 15
Proses
5
2 3 8 10 22 15
2 3 8 10 15↔22 à Pengurutan berhenti di sini!
2 3 8 10 15 22
2 3 8 10 15 22
2 3 8 10 15 22
2 3 8 10 15 22
Prosedur Bubble Sort
void bubble_sort(){
for(int i=1;i<n;i++){
for(int j=n-1;j>=i;j--){
if(data[j]<data[j-1]) tukar(j,j-1); //ascending
}
}
}
Dengan
prosedur diatas, data terurut naik (ascending), untuk urut turun (descending),
silahkan ubah bagian:
if (data[j]<data[j-1]) tukar(j,j-1);
Menjadi:
if (data[j]>data[j-1]) tukar(j,j-1);
“The
bubble sort is an easy algorithm to program, but it is slower than many other
sorts”
SELECTION
SORT
Merupakan kombinasi antara sorting dan searching .Untuk setiap
proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai
terkecil atau terbesar 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]), pada putaran kedua akan
dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]).
Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks
pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.
Proses
1
0 1 2 3 4 5
32
75 69 58 21 40
Pembanding Posisi
32
< 75 0
32
< 69 0
32
< 58 0
32
> 21 (tukar idx) 4
21
< 40 4
Tukar
data ke-0 (32) dengan data ke-4 (21)
0 1 2 3 4 5
21
75 69 58 32 40
Proses
2
0 1 2 3 4 5
21
75 69 58 32 40
Pembanding
Posisi
75
> 69 (tukar idx) 2
69
> 58 (tukar idx) 3
58
> 32 (tukar idx) 4
32
< 40 4
Tukar
data ke-1 (75) dengan data ke-4 (32)
0 1 2 3 4 5
21
32 69 58 75 40
Proses
3
0 1 2 3 4 5
21
32 69 58 75 40
Pembanding
Posisi
69
> 58 (tukar idx) 3
58
< 75 3
58
> 40 5
Tukar
data ke-2 (69) dengan data ke-5 (40)
0 1 2 3 4 5
21
32 40 58 75 69
Proses
4
0 1 2 3 4 5
21
32 40 58
75 69
Pembanding
Posisi
58
< 75 3
58
< 69 3
Tukar
data ke-3 (58) dengan data ke-3 (58)
0 1 2 3 4 5
21
32 40 58 75 69
Proses
5
0 1 2 3 4 5
21
32 40 58 75 69
Pembanding
Posisi
75
> 69 5
Tukar
data ke-4 (75) dengan data ke-5 (69)
0 1 2 3 4 5
21
32 40 58 69 75
Prosedur
Selection Sort
void selection_sort(){
for(int i=0;i<n-1;i++){
pos = i;
for(int j=i+1;j<n;j++){
if(data[j] < data[pos]) pos = j;
//ascending
}
if(pos != i) tukar(pos,i);
}
}
