Searching

LAPORAN PRAKTIKUM

ALGORITMA PEMOGRAMAN 2

Searching (Sequentian dan Binary Seacrh)

Flowchart Binary Search

Oleh:

RATIH

1801301059

Dosen Pengampu :

Veri Julianto, S.Si, M.Si

PROGRAM STUDI TEKNIK INFORMATIKA

POLITEKNIK NEGERI TANAH LAUT

PELAIHARI

2019

1.      Judul Materi

Searching

2.      Kemampuan Akhir Tahap Pembelajaran (KATP)

Mahasiswa dapat menerapkan metode searching dan membedakan metode-metode searching pada bahasa pemrograman C++ secara tepat (C3, A3, P4)

3.       Alat dan Bahan

Alat dan bahan yang diperlukan adalah: Personal Computer (PC)/Laptop, Terminal, dan Codeblocks.

4.      Teori Singkat

Algoritma pencarian (searching algorithm) adalah algoritma yang menerima sebuah argumen kunci dan dengan langkah-langkah tertentu akan mencari argument kunci tersebut pada data yang telah dimiliki. Setelah proses pencarian dilaksanakan, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang dicari ditemukan (successful) atau tidak ditemukan (unsuccessful).

Ada dua macam teknik pencarian yaitu pencarian sekuensial (sequential search) dan pencarian biner (binary search). Perbedaan dari dua teknik ini terletak pada keadaan data. Pencarian sekuensial digunakan apabila data dalam keadaan acak atau tidak terurut. Sebaliknya, pencarian biner digunakan pada data yang sudah dalam keadaan urut.

5.      Pelaksanaan Praktikum

Tahapan pelaksanaan praktikum adalah sebagai berikut.

a.       Tahapan uraian materi, yaitu penjelasan singkat tentang materi Sequential dan Binary search.

b.      Tahapan latihan,

i.        mahasiswa berlatih membuat Algoritma Sequential dan Binary search dalam bentuk flowchart

ii.      mahasiswa berlatih menerapkan sequential search untuk mencari argument kunci pada kasus yang diberikan

iii.    pemberian source code kepada mahasiswa tentang sequential search dalam pemrograman C++ pada codeblocks,

iv.    mahasiswa berlatih menerapkan binary search untuk mencari argument kunci pada kasus yang diberikan

v.      pemberian source code kepada mahasiswa tentang binary search dalam pemrograman C++ pada codeblocks,

c.       Tahapan tindak lanjut, yaitu pemberian tugas kepada mahasiswa.

a.       Sequential Search

i.        Manual

Algoritma pencarian dapat dijelaskan sebagai berikut : pencarian dimulai dari data paling awal, kemudian ditelusuri dengan menaikkan indeks data, apabila data sama dengan kunci pencarian dihentikan dan diberikan nilai pengembalian true, apabila sampai indeks terakhir data tidak ditemukan maka diberikan nilai pengembalian false.

Ilustrasi dari algoritma sequential search adalah sebagai berikut :

Kunci=3

ii.        Program

#include <iostream> using namespace std; int A[]={2,6,3,5,12,14,1,7,20,21,19}; int cari, a, ketemu =0, i; int main() {     cout<<"input data yang dicari   : ";cin>>cari;     a= sizeof(A)/sizeof(A[0]);     for(int i=0; i<a; i++) ///akan menghitung data     {         if (A[i]=cari)///== perbandingan true/falsh         {             ketemu=!ketemu;             break;         }     }     if (ketemu>0)         {             cout<<cari<<" ditemukan"<<endl;         }     else         {             cout<<cari<<" tidak ditemukan"<<endl;         }     return 0; }

iii.        Hasil Running

a.       Binary Search

i.    Program

#include <iostream> #include <conio.h> Using namespace std; int BinarySearch(int Data[], int x, int n) {   int L = 0, R = n-1, m, ketemu = 0;   while((L <= R) && (!ketemu)) {     m = (L + R) / 2;     if(Data[m] == x)      ketemu = !ketemu;     else if (x < Data[m])      R = m - 1;     else      L = m + 1;   }  if(ketemu)   return m+1;  else   return -1; }  int main() {      int Data[]={1,2,3,4,5,6,7,8,9,10};      int n = sizeof(Data);      int cari; cout<<"Masukkan data yang dicari : ";cin>>cari;      int ketemu = BinarySearch(Data, cari, n);      if(ketemu>0)         cout<<"Data ditemukan di posisi : "<<ketemu;     else         cout<<"Data tidak ditemukan";      getch(); }

ii.     Hasil Running

 

Materi Shorting, Bubble Short, Quick Short, dan Marge Short.

SORTING

Pengertian Sorting

Pengurutan (Sorting) merupakan proses pengurutan sekumpulan data dalam suatu    urutan tertentu.

Sorting dipakai untuk:
1.Membantu proses pencarian (searching)
2.Menyelesaikan masalah-masalah kompleks seperti penjadwalan (scheduling), pengolahan basis data, riset operasi, dsb.

Jenis-jenis Shorting :

1. Metode Pemograman Bubble Sort dengan C++

Metode bubble sort, merupakan metode tersederhana untuk melakukan pengurutan data, tetapi memiliki kinerja yang terburuk untuk data yang besar. Pengurutan dilakukan dengan membandingkan sebuah bilangan dengan seluruh bilangan yang terletak sesudah bilangan tersebut. Penukaran dilakukan kalau suatu kriteria dipenuhi.

Sebagai contoh, terdapat kumpulan seperti berikut.
25 57 48 37 12 92 80 33
Contoh proses pengurutan dengan urut naik ditunjukkan pada gambar





Pengurutan tahap pertama




Pengurutan tahap kedua

Jika jumlah data adalah n, maka terjadi n-1 tahap pengurutan. Berarti pada contoh di di atas diperlukan 7 tahap pengurutan. Gambar 11.4 memperlihatkan setelah 7 tahap pengurutan dilakukan.




Keadaan di setiap tahap pengurutan

Implementasikan pengurutan dengan metode buble sort baik dalam algoritma maupun program

Algoritma :
SUBRUTIN bubble_sort(L,n)
      Untuk tahap = 1 s/d n-1
        Untuk j← 0 s/d n-tahap-1
          Jika L[j] > L[j+1] MAKA
            // Lakukan penukaran
            tmp ←L[j]
            L[j] ←L[j+1]
            L[j+1] ←tmp
          AKHIR – JIKA
        AKHIR – UNTUK
      AKHIR – UNTUK
    AKHIR – SUBRUTIN

Implementasi dalam bahasa pemograman C++

#include <iostream.h>
#include <conio.h>
void tampilkan_larik(int data[], int n)
{
int i;
for(i=0;i<n;i++)
cout<<data[i]<<" ";
cout<<"\n";
}

void buble_sort(int data[],int n)
{
int tahap,j,tmp;
for (tahap=1;tahap<n;tahap++)
{
for (j=0;j<n-tahap;j++)
if (data[j]>data[j+1])
{
//tukarkan
tmp=data[j];
data[j]=data[j+1];
data[j+1]=tmp;
}
cout<<"hasil tahap "<<tahap<<" : ";
tampilkan_larik (data,n);
}
}

int main()
{
const jum_data=8;
int i;
int data[]={25,57,48,37,12,92,80,33};

buble_sort(data, jum_data);

//hasil pengurutan
cout<<endl;
cout<<"Hasil Pengurutan: \n";
tampilkan_larik(data,jum_data);
getch();
}

Gambar Program Setelah Dieksekusi :

2. Quick Sort dan Contoh

Quick Sort merupakan salah satu algoritma pengurutan data yang menggunakan teknik membagi  data menjadi partisi-partisi. Metode Quick Sort disebut juga dengan nama partition exchange sort.

Untuk memulai proses pengurutan, pertama-tama sebuah data dipilih dari kelompok data sebagai data pivot. Posisi data pivot dapat dicari dengan menggunakan rumus :

    i  = (indeks awal + indeks akhir) div 2

Kemudian elemen-elemen data akan diatur, sehingga nilai data pivot yang terletak di posisi ke I memenuhi kondisi sebagai berikut :

Semua data di posisi ke 1 sampai dengan ke I-1  lebih kecil atau sama dengan pivot atau data[i]<=pivot.

Semua data di posisi ke I+1 sampai dengan ke N  lebih besar atau sama dengan pivot atau data[i]>=pivot.

Contoh  :

Ada  12 data  sebagai berikut :

indeks     1      2      3    4   5     6     7      8     9    10   11   12

Data        33   99   18    7   5    45   57    25   55   10   40   50

Pos = (1+12) div 2 = 6

Pivot = data[ pos]  = 45

Data 45 terpilih sebagai data pivot. Setelah diatur, maka posisi urutan data sebagai berikut :

indeks     1      2      3    4   5     6     7      8     9    10   11   12

Data        33   25    18   7   5    10   40     45  55   50   57   99

Dimana :

Semua elemen di posisi ke 1 sampai dengan posisi ke 8   lebih kecil atau sama dengan nilai 45.

Semua elemen di posisi ke 9  lebih besar atau sama dengan 45.

Dengan demikian, data tersebut akan terpecah menjadi 2 partisi, satu partisi di sisi kiri 57 dan satu partisi di sisi kanan 57 sebagai berikut :  

                                      [33   25    18   7   5    10   40   ]    45     [55   50   57   99]

Dengan cara yang sama, proses  partisi diulangi lagi untuk masing-masing partisi  baik  di sisi kanan maupun di sisi kanan. Jadi setiap partisi yang diperoleh akan dipartisi lagi hingga diperoleh hasil pengurutan data.

Dalam proses partisi dengan metode quick sort dapat selesaikan  dengan menggunakan prosedur rekursi. Karena proses partisi dengan cara sama selalu diulangi. Proses partisi dibentuk dalam sebuah prosedur atau fungsi dan akan memanggil dirinya sendiri.

Animasi dari proses Quick sort seperti pada gambar dibawah ini :

Kode program pascal untuk mengurutkan data dengan metode quick sort adalah sebagai berikut :

program quicksorting;

uses

crt;

type

Matrix = array[1..100] of integer;

Procedure input(var d:matrix;var n :integer);

var

code,k :integer;

i:string;

begin

  randomize;

  write(' Jumlah data  = ');readln(n);

  for k:=1 to n do

    Begin

      d[k]:=random(100);

      write(d[k], '  ');

    End; writeln;

end;

Procedure tukardata(var a,b : integer);

var t :integer;

begin

    t:=a;a:=b;b:=t;

end;

Procedure cetak(d:matrix;c:integer);

var

i:integer;

begin

   for i:=1 to c do

   write(d[i]:5);

   writeln;

end;

procedure quicksort(var d:matrix; a,b:integer);

var

a1,b1,pivot: integer;

begin

   a1:=a; b1:=b;

   pivot:=d[(a+b) div 2];

   repeat

     while(d[a1]     while(d[b1]>pivot) do dec(b1);

     if (a1<=b1) then

        begin

          tukardata(d[a1],d[b1]);

          inc(a1);

          dec(b1);

        end;

   until (a1>b1);

   cetak(d,b);

   if (a < b1) then quicksort(d, a, b1);

   if (a1 < b ) then quicksort(d,a1, b);

end;

{Program Utama}

var

data :matrix;

n:integer;

begin

clrscr;

  input(data,n);

  writeln('Proses Sorting Data');

  cetak(data,n);

  quicksort(data,1,n);

  writeln;

  writeln('Hasil Sorting Data ');

  cetak(data,n);

  readkey;

end.

Output  program :

3. Marge Short

Algoritma lain yang menggunakan Divide and Conquer dalam pengurutan adalah Merge Sort.

Secara   konseptual,  untuk  sebuah array  berukuran  n,
Merge Sort bekerja sebagai berikut:
1.  Jika  bernilai  0   atau   1,   maka  array  sudah   terurut.

2.   Jika Array tidak terurut, bagi menjadi 2 sub-array dengan ukuran n/2

3. Urutkan setiap sub array. Jika sub array tidak cukup kecil lakukan langkah kedua dengan rekursif

4. Menggabungkan sub array menjadi satu array

Berikut ini implementasi sederhana dari Algoritma Merge Sort dengan C++ dan Tool yang digunakan Code Block 8.02

#include <iostream>

using namespace std;
void merge(int low, int mid, int up);
void mergeSort(int low, int up);
int a[50];
int main()
{
int jumlahBil,i;
cout<<"Masukkan Jumlah element Array"<< endl;
cin>>jumlahBil;
for(int i=0; i<jumlahBil;i++)
{
cout<<"Bilangan ke-"<< i+1 << endl;
cin>>a[i];
}
mergeSort(1,jumlahBil);
for(i=1;i<=jumlahBil;i++)
cout<<a[i]<<"    ";
cout<<endl;
return 0;
}
void merge(int low, int mid, int up)
{
int h, i,j,k;
int b[50];
h = low;
i = low;
j = mid+1;
while((h<=mid)&&(j<=up))
{
if(a[h] < a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=up;k++){
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=up;k++) a[k]=b[k];
}
void mergeSort(int low, int up)
{

int mid;
if(low<up)
{
mid=(low+up)/2;
mergeSort(low,mid);
mergeSort(mid+1,up);
merge(low,mid,up);
}
}




Sumber : https://7seasons.wordpress.com/tag/merge-sort-bubble-short-quick short/