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 :
Selasa, 30 Juni 2009
Sequential Search
Sequential Search adalah membandingkan data-data yang ada dalam kumpulan tersebut yang mulai dari elemen pertama sampai elemen ditemukan, atau sampai elemen terakhir.
Kesimpulan dari kode program di atas, Secara umum pencarian beruntun dan kinerja lambat yang di karenakan danya proses perulangan di dalam program tersebut. Bayangkan jika ada lebih dari 100.000 data itu artinya akan ada 100.000 kali perulangan apabila dalam satu kali proses perulangan membutuhkan waktu 0,01 detik maka akan membutuhkan waktu sekitar 1000 detik karena hal itulah metode ini tidak di gunakan untuk mencari data yang besar. contoh program:
kode program Sequential Search :
#include
#include
int main(int argc, char* argv[])
{
int X,i,k;
int L[10] = {20,15,22,14,12,10,24,19,18,16};
printf("Data yang akan dicari = ");
scanf("%d",&X);
k = 0;
for(i=0;i<=9;i++)
{
if(L[i]==X)
{
printf("Data ditemukan di elemen %d \n",i);
k++;
}
}
if(k==0)
{
printf("Data tidak ditemukan \n");
}
printf("Jumlah data yang ditemukan = %d",k);
getch();
return 0;
}
Kesimpulan dari kode program di atas, Secara umum pencarian beruntun dan kinerja lambat yang di karenakan danya proses perulangan di dalam program tersebut. Bayangkan jika ada lebih dari 100.000 data itu artinya akan ada 100.000 kali perulangan apabila dalam satu kali proses perulangan membutuhkan waktu 0,01 detik maka akan membutuhkan waktu sekitar 1000 detik karena hal itulah metode ini tidak di gunakan untuk mencari data yang besar. contoh program:
kode program Sequential Search :
#include
#include
int main(int argc, char* argv[])
{
int X,i,k;
int L[10] = {20,15,22,14,12,10,24,19,18,16};
printf("Data yang akan dicari = ");
scanf("%d",&X);
k = 0;
for(i=0;i<=9;i++)
{
if(L[i]==X)
{
printf("Data ditemukan di elemen %d \n",i);
k++;
}
}
if(k==0)
{
printf("Data tidak ditemukan \n");
}
printf("Jumlah data yang ditemukan = %d",k);
getch();
return 0;
}
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 ( Shorting)
Ø 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
–Metode sorting paling mudah, namun paling lambat dibandingkan dengan yang lain.
–Bubble sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya.
–Bisa dilakukan baik dari awal array maupun akhir array.
–Proses yang berlangsung, jika:
# Ascending: jika elemen sekarang lebih besar daripada elemen berikutnya, maka kedua elemen tersebut ditukar.
# Descending: jika elemen sekarang lebih kecil daripada elemen berikutnya, maka kedua elemen tersebut ditukar.
–Proses penukaran ini akan terus dilakukan hingga seluruh array telah diperiksa.
–Contoh fungsi bubble sort:
//Bubble Sort
void bubble (int a[], int n) {
int i,j;
for (i=n;i>=1;i–)
{
for (j=2;j
{
if(a[j-1]>a[j])
tukar (a,j-1,j);
}
}
}
Contoh untuk mengurutkan data 34,43,65,90
Pada iterasi i=0:j=13: tukar 56-37 menjadi 34,43,65,90
j=12: tidak ada penukaran 34,43,65,23,90 j= 3: tukar 65-23 menjadi 34,43,23,65,90
j= 2: tukar 43-23 menjadi 34,23,43,65,90j= 1: tukar 34-23 menjadi 23,34,43,65,90
Jika Bobble Sort dalam setiap iterasi melakukan loop-for penukaran ke satu arah, Shaker Sort (suatu variant dari Bubble Sort) melakukan loop-for penukaran dengan arah bolak-balik dengan batas loop-for kiri dan kanan semakin menyempit.
sangat mirip dengan bubble sort, perbedaannya hanya dalam hal bagaimana membandingkan antar elemennya
exchange sort membandingkan suatu elemen dengan elemen lainnya dalam array tsb, dan melakukan pertukaran elemen jika perlu, jadi ada elemen yang selalu menjadi elemen pusat ( pivot )
contoh program :
void exchange_sort ( int data [ ] )
{
for ( int i=0 ; i
{
for ( int j=i+1 ; j
{
if ( data[ i ] < style="">
}
}
:: Kombinasi sorting dan searching.
:: Metode sorting ini menggunakan ide menemukan data dengan nilai terbesar dalam array lalumemindahkannya ke bagian akhir array ( jika array harus dalam urutan dari kecil ke besar ). Jikaterbesar sudah berada di posisi yang benar, kita bisa menerapkan hal yang sama untuk data yang tersisa lainnya. Yaitu, menemukan data terbesar berikutnya dan memindahkan ke bagian akhir
:: Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses. data
:: Contoh fungsi selection sort :
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) ;
:: Metode sorting ini bisa diterapkan dalam menjaga array dalam urutan tertentu. Misalkan kita memiliki array yang telah tersortir dan kita ingin memasukkan sebuah data ke dalam array. Jika kita ingin memastikan bahwa array yang telah berubah tersebut masih tetap dalam urutan tertentu, maka data baru harus dimasukkan dalam posisi tertentu yang tepat, misalnya semua data yang memiliki nilai lebih kecil berada sebelumnya dan data yang lebih besar berada di posisi sesudahnya. Ini berarti memindahkan setiap data yang lebih besar satu elemen ke kanan, sehingga terbentuk sebuah ruang kosong untuk elemen baru ini
:: Misal ascending : pengurutan dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang lebih kecil, maka akan dimasukkan di posisi yang seharusnya.
:: Pada penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang.
:: Contoh program insertion sort :
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 ;
}
:: Merupakan metode sorting yang paling cepat ( saat ini tercepat ).
:: Quick sort adalah sebuah algoritma rekursif
:: Algoritma Quicksort didasarkan pada sebuah ide yang sederhana : Diberikan sebuah
array, pilih data manapun dari array. Data yang dipilih tersebut selanjutnya kita sebut
pivot. ( Dalam praktek kali ini, kita akan gunakan data pertama dari array ) Pindah semua data yang lebih kecil dari pivot ke bagian awal list, dan pindahkan semua data yang lebih besar dari pivot ke akhir dari list. Sekarang, taruh pivot diantara dua kumpulan data tadi. Posisi pivot tersebutsudah tidak akan dipindah-pindah lagi. Kita sebut prosedur tersebut QuicksortStep
:: QuicksortStep tidak rekursif, ia hanya digunakan sebagai subroutine oleh Quicksort.
Dengan subroutine QuicksortStep ini, Quicksort menjadi mudah. Algoritma Quicksort
70 untuk melakukan sorting pada sebuah array menerapkan QuicksortStep pada array,
kemudian menerapkan Quicksort secara rekursif pada data yang berada di sebelah kiri
dan sebelah kanan pivot
:: contoh program :
void QuickSort ( int L,int R )
{
int I , j ;
int mid ;
i = L ;
j = R ;
mid = data[ (L+R) / 2] ;
do
{
while( data[ I ] <>
while( data[ j ] > mid ) j--;
if( i <=j )
{
tukar( i,j );
i++;
j--;
}
}
while( i
if( L <>
if( i > R ) QuickSort( i,R );
}
Selasa, 16 Juni 2009
pahLawaN beRtoPenG,,
HiduP Tu baGaikaN warna,,KadanG hitaM gelap daN kadaNg putiH meMpesoNa,,
Jadi semaSih kaU biSa meniKmaTi hidUp iNi,niKmatiLah seBaiK mungKin,,
peRbanyAk pahaLa daN kuRangi dOza,,
GooD LucK frieNd'S,,
GodbLesS yOu,,
Minggu, 14 Juni 2009
Lupakan Aku Dan Semua Kenangan Kita
Indahnya sinar bintang dimalam hari
Mungkin takkan pernah seindah manis senyummu
Begitu juga rasa cintaku
Yang takkan pernah hilang hingga akhir masa
namun mengapa kini kau tega
menghianati ketulusan cintaku
Jika memang kau tak sayang tolong katakan
Agar kutak lagi mengharap cintamu
Lupakan aku dan semua kenangan kita
Pergila engkau bersama dirinya
Seorang yang kau cintai melebihi diriku
Agar kau bahagia tuk slama lamanya
Mungkin takkan pernah seindah manis senyummu
Begitu juga rasa cintaku
Yang takkan pernah hilang hingga akhir masa
namun mengapa kini kau tega
menghianati ketulusan cintaku
Jika memang kau tak sayang tolong katakan
Agar kutak lagi mengharap cintamu
Lupakan aku dan semua kenangan kita
Pergila engkau bersama dirinya
Seorang yang kau cintai melebihi diriku
Agar kau bahagia tuk slama lamanya
Langganan:
Postingan (Atom)