Tidak semua yang saya tulis dalam CERPEN adalah saya :)

Welcome to my Blog... Blog ini mengenai tugas kuliah, cerpen, artikel dan beberapa hal tentang saya dan hobi saya :) boleh COPAS, tapi izin dulu yaa, jangan rendahkan dirimu sebagai pelagiat. Terima kasih :)

Selasa, 29 Mei 2012

Search & sort

Search :
            Pada suatu data seringkali dibutuhkan pembacaan kembali informasi (retrieval information) dengan cara searching. Searching adalah pencarian data dengan cara menelusuri data-data tersebut.  Tempat pencarian data dapat berupa array dalam memori, bisa juga pada file pada external storage.

1.      Linier search

            Linier Search adalah metode untuk menemukan nilai tertentu dalam daftar, yang terdiri dari pengecekan setiap satu dari unsur-unsurnya, satu persatu dan berurutan, sampai salah satu yang diinginkan ditemukan.

Contoh Program Linier Search :

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void main(){
int arr[100],i,element,no;
clrscr();
printf("\nMasukan jumlah data : " );
scanf("%d", &no);
for(i=0;i<no;i++){
printf("\ndata ke [%d] : ", i+1);
scanf("%d",&arr[i]);
}
printf("\nMasukan data yang akan dicari     : ");
scanf("%d", &element);
for(i=0;i<no;i++){
if(arr[i] == element){
printf("\nData yang dicari ada di posisi ke : %d",i+1);
getch();
exit(1);
}
}
printf("\nElement not found");
getch();
}
  
2.      Binary search

            Dalam Pencarian Binary Search, Data yang ada harus diurutkan terlebih dahulu berdasarkan suatu urutan tertentu yang dijadikan kunci pencarian. Adalah teknik pencarian data dalam dengan cara membagi data menjadi dua bagian setiap kali terjadi proses pencarian.
            Pencarian secara biner, digunakan ketika sebuah komputer harus mencari posisi sebuah simbol dalam daftar urut. Komputer akan mencari simbol dari tengah daftar sampai data terakhir, dan membandingkannya dengan simbol yang sedang dicari. Apabila simbol tersebut sudah ditemukan, pencarian pada setengah daftar sisanya akan dihentikan.

Contoh Program Binary Search :

#include<iostream.h>
#include<conio.h>

main()
{
clrscr();
//deklarasi variabel
int a[10], i,j,k,tkr,top,bottom,middle,tm;
//proses penginputan data
for(i=0;i<10;i++)
{
cout<<"Data ke ["<<i<<"] = ";
cin>>a[i];
}
cout<<endl;
cout<<"Masukkan data yang akan anda cari : ";
cin>>k;
//proses pengurutan data
for(i=0;i<10;i++)
{
for(j=i+1;j<10;j++)
{
if (a[i]>a[j])
{
tkr=a[i];
a[i]=a[j];
a[j]=tkr;
}
}
}
//proses pencarian data
tm=0;
top=9;
bottom=0;
while(top>=bottom)
{
middle=(top+bottom)/2;
if(a[middle]==k)
{
tm++;
}
if(a[middle]<k)
{
bottom=middle+1;
}
else
{
top=middle-1;
}
}
if (tm>0)
{
cout<<"Data "<<k<<" yang dicari ada dalam array ";
}
//jika tidak ditemukan
else
{
cout<<"Data tidak ditemukan dalam array";
}
getch();
}


3.      Fibonancci search

            Deret Fibonacci adalah sebuah deret yang untuk suku pertama dan kedua bernilai 0 dan 1, sedangkan untuk suku ketiga dan seterusnya merupakan penjumlahan 2 suku sebelummnya, misal untuk ke-3 adalah (0+1) = 1, suku ke-4 adalah (1+1) = 2, dst.

Contoh Program Fibonancci Search :

#include<iostream.h>
#include<stdio.h>
#include<conio.h>

int fibonacci(int n)
{
if(n==1)
return(0);
else if(n==2)
return(1);
else
return (fibonacci(n-1)+fibonacci(n-2));
}

int main()
{
clrscr();
int n;
cout<<"\nBerapa jumlah bilangan fibonacci yang ingin anda tampilkan: ";cin>>n;
for(int i=1;i<=n;i++)
cout<<fibonacci(i)<<" ";
cout<<endl;
getch();
}


Sort :
Pengurutan data dalam struktur data sangat penting terutama untuk data yang beripe 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

1.      Bubble Sort
Bubble Sort adalah Cara pengurutan data atau file dengan cara saling menukar tempat dalam urutan, mirip dengan gelembung dalam air. Metode ini adalah cara terbaik untuk mengurutkan data/file dengan jumlah sedikit. Untuk file yang lebih besar terdapat metode lainnya.

2.      Selection Sort
Algoritma ini mudah diterjemahkan ke dalam program computer tetapi memiliki kekurangan yaitu sort dengan menggunakan metode Seleksi membutuhkan ruang di memori untuk meyimpan 2 daftar lengkap.

Jika memiliki satu daftar nama dan meletakkan dalam urutan berdasarkan huruf bisa menggunakan pemdekatan umum sebagai berikut :
a.      Temukan atau cari nama yang pertama kali datang dalam urutan huruf dan tulis di sheet kedua.
b.      Tandai nama yang keluar dari daftar asli.
c.       Lanjutkan perputaran ini sampai semua nama di daftar semula telah di coret dan ditulis di daftar kedua dimana di bagian daftar yang kedua ini nama-nama sudah terurut berdasarkan huruf.

3.      Quick Sort
Ide dasar quick sort (pengurutan cepat) yaitu membandingkan hasil setiap perbandingan sebagai penunjuk ke perbandinga berikutnya. Selama perbandingan, kunci dipertukarkan setelah dilengkapi, daftar kemudian dibagi menjadi nilai kunci pada satu partisi (tidak terurut) semuanya kurang dari nilai kunci yang dipilih dan nilai kunci di partisi yang lain semuanya lebih besar dari nilai kunci.
Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama), dan yang telah diurutkan (meja kedua). Elemen pertama yang diambil dari bagian array yang belum diurutkan dan kemudian diletakkan pada posisinya sesuai dengan bagian lain dari array yang telah diurutkan. langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.

4.      Insertion sort
Insertion sort merupakan algoritma sorting sederhana yang relatif efisien untuk daftar kecil dan sebagian besar daftar-disortir, dan sering digunakan sebagai bagian dari algoritma yang lebih canggih. Ia bekerja dengan mengambil unsur-unsur dari satu daftar dengan satu dan memasukkan mereka dalam posisi yang benar mereka ke dalam daftar diurutkan baru. Pada array, daftar baru dan elemen-elemen yang tersisa dapat berbagi ruang array, tetapi penyisipan mahal, membutuhkan menggeser semua elemen-elemen berikut alih oleh satu. Jenis penyisipan bekerja seperti dengan namanya - itu memasukkan setiap barang ke tempat yang tepat dalam daftar akhir. Pelaksanaan sederhana ini membutuhkan struktur daftar dua - daftar sumber dan daftar dimana item diurutkan dimasukkan. Untuk menghemat memori, sebagian besar implementasi menggunakan semacam di tempat yang bekerja dengan menggerakkan item saat masa lalu item sudah disortir dan berulang kali bertukar dengan item sebelumnya sampai di tempat. Shell sort (lihat di bawah) adalah varian dari insertion sort yang lebih efisien untuk daftar yang lebih besar. Metode ini jauh lebih efisien daripada bubble sort, walaupun memiliki kendala lebih.

contoh program sorting (Selection sort, Bubble Sort, Exchange Sort,  Insertion Sort, Quick Sort). digabung jadi satu program :

#include <iostream.h>
#include <conio.h>

int data[100],data2[100];
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-1;j>=i;j-1)
{
if(data[j]<data[j-1]) tukar(j,j-1);
}
}
cout<<"bubble sort selesai!"<<endl;
}

void exchange_sort()
{
for (int i=0; i<n-1; i++)
{
for(int j = (i+1); j<n; j++)
{
if (data [i] > data[j]) tukar(i,j);
}
}
cout<<"exchange sort selesai!"<<endl;
}

void selection_sort()
{
int pos,i,j;
for(i=0;i<n-1;i++)
{
pos = i;
for(j = i+1;j<n;j++)
{
if(data[j] < data[pos]) pos = j;
}
if(pos != i) tukar(pos,i);
}
cout<<"selection sort selesai!"<<endl;
}

void insertion_sort()
{
int temp,i,j;
for(i=1;i<n;i++)
{
temp = data[i];
j = i -1;
while(data[j]>temp && j>=0)
{
data[j+1] = data[j];
j-1;
}
data[j+1] = temp;
}
cout<<"insertion sort selesai!"<<endl;
}

void QuickSort(int L, int R) //the best sort i’ve ever had :)
{
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);
}

void Input()
{
cout<<"Masukkan jumlah data = "; cin>>n;
for(int i=0;i<n;i++)
{
cout<<"Masukkan data ke-"<<(i+1)<<" = "; cin>>data[i];
data2[i] = data[i];
}
}

void Tampil()
{
cout<<"Data : "<<endl;
for(int i=0;i<n;i++)
{
cout<<data[i]<<" ";
}
cout<<endl;
}

void AcakLagi()
{
for(int i=0;i<n;i++)
{
data[i] = data2[i];
}
cout<<"Data sudah teracak!"<<endl;
}

void main()
{
int pil;
clrscr();
do
{
clrscr();
cout<<"Program Sorting Komplit!!!"<<endl;
cout<<"*********************************************"<<endl;
cout<<" 1. Input Data"<<endl;
cout<<" 2. Bubble Sort"<<endl;
cout<<" 3. Exchange Sort"<<endl;
cout<<" 4. Selection Sort"<<endl;
cout<<" 5. Insertion Sort"<<endl;
cout<<" 6. Quick Sort"<<endl;
cout<<" 7. Tampilkan Data"<<endl;
cout<<" 8. Acak Data"<<endl;
cout<<" 9. Exit"<<endl;
cout<<"    Pilihan Anda = ";  cin>>pil;
switch(pil)
{
case 1:Input(); break;
case 2:bubble_sort(); break;
case 3:exchange_sort(); break;
case 4:selection_sort(); break;
case 5:insertion_sort(); break;
case 6:QuickSort(0,n-1);
cout<<"quick sort selesai!"<<endl;
break;
case 7:Tampil(); break;
case 8:AcakLagi(); break;
}
getch();
}while(pil!=9);
}


  1. Merge sort
            Merge sort mengambil keuntungan dari kemudahan penggabungan sudah daftar diurutkan ke daftar diurutkan baru. Dimulai dengan membandingkan setiap dua elemen (yaitu 1 dengan 2, kemudian 3 dengan 4 ...) dan swapping mereka jika yang pertama datang setelah kedua. Kemudian masing-masing menggabungkan daftar yang dihasilkan dua menjadi daftar empat, kemudian menggabungkan daftar tersebut empat, dan seterusnya, sampai akhirnya dua daftar digabungkan ke dalam daftar diurutkan akhir. Dari algoritma yang dijelaskan di sini, ini adalah yang pertama yang baik daftar skala yang sangat besar.

Contoh Program Merge sort :

#include<iostream.h>
#include<conio.h>

void mergesort(int *,int,int);
void merge(int *,int,int,int);
int a[20],i,n,b[20];

main()
{
clrscr();
cout <<"\nMasukan data berupa angka : ";
cin >> n;
cout <<"Masukan data :\n";
for(i=0;i<n;i++)
cin >> a[i];
mergesort(a,0,n-1);
cout <<" angka setelah sort ";
for(i=0;i<n;i++)
cout << a[i] << " ";
getch();
}

void mergesort(int a[],int i,int j)
{
   int mid;
   if(i<j)
   {
      mid=(i+j)/2;
      mergesort(a,i,mid);
      mergesort(a,mid+1,j);
      merge(a,i,mid,j);
   }
}
void merge(int a[],int low,int mid ,int high)
{
   int h,i,j,k;
   h=low;
   i=low;
    j=mid+1;
   while(h<=mid && j<=high)
   {
      if(a[h]<=a[j])
             b[i]=a[h++];
      else
             b[i]=a[j++];
      i++;
   }

   if( h > mid)
      for(k=j;k<=high;k++)
            b[i++]=a[k];
   else
      for(k=h;k<=mid;k++)
             b[i++]=a[k];

   cout <<"\n";
   for(k=low;k<=high;k++)
   {  a[k]=b[k];
     cout << a[k] <<" ";
   }
}


  1. Heap sort
            Heapsort adalah versi yang jauh lebih efisien selection sort. Ia juga bekerja dengan menentukan elemen (atau terkecil) terbesar daftar, menempatkan bahwa pada akhir (atau awal) dari daftar, kemudian melanjutkan dengan sisa daftar, t...api menyelesaikan tugas ini secara efisien dengan menggunakan struktur data yang disebut tumpukan, tipe khusus pohon biner. Setelah daftar data telah dibuat menjadi tumpukan, simpul akar dijamin menjadi elemen terbesar. Ketika dipindahkan dan ditempatkan di akhir daftar, tumpukan adalah ulang sehingga elemen terbesar yang tersisa bergerak ke akar. Menggunakan heap, menemukan elemen terbesar berikutnya membutuhkan O (log n) waktu, bukan O (n) untuk linear scan di selection sort sederhana. Hal ini memungkinkan heapsort untuk menjalankan dalam O (n log n) waktu.