Selasa, 04 Januari 2011

program sorting

#include
#include

int data[10],data2[10];
int n;

void tukar(int a, int b)
{
int t;
t = data[b];
data[b] = data[a];
data[a] = t;
}

void bubble_sort()
{
for(int i=1;i<=n;i++) { for(int j=n; j>=i; j--)
{
if(data[j] < data[j-1]) tukar(j,j-1); } } } void main() { cout<<"===PROGRAM BUBBLE SORT==="<>n;
for(int i=1;i<=n;i++) { cout<<"Masukkan data ke "<>data[i];
data2[i]=data[i];
}

bubble_sort();

cout<<"\n\n"; //tampilkan data cout<<"Data Setelah di Sort : "; for(int i=1; i<=n; i++) { cout<<" "temp && j>=0)
{
data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
}
void main()
{
cout<<"===PROGRAM INSERTION SORT==="<>n;
for(int i=1;i<=n;i++) { cout<<"Masukkan data ke "<>data[i];
data2[i]=data[i];
}

insertion_sort();
cout<<"\n\n";
//tampilkan data
cout<<"Data Setelah di Sort : ";
for(int i=1; i<=n; i++)
{
cout<<" "< }
cout<<"\n\nSorting Selesai";
getch();
}

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!” else cout<<”Data Tidak ada!”

Algoritma brute force (di dalam pencarian string)

Algoritma brute force merupakan algoritma pencocokan string yang ditulis tanpa memikirkan peningkatan performa. Algoritma ini sangat jarang dipakai dalam praktek, namun berguna dalam studi pembanding dan studi-studi lainnya.
[sunting] Cara kerja

Secara sistematis, langkah-langkah yang dilakukan algoritma brute force pada saat mencocokkan string adalah:

1. Algoritma brute force mulai mencocokkan pattern pada awal teks.
2. Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
1. Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
2. Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.
3. Algoritma kemudian terus menggeser pattern sebesar satu ke kanan, dan mengulangi langkah ke-2 sampai pattern berada di ujung teks.

Berikut adalah Algoritma brute force yang sedang bekerja mencari string:

Algoritma brute force yang sedang bekerja mencari string.
[sunting] Pseudocode

Pseudocode algoritma brute force ini:

procedure BruteForceSearch(
input m, n : integer,
input P : array[0..n-1] of char,
input T : array[0..m-1] of char,
output ketemu : array[0..m-1] of boolean
)

Deklarasi:
i, j: integer 

Algoritma:
for (i:=0 to m-n) do
j:=0
while (j < n and T[i+j] = P[j]) do j:=j+1 endwhile if(j >= n) then
ketemu[i]:=true;
endif 
endfor

ALGORITMA PENCARIAN BINER

Pencarian Biner (Binary Search) dilakukan untuk :
   memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.
   Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).
   Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.

ALGORITMA  

Kamus
      Const N : integer = 8  { misalkan jumlah elemen array maksimum = 8 }
      Type A = array [ 1 ..... N ] of integer
      Cari, BatasAtas, BatasBawah, Tengah : Integer
      Ketemu : boolean
ALGORITMA
         Input (cari) { meminta nilai data yang akan dicari}
         BatasAtas     ¬  1 { indeks array dimulai dari 1 }
         BatasBawah     ¬   N    
         Ketemu   ¬  False
         While (BatasAtas < BatasBawah)and (not ketemu) do
               Tengah ¬   (BatasAtas  + BatasBawah) div 2
               If A [Tengah] = cari then
                  Ketemu ¬ true
                           Else
                                 If ( A [Tengah]  < cari ) then { cari di bagian kanan }
                                       BatasAtas ¬Tengah + 1
                                 Else
                                       BatasBawah ¬Tengah – 1 { cari di bagian kiri }
                                 Endif
                           Endif
         EndWhile
         If (ketemu) then
                     Output ( ‘Data berada di index nomor’, Tengah )
         Else     Output ( ‘Data tidak ditemukan’ )
         Endif





Contoh Nilai-Nilai data yang sudah terurut :

A
2
5
8
12
15
25
37
57

1
2
3
3
5
6
7
8

Kasus 1  : cari = 12

Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 8) div 2 = 4
                           A [Tengah] = A [4] = 12, berarti loop pertama data langsung ditemukan

Kasus 2  : cari = 15

Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 +  8) div 2 = 4
                           A [Tengah] = A [4] = 12 < cari = 15, berarti BatasAtas = Tengah + 1 = 4 + 1 = 5
Loop kedua :     Tengah = (BatasAtas + BatasBawah) div 2 = (5 +  8) div 2 = 6
                           A [Tengah] = A [6] = 25 > cari = 15, berarti BatasBawah = Tengah - 1 = 6 - 1 = 5
Loop ketiga :     Tengah = (BatasAtas + BatasBawah) div 2 = (5 +  5) div 2 = 5
                           A [Tengah] = A [5] = 15, berarti  setelah loop ketiga, data ditemukan

Kasus 3  : cari = 10

Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 +  8) div 2 = 4
                           A [Tengah] = A [4] = 12 > cari = 10, berarti BatasBawah = Tengah - 1 = 4 - 1 = 3
Loop kedua :     Tengah = (BatasAtas + BatasBawah) div 2 = (1 +  3) div 2 = 2
                           A [Tengah] = A [2] = 5 < cari = 10, berarti BatasAtas = Tengah + 1 = 2 + 1 = 3
Loop ketiga :     Tengah = (BatasAtas + BatasBawah) div 2 = (3 +  3) div 2 = 3
                           A [Tengah] = A [3] = 8, berarti  setelah loop ketiga, data tidak ditemukan

Untuk jumlah data sebanyak n, maka proses pembandingan maksimal sebanyak ( log n ) kali. Untuk contoh di atas, jumlah data 8, maka proses pembandingan maksimal sebanyak 3 kali.