Pencarian (Searching)

Pencarian untuk array nilai tertentu adalah kegiatan yang umum
bahwa setiap programmer harus tahu cara melakukannya.Bryan
Roth membahas dua metode dasar pencarian dan berurut biner
Serta menunjukkan bagaimana mereka ke dalam kode C++.
Pencarian adalah operasi yang sangat berguna dalam bahasa C + + dan bahasa pemrograman lain. Pencarian sangat berguna dengan array. Terdapat juga banyak cara untuk mengambil keuntungan
Dari pencarian,sebagai contoh mencari barang tertentu dalam sebuah database inventaris,
Menerapkan metode pencarian dalam catalog perpustakaan.
Dalam artikel ini dua dasar metode pencarian akan diperkenalkan dan dibahas
Kedua metode yang berurut pencarian dan pencarian biner. Adalah penting untuk mengetahui kedua jenis pencarian dan bagaimana mereka melakukan sebelum bergerak untuk mencari metode lebih maju.
Berikut dua metode pencarian yaitu Sequential Search dan Binary Search :

Sequential Search

**Definisi : utama adalah nilai yang dicari dalam array.

Jenis paling sederhana adalah proses pencarian Berurut Pencarian(Sequential Search).

Pada berurut pencarian,setiap elemen array dibandingkan pada tombol tersebut, dalam rangka muncul

dalam array,sampai elemen pertama yang cocok dengan kunci yang ditemukan.jika pada saat

mencari untuk elemen yang ada di dekat bagian depan array, maka pencarian akan berurut

menemukannya dengan cepat.Semakin banyak data yang harus dicari,maka akan semakin

lama waktu yang dibutuhkan untuk menemukan data yang sesuai dengan menggunakan tombol proses ini.

Contoh algoritma Sequential Search :

#include

#include

int cari_linear(int array[],int ukuran, int cari);

void main()

{

const int ukuran=10;

int array[ukuran]={25,36,2,48,0,69,14,22,7,19};

cout<<"isi dari array : "<

for(int i=0;i

cout<<" "<

int cari;

int tanda=-1;

cout<<"\n masukkan data yang dicari : ";

cin>>cari;

tanda= cari_linear(array,ukuran,cari);

if (tanda!=-1)

cout<<"\n data tersebut ditemukan pada posisi : array["<<

tanda<<"],"<<" atau deret ke-"<<(tanda+1);

else

cout<<"\n data tersebut tidak ditemukan ";

getch();

}

int cari_linear(int array[],int ukuran,int cari)

{

int tanda=-1;

for(int i=0;i

{

if(cari==array[i])

{

tanda=i; break;

}

}

return tanda;

}

Binary Search

Metode Binary Search :

Jika kita mempunyai sebuah file dari record-record yang telah dijalankan,

kita dapat melanjutkan menghapuskan memory pemeriksaan yang diperlukan

untuk mendapatkan kembali sebuah record yang telah dipakai oleh suatu teknik

binary search.

Suatu binary search dibandingkan dengan kunci dari pencarian record dengan

record tengah dari sebuah file. Kemudian masing-masing pencarian record

yang telah ditempatkan atau setengah dari file yang telah dihilangkan dengan

pertimbangan yang lebih lanjut. Dalam kasus yang sebelumnya, proses pemban-

dingan dari record tengah dilanjutkan dalam record-record selanjutnya.

Jika kita harus menghilangkan bagian atas dari sebuah file termasuk

record yang telah dibandingkan berlawanan. Selanjutnya jika kita harus

menghilangkan bagian bawah dari sebuah file termasuk record yang telah

dibandingkan berlawanan. Dalam pengulangan proses dari pembandingan

berlawanan dari record tengah, kita akhirnya akan menempatkan record yang

kita inginkan atau menentukan bahwa itu tidak ada dalam file ketika tidak

ada record-record selanjutnya.

Algoritma Binary Search :

Terendah = 1.

Tertinggi = n.

While terendah <>

Tengah = (terendah + tertinggi) / 2.

if nilai kunci = nilai (tengah). Then data ditemukan.

Else if nilai kunci > nilai (tengah). Then terendah = tengah + 1.

Else tertinggi = tengah - 1.

end

end

end

Mari kita amati sebuah contoh dari suatu binary search yang telah disajikan terhadap suatu file dari record-record yang telah disusun secara urut. Dalam contoh ini, kita mencari record-record dengan kunci 39, dimana berindikasikan record yang terbaru yang telah dibandingkan berlawanan dari tanda kurung besar membatasi record yang masih dibawah pertimbangan.

Contoh :

Di bawah ini adalah kunci–kunci carilah kunci 39 dengan mengunakan algoritma Binary Search.

[13, 16, 18, 27, 28, 29, 38, 39, 53].

1 2 3 4 5 6 7 8 9

File ini dinamakan File Sequential (secara berurutan).

Cara penyelesaian.

Bila di cari kunci 39 maka ;

Bila terendah = 1, dan tertinggi = 9,

maka 1 + 9 = 10 , lalu 10 / 2 = 5.

1. Nomor urut 5, adalah kunci 28 , tapi 28 <>

[13, 16, 18, 27, 28, 29, 38, 39, 53].

maka terendah = 5 , dan tertinggi = 9,

maka : 5 + 9 = 14

14 / 2 = 7.

2. Nomor urut 7 adalah 38 , tapi 38 <>

[13, 16, 18, 27, 28, 29, 38, 39, 53].

maka terendah = 8, dan tertinggi = 9, (karena mid + 1 jadi 7+1=8)

maka : 8 + 9 = 17

17 / 2 = 8,5 => 8,5 ≈ 8

3. Nomor urut 8 adalah kunci 39 , dimana kunci 39 = 39.

[13, 16, 18, 27, 28, 29, 38, 39, 53]

Metode Pengurutan Data (Sorting)

Ø Pengurutan berdasarkan perbandingan (comparison-based sorting)

• Bubble sort, exchange sort

Ø Pengurutan berdasarkan prioritas (priority queue sorting method)

• Selection sort

Ø Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method)

• Insertion sort

Ø Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer method)

• Quick sort

Quick Sort

Quick sort banyak digunakan untuk proses sorting,karena:
merupakan proses sorting yang umum digunakan,
mudah untuk diimplementasikan,
Prosesnya sangat cepat.
AturanQuick Sort:
Select
Pertama kita pilih elemen yang ditengah sebagai pivot, misalkan X.
Partition
kemudian semua elemen tersebut disusun dengan menempatkanX
pada posisi j sedemikian rupa sehingga elemen disebelah kiri1 lebih
X.
Rekursif
Kemudian proses diulang untuk bagian kiri dan kanan elemenX
dengan cara yg sama dengan langkah 1 sampai kondisi terurut.
algoritma quicksort :

void QuickSort(int L, int R)
{
int i, j;
int mid;

i = L;
j= R;
mid = data [(L+R) / 2];

do
{
while (data [i] < mid) i++;
while (data [j] > mid) j--;

if (i<= j)
{
tukar(i,j);
i++;
j--;
};
}while (i < j);

if (L < j) QuickSort (L,j);
if (i < R) QuickSort (i,R);
}

Insertion Sort

Pengurutan dengan cara membandingkan data ke-I (dimana I dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yag lebih kecil maka data tersebut disisipkan ke depan sesuai dengan posisi yang seharusnya.

Langkah 1 :

i= 1 2 3 4 5 6

22 10 15 3 8 2

Temp cek geser

10 temp<22 data ke-1-> posisi 2

Temp menempati posisi ke-1

10 22 15 3 8 2

Langkah 2 :

i= 1 2 3 4 5 6

10 22 15 3 8 2

Temp cek geser

15 temp<22 data ke-2-> posisi 3

Temp menempati posisi ke-2

10 15 22 3 8 2

Langkah 3 :

i= 1 2 3 4 5 6

10 15 22 3 8 2

Temp cek geser

3 temp<22 data ke-3-> posisi 4

temp<15 data ke-2 ->posisi 3

temp<10 data ke-1 ->posisi 2

Temp menempati posisi ke-1

3 10 15 22 8 2

Langkah 4 :

i= 1 2 3 4 5 6

3 10 15 22 8 2

Temp cek geser

8 temp<22 data ke-4-> posisi 5

temp<15 data ke-3 ->posisi 4

temp<10 data ke-2 ->posisi 3

temp>3 -

Temp menempati posisi ke-2

3 8 10 15 22 2

Langkah 5 :

i= 1 2 3 4 5 6

3 8 10 15 22 2

Temp cek geser

2 temp<22 data ke-5-> posisi 6

temp<15 data ke-4 ->posisi 5 temp<10 data ke-3 ->posisi 4

temp<8 data k-2->posisi 3

temp < style=""> data ke-1 ->data ke 2

Temp menempati posisi ke-1

2 3 8 10 15 22

Terurut :

2 3 8 10 15 22

algoritma insertion sort :

Procedure asc_Insert;

Var I,j,temp:byte;

Begin

for i:=2 to max do

begin

temp:=data[i];

j:=i-1;

while(data[j]>temp) and (j>0) do

begin

data[j+1]:=data[j]

dec(j);

end;

Data[j+1]:=temp;

End;

End;

Procedure decs_Insert;

Var I,j,temp:byte;

Begin

for i:=2 to max do

begin

temp:=data[i];

j:=i-1;

while(data[j]0) do

begin

data[j+1]:=data[j]

dec(j);

end;

Data[j+1]:=temp;

End;

End;

Selection Sort

Membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudian ditukar. Dan begitu seterusnya

Langkah 1 :

i = 1 2 3 4 5 6

22 10 15 3 8 2

Pembanding posisi

22 > 10 2

10 < style=""> 2

10 > 3 4

3 < style=""> 4

3 > 2 6

Posisi data ke-1(22) =6

Tukar data ke-1 dengan data ke-6

2 10 15 3 8 22

Langkah 2 :

i= 1 2 3 4 5 6

2 10 15 3 8 22

Pembanding posisi

10 < style=""> 2

10 > 3 4

3 < style=""> 4

3 < style=""> 4

Posisi data ke 2(10)=4

Tukar data ke-2 dengandata ke-4

2 3 15 10 8 22

• Langkah 3:

i= 1 2 3 4 5 6

2 3 15 10 8 22

Pembanding posisi

15 < style=""> 4

10 > 8 5

8< style=""> 5

Posisi data ke 3(15)=5

Tukar data ke-3 dengandata ke-5

2 3 8 10 15 22

Langkah 4 :

i= 1 2 3 4 5 6

2 3 8 10 15 22

Pembanding posisi

10 < style=""> 4

10 > 22 4

8< style=""> 5

Posisi data ke-4=tetap

Pada posisinya=4(tidak berubah)

2 3 8 10 15 22

Langkah 5 :

i= 1 2 3 4 5 6

2 3 8 10 15 22

Pembanding posisi

15 < style=""> 5

Posisi data ke-5=tetap

Pada posisinya=5(tidak berubah)

2 3 8 10 15 22

Terurut:

2 3 8 10 15 22

algoritma selection sort :

Procedure acending_Selection;

Var I,j,pos:byte;

Begin

for i:=1 to max-1 do

begin

pos:=I;

for j:=i+1 to max do

if data[j] <>

if i<>pos then

tukardata(data[i],data[pos])

end;

End;

• Procedure desending_Selection;

Var I,j,pos:byte;

Begin

for i:=1 to max-1 do

begin

pos:=I;

for j:=i+1 to max do

if data[pos] <>

if i<>pos then

tukardata(data[i],data[pos])

end;

End;

Exchange Sort

Sangat mirip dengan Bubble Sort

Banyak yang mengatakan Bubble Sort sama dengan Exchange Sort

Pebedaan : 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, begitu seterusnya.

algoritma exchange sort :

Void exchange_sort(int data[]){

For (int i=0; i

For(int j = i+1;j

If(data [i] <>

Tukar(&data[i],&data[j]);

}

}

}

Bubble Sort

Bubble sort adalah membandingkan elemen yang sekarang dengan elemen

yang berikutnya, jika elemen sekarang > elemen berikutnya, maka tukar.

Contoh pengurutan data :

Lankah 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

Langkah 2 :

2 22 10 15 3 8

2 22 10 15 3 8

2 22 10 3 15 8

2 22 10 3 15 8

2 3 22 10 15 8

Langkah 3 :

2 3 22 10 15 8

. 3 22 10 8 15

2 3 22 8 10 15

2 3 8 22 10 15

Langkah 4 :

2 3 8 22 10 15

. 3 8 22 10 15

2 3 8 10 22 15

Langkah 5 :

2 3 8 10 22 15

2 3 8 10 15 22

Terurut :

2 3 8 10 15 22

Algoritma bubble sort :

Procedure tukar (var a,b:word);

Var c:word;

Begin

c:=a;

a:=b;

b:=c;

End;

Pengurutan Ascending : Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar.

Procedure asending_Buble(var data:array; jmldata:integer);

Var I,j:integer;

Begin

for i:=2 to jmldata do

for j:=jmldata downto I do

if data[j]

tukardata(data[j], data[j-1])

End;

Pengurutan Descending: Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar.

Procedure decending_Buble(var data:array; jmldata:integer);

Var I,j:integer;

Begin

for i:=2 to jmldata do

for j:=jmldata downto I do

if data[j] >data{j-1] then

tukardata(data[j], data[j-1])

End;