How To Solve It By Computer (Algorithm 5.7 Binary Search)

Bismillahirohmanirrohim
Assalamualikum w.w,

Berikut ini adalah materi dari SEARCING AND SORTING. Program yang dibuat yaitu tentang 
E-Book (How To Solve It By Computer) = Algorithm 5.7 Binary Search.

Algoritma :

Pencarian pada data yang telah terurut menunjukkan kinerja yang lebih baik daripada pada data yang masih acak, hal ini karena dapat segera diketahui bahwa x tidak terdapat dalam larik bila ditemukan elemen yang lebih besar dari x.
Binary searching atau biasa disebut pencarian bagi dua merupakan metode pencarian yang paling efisien untuk data yang telah terurut. Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat.
Langkah-langkah pencarian bagi dua untuk data yang telah terurut secara ascending:
1. Bagi dua elemen larik yang telah terurut secara ascending, dengan cara menentukan elemen awal pencarian, elemen akhir pencarian dan elemen tengahnya.
- elemen awal pencarain (lo) = 1
- elemen akhir pencarain (hi) = n
- elemen tengah = (lo + hi) div 2

Misalnya terdapat larik L dengan 9 elemen yang telah terurut secara ascending seperti dibawah ini, maka kita akan menentukan elemen awal, akhir dan tengah pencariannya.

3
6 7 9 10
15 20 30 45

Lo = 1
Hi = 9
Mid = ( 1 + 9 ) div 2 = 5
2. Jika elemen yang dicari ada pada elemen di mid, maka ketemu.
3. Jika elemen yang ada di mid > elemen yang dicari, maka hi berubah
Hi = mid - 1
4. Jika elemen yang ada di mid < elemen yang dicari, maka lo berubah Lo = mid + 1 5. Ulangi langkah-langkah tersebut sampai data yang dicari ditemukan atau sampai elemen telah habis dibagi. Contoh: 3 6 7 9 10 15 20 30 45 Misalnya data yang dicari (x) = 7 1. lo = 1 hi = 9 mid = (1 + 9) div 2 = 5 L[5] = 10 L[mid] > x, maka hi berubah
2. hi = mid -1 = 5 – 1 = 4
lo = 1
mid = ( 1 + 4 ) div 2 = 2
L[2] = 6
L[mid] < x, maka lo berubah 3. lo = mid +1 = 2 + 1 = 3 hi = 4 mid = ( 3 + 4 ) div 2 = 3 L[3] = 7 L[mid] = x, maka data ditemukan Pseudocode Pencarian bagi dua: Algoritma bin_searching; Var lo,hi,mid,n,x,idx :integer; ketemu : boolean; L : array [1..100] of integer; Begin {misalnya telah terdapat sekumpulan data yng tersimpan di dalam larik L} lo ß 1; hi ß n; ketemu ß false; while (not ketemu) and (lo <= hi) do midß (lo + hi ) div 2; If L[mid] = x then ketemu ß true Else If ( L[mid] > x ) then
lo ß mid + 1
Else
hi ß mid – 1;
End if
End if
End while
If (ketemu) then
Idx ß mid
Else
Idx ß -1;
End if
End.

Alhamdulillah

Selamat mencoba dan semoga bermanfaat :)

Wassalamualikum w.w.

Read More

How To Solve It By Computer ( Algorithm 5.4 Sorting By Insertion)

Bismillahirohmanirrohim
Assalamualikum w.w,

Berikut ini adalah materi dari SEARCING AND SORTING. Program yang dibuat yaitu tentang E-Book (How To Solve It By Computer) = Algorithm 5.4 Sorting By Insertion. 

Algoritma :

1. membangun sebuah array [1 .. n] elemen n.
2. menemukan minimum dan meletakkannya di tempat untuk bertindak sebagai sentinel :
3. sementara masih ada unsur-unsur yang akan dimasukkan di bagian memerintahkan melakukan
a.Pilih x elemen berikutnya untuk dimasukkan
b.sementara x kurang dari sebelumnya unsur melakukan
c.insert x pada posisi saat ini

for i:=2 to n do

begin {search for x's position then insert it}

j:=1; x:=a[i];

while x>a[j] do j:=j+1

for k:= i down to j+1 do a[k]:= a[k-1];

a[j]:=x

end

Program C++ :

#include <iostream.h>

void main(){
int data[100];
int a,b,c,d,x;
int temp;


cout<<"PROGRAM SORTING DATA "<<endl;
cout<<"---------------------------------------------"<<endl;
cout<<"Masukkan jumlah data : ? ";cin>>x;


for(d=1;d<=x;d++)
{
cout<<"Data ke-"<<d<<" = ";cin>>data[d];
}
cout<<"\nData Sebelum Diurutkan \n";
for(d=1;d<=x;d++){
cout<<"\t"<<data[d];
}
for(a=0;a<x;a++){
for(b=0;b<x;b++)
if(data[b]>= data[b+1])
{
temp=data[b];
data[b]=data[b+1];
data[b+1]=temp;
}
}
cout<<"\n\nData setelah diurutkan :\n";
for(c=0;c<x;c++)
cout<<"\t"<<data[c];
cout<<"\n\n---------------------------------------------"<<endl
}

 system("PAUSE");

    return EXIT_SUCCESS;

}

Alhamdulillah

Selamat mencoba dan semoga bermanfaat :)

Wassalamualikum w.w.

Read More

How To Solve It By Computer ( Algorithm 5.3 Sorting By Exchange)

Bismillahirohmanirrohim
Assalamualikum w.w,

Berikut ini adalah materi dari SEARCING AND SORTING. Program yang dibuat yaitu tentang E-Book (How To Solve It By Computer) = Algorithm 5.3 Sorting By Exchange. 

Soal

Diberikan urutan yang tidak beraturan dari kumpulan nilai n gunakan urutan dengan emnggunakan sorting by exchange

Penyelesaian :

Bubble Sort (Gelembung) merupakan metode pertukaran yang alur logikanya mirip dengan gelembung yaitu dengan cara membandingkan indeks Array yang pertama dengan indeks Array berikutnya secara terus menerus dan bergantian. Namun cara ini kurang efektif karena meskipun data sudah terurut proses perulangan yang terjadi akan terus berlangsung sampai batas perulangan itu berakhir. Ini adalah contoh alur alogaritmanya dalam kode program.

for (c=0; c<7; c++)
{ for (x=0; x<7; x++)
{if (menu[x]menu[x+1])
{term=menu[x];
menu[x]=menu[x+1];
menu[x+1]=term;
}
else {
menu[x]=menu[x];
}}}

Selection Sort (Maksimum/Minimum) merupakan metode pertukaran yang mencari nilai Maksimum/Minimum sekelompok data array yang nantinya nilai yang paling ujung akan diisolasikan dan tidak disertakan pada proses selanjutnya. Perhatikan contoh code berikut ini.

for(y=0; y<9; y++)
{max=0;
for (x=1; x<=b; x++)
{ if (A[x]>A[max])
{
max=x;
} }
if (A[max]>A[b])
{ term=A[b];
A[b]=A[max];
A[max]=term;
b--;
} else
{
b--;
}}


Insertion Sort (Sisip) meripakan metode pengurutan dengan cara menyisipkan nilai pada array pada posisi yang tepat. Untuk lebih jelasnya silakan lihat code dibawah ini.

for (k=1; k<9; k++)
{
term=L[k];
j=k-1;
while (term<=L[j])
{
L[j+1]=L[j];
j--;
}
if ((term >= L[j]) || (j=1))
{
L[j+1]=term;
}
else
{
L[j+1]=L[j];
L[j]=term;
}

Alhamdulillah

Selamat mencoba dan semoga bermanfaat :)

Wassalamualikum w.w.

Read More

How To Solve It By Computer ( Algorithm 5.2 Sorting By Selection)

Bismillahirohmanirrohim
Assalamualikum w.w,

Berikut ini adalah materi dari SEARCING AND SORTING. Program yang dibuat yaitu tentang E-Book (How To Solve It By Computer) = Algorithm 5.2 Sorting By Selection.

Algoritma:

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 :

Temukan atau cari nama yang pertama kali datang dalam urutan huruf dan tulis di sheet kedua

Tandai nama yang keluar dari daftar asli

 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.

Program C++ :

#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–)
{
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–;
}
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);
}

Alhamdulillah

Selamat mencoba dan semoga bermanfaat :)

Wassalamualikum w.w.

Read More

How To Solve It By Computer (Algorithm 5.1 The Two-Way Merge)

Bismillahirohmanirrohim
Assalamualikum w.w,

Berikut ini adalah materi dari SEARCING AND SORTING. Program yang dibuat yaitu tentang E-Book (How To Solve It By Computer) = Algorithm 5.1 The Two-Way Merge. 

Algoritma :

        if a[m]<b[n] then a[m+1]:=b[n+1]:=a[m];
            i:=1;
            j:=1;
            nm:= n+m;
       for k:= 1 to nm dobegin {merge next element }
            if a[i]<b[j] thenbeginc[k]:=a[i];
                 i:=i+1end elsebeginc[k]:=b[j];
                 j:=j+1end
       end

Program dengan C++ :

#include <iostream>
#include <cstdlib>

using namespace std;

int data[100];

void mergeSort(int awal, int mid, int akhir){
         cout<<endl;
int temp[100], tempAwal = awal, tempMid = mid, i = 0;

while(tempAwal < mid && tempMid < akhir){
        if(data[tempAwal] < data[tempMid])
               temp[i] = data[tempAwal],tempAwal++;
        else
              temp[i] = data[tempMid],tempMid++;
              i++;
}
while(tempAwal < mid) //kalau masih ada yang sisa
         temp[i] = data[tempAwal],tempAwal++,i++;
         while(tempMid < akhir)
         temp[i] = data[tempMid],tempMid++,i++;
for(int j=0,k=awal;j<i,k<akhir;j++,k++) //mengembalikan ke array semula, tapi
cout<<data[k]<<' '<<temp[j]<<endl, data[k] = temp[j]; //sudah urut
}

void merge(int awal, int akhir) //membagi data secara rekursif{
      if(akhir-awal != 1){
          int mid = (awal+akhir)/2;
          merge(awal, mid);
          merge(mid, akhir);
          mergeSort(awal, mid, akhir);
      }
}

int main(){
    int n;
   cout<<"Masukan banya data = ";cin>>n;
   cout<<"Masukan data yang akan di susun = ";
   for(int i=0;i<n;i++)
   cin>>data[i];
   merge(0,n);
   for(int i=0;i<n;i++)
        cout<<data[i]<<' ';

return 0;
}

Alhamdulillah

Selamat mencoba dan semoga bermanfaat :)

Wassalamualikum w.w.

Read More

Rencana Kuliah Bulan Ke-3 : Sorting Data Secara Manual Dengan Metode INSERTION SORT

Bismillahirohmanirrohim
Assalamualikum w.w,

Berikut ini adalah materi dari SEARCING AND SORTING. Program yang dibuat yaitu tentang Sorting Data Secara Manual Dengan Metode Insertion Sort

Insertion Sort

     Insertion Sort merupakan algoritma sorting, terutama untuk mengurutkan data dengan jumlah element sedikit. Dimana Input berupa deretan angka jumlah n buah data dan output berupa permutasi (pengurutan) sejumlah n angka dari input, dimana hasilnya berupa data yang sudah terurut secara asceding maupun desceding.
     Proses yang terjadi pada pengurutan dengan Insertion Sort adalah dimulai dari data ke-2 kemudian disisipkan pada tempat yang sesuai. Data pada posisi pertama dianggap memang sudah benar pada tempatanya. Ilustrasinya mirip seperti saat menyisipkan kartu dipermainan kartu. Dimulai dengan tangan kiri yang kosong dan kartunya tertumpuk dimeja. Selanjutnya kita ambil satu persatu kartu di meja dan diletakkan ditangan kiri dengan posisi yang benar (terurut).Untuk menemukan posisi yang benar, maka kita harus membandingkan satu persatu kartu yang ada (ditangan kiri) secara berurutan.
     Demikian juga halnya dalam pengurutan data. Jika data sudah ada, maka pengurutan dimulai dengan mengambil satu data dan membandingkannya dengan data-data yang ada didepannya. Jika data yang diambil memenuhi syarat perbandingan, maka data yang diambil tersebut akan diletakan di depan data yang dibandingkan, kemudian data-data yang dibandingkan akan bergeser mundur.

     Catatan: Dalam hal pengurutan data dengan metode insertion sort ini, data yang diambil pertama adalah data kedua, kemudian data yang diambil akan dibandingkan dengan data – data yang ada disebelah kiri / data sebelumnya (data- data sebelum data yang diambil). Jika proses tersebut selesai, maka akan dilanjutkan dengan data-data selanjutnya (data ke-3, data ke-4… dan seterusnya). Proses akan berlangsung sampai data – data terurutkan dengan benar.

   Berikut adalah simulasi Algoritma Insertion Sort Jika digambarkan secara singkat, maka algoritma Insertion sort ini dapat digambar sebagai berikut.

Ilustrasi konsep insertion sort ini adalah sebagai berikut:

5 [2] 4 6 1 3
2 5 [4] 6 1 3
2 4 5 [6] 1 3
1 2 4 5 6[ 3]
1 2 3 4 5 6

Berikut ini penjelasan menggunakan 5 kaidah :
1. Mengerti masalah :
    Mencari bilangan terkecil ke yang terbesar 
2. Menentukan input dan output nya :
    input = 5 2 4 6 1 3
    output = 1 2 3 4 5 6
3. Menyusun Algoritma dengan Flowchart :

4. Mengelementasikan Dengan C++ :

#include <iostream>

#include <conio.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

using namespace std;

class Sorting {

      friend istream& operator>>(istream& in, Sorting& a);

      friend ostream& operator<<(ostream& out, Sorting& a);

public:

       void baca_data();

       void cetak_data();

  void buble_sort();

  void insertion_sort();

  void selection_sort();

private:

        void minimum(int , int, int&);

void tukar (int&, int&);

int data[10], n;

};

  istream& operator>>(istream& in, Sorting& a) {

    cout<<"Banyak data : ";

    in>>a.n;

    for (int i = 0; i < a.n; i++) {

    cout<<"Data ke-" <<i+1<< " : ";

    in>>a.data[i];

}

  return in;

}

  ostream& operator<<(ostream& out, Sorting& a) {

    for (int i = 0; i < a.n; i++)

    out<<a.data[i] << " ";

    out<<"\n";

  return out;

}

  void Sorting::tukar (int &a, int &b){

       int temp;

       temp = a;

  a = b;

  b = temp;

  }

  void Sorting::insertion_sort(){

       int i, j, temp;

  cout<<"Data pertama sudah ada ditangan kiri, yaitu : " << data[0] << '\n';

  for(j = 1; j < n; j++){

           temp = data[j];

  cout<<"\nData ke-" << j+1 << " yaitu " << data[j] << " diambil dari meja\n";

  cout<<"Dilakukan penggeseran elemen :\n";

       for(i = j - 1; (i >= 0) && (data[i] > temp); i--){

           cout<<"data pd posisi ke-[" << i+1 << "] digeser ke posisi [" << i+2 << "]\n";

  data[i+1] = data[i];

       }

        cout<<"Data baru masuk pada posisi ke-[" << i+2 << "]\n";

data[i+1] = temp; //Insert key into proper position

cout<<"Data saat ini adalah : ";

for (int k=0; k<=j; k++) cout << data[k] << " ";

            getch();

}

  }

int main(int argc, char** argv) {

    Sorting angka;

cin>>angka;

angka.insertion_sort();

cout<<"\nHasil akhir adalah : \n";

cout<<angka;

 return 0;

}

    

5. Menguji coba dengan data :

    Setelah diuji coba program nya berjalan. 

Materi Selanjut nya:
Sorting Data Secara Manual Dengan Metode Bubble Sort KETIK DISINI
Sorting Data Secara Manual Dengan Metode Selection Sort KLIK DISINI

Alhamdulillah

Selamat mencoba dan semoga bermanfaat :)

Wassalamualikum w.w.

Read More

Kasus 8.7 Quick Sort

Bismillahirohmanirrohim
Assalamualikum w.w,

Berikut ini adalah materi dari SEARCING AND SORTING. Program yang dibuat yaitu tentang Quick Sort:

Program menggunakan Dev C++:

#include <iostream>

#include <cstdlib>/* run this program using the console pauser or add your own getch, system("pause") or input loop */

using namespace std;

void masuk_data(int A[], int n) {

     int i;

for (i = 0; i < n; i++) {

 cout << "Data ke-%d : ",i+1;

 cin >> A[i]; } }

void cetak_data(const int A[], int n) {

     int i;

     for (i = 0; i < n; i++)

     cout << "%d ",A[i];

cout << "\n";}

void tukar (int *a, int *b){

     int temp;

temp = *a;

*a = *b;

*b = temp;}

void quick_sort(int data[], int L, int R) {

     int i, j, p;

p = data[(L+R) / 2];

i = L;

j = R;

while (i<=j) {

while (data[i] < p) i++;

while (data[j] > p) j--;

if (i<=j){

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

 i++;

 j--; } }

if (L < j) quick_sort(data,L,j);

if (i < R) quick_sort(data,i,R); }

int main(int argc, char** argv) {

    int data[10], n;

cout << "Banyak data : ";

cin >> n;

masuk_data(data,n);

quick_sort(data,0,n-1);

cetak_data(data,n);

 return 0;

}

Gambar outptu nya:

Gambar programnya:

Alhamdulillah

Selamat mencoba dan semoga bermanfaat :)

Wassalamualikum w.w.

Read More

Kasus 8.6 Merge Sort

Bismillahirohmanirrohim
Assalamualikum w.w,

Berikut ini adalah materi dari SEARCING AND SORTING. Program yang dibuat yaitu tentang Merge Sort:

Program menggunakan Dev C++:

#include <iostream>

#include <cstdlib>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

using namespace std;

typedef int larik[10];

void masuk_data(int A[], int n){

     int i;

for (i = 0; i < n; i++){

 cout << "Data ke-%d : ",i+1;

 cin >> A[i];

     }

}

void cetak_data(const int A[], int n) {

     int i;

for (i = 0; i < n; i++)

     cout << "%d ",A[i];

     cout << "\n";

}

void merge(larik a, int kiri, int tengah, int kanan){

     int bagianKiri, posTemp, banyakElemen, i;

larik temp;

bagianKiri = tengah - 1;

posTemp = kiri;

banyakElemen = kanan - kiri + 1;

while ((kiri <= bagianKiri) &&(tengah <= kanan))

         if ((a[kiri] <= a[tengah])){

  temp[posTemp] = a[kiri];

           posTemp = posTemp + 1;

  kiri = kiri + 1;

} 

else{

temp[posTemp] = a[tengah];

posTemp = posTemp + 1;

tengah = tengah + 1;

        }

/* kopi bagian kiri */

while ((kiri <= bagianKiri)) {

temp[posTemp] = a[kiri];

posTemp = posTemp + 1;

kiri = kiri + 1;

}/* kopi bagian kanan */

         while ((tengah <= kanan)) {

temp[posTemp] = a[tengah];

posTemp = posTemp + 1;

tengah = tengah + 1;

         } /* kopi kembali ke array asal */

for (i = 1; i <= banyakElemen; i++){

a[kanan] = temp[kanan];

kanan = kanan - 1;

}

}

void merge_sort(larik A, int kiri, int kanan){

    int tengah;

if ((kiri < kanan)){

tengah = (kiri + kanan) / 2;

merge_sort(A, kiri, tengah);

merge_sort(A, tengah + 1, kanan);

merge(A, kiri, tengah + 1, kanan);

}

}

int main(int argc, char** argv) {

    int n;

larik data;

cout << "Berapa data array : ";

cin >> n;

masuk_data(data, n);

cetak_data(data, n);

merge_sort(data, 0, n-1);

cetak_data(data, n);

return 0;

}

Gambar program nya:

Gambar output nya:

Alhamdulillah

Selamat mencoba dan semoga bermanfaat :)

Wassalamualikum w.w.

Read More