"TI Politala Alpro 2 B"

"PROGRAM SEARCHING DALAM C++"

1.    Definisi C++

C++ adalah bahasa pemrograman komputer yang di buat oleh Bjarne Stroustrup, yang merupakan perkembangan dari bahasa C dikembangkan di Bong Labs (Dennis Ritchie) pada awal tahun 1970-an, Bahasa itu diturunkan dari bahasa sebelumnya, yaitu B.

2.    Definisi Searching

Searching adalah mencari data yang dibutuhkan. Searching dalam pemrograman bisa dilakukan untuk mencari data yang ada di dalam memory komputer. Dalam kehidupan sehari-hari kita juga sering melakukan kegiatan searching seperti mencari data/informasi yang ada dalam internet. Ada beberapa metode yang dapat digunakan untuk searching, ada yang dinamakan:

Ø Sequential Search

Ø Binary Search

3.    Definisi Sequential Search

Sequential Search merupakan metode pencarian data dalam array dengan cara membandingkan data yang dicari dengan data yang ada di dalam array secara berurutan. Pencarian data dengan Metode Sequential Search efektif untuk mencari data yang dalam posisi yang tidak terurut atau acak.

Prosesnya bisa dijelaskan seperti berikut:

1.    Menentukan data yang dicari

2.    Membaca data array satu per satu secara sekuensial

3.    Mulai dari data pertama sampai dengan data terakhir, kemudian data yang dicari tadi dibandingkan dengan masing-masing data yang ada di dalam array.

a.    Jika data yang dicari ditemukan maka kita dapat membuat statement bahwa data telah temukan.

b.    Jika data yang dicari tidak ditemukan maka kita dapat membuat statement bahwa data telah temukan.

Ilustrasi:

Data yang dicari yaitu 7 disimpan di variabel x, kemudian akan dibanding satu per satu secara sekuensial terhadap data yang ada dalam array. Jika ditemukan data di dalam array yang sama dengan data yang dicari artinya data ditemukan.

Sequential Searching memiliki Kelebihan dan Kekurangan yaitu:

Ø Kelebihan Sequential Searching bisa dikatakan lebih mudah dalam implementasinya dalam pemrograman.

Ø Kekurangannya jika data yang terdapat dalam suatu array itu sangat banyak, maka akan diperlukan waktu yang lebih lama untuk membandingkan data yang dicari dengan jumlah data yang sangat banyak dalam suatu array.

4.     Definisi Binary Search

Metode pencarian Binary yaitu mencari data dengan melakukan mengelompokkan array menjadi bagian-bagian. Binary Search ini hanya dapat diimplementasikan pada data yang telah terurut baik ascending maupun descending dalam suatu array.

Proses Binary Search yang urutan datanya ascending:

1.    Pertama buat perulangan lalu menentukan posisi low yaitu posisi yang menandakan index paling rendah kemudian menentukan posisi high. Kemudian mencari posisi mid = (high + low)/2

2.    Lalu membandingkan data yang dicari dengan nilai yang ada di posisi mid.

3.    Jika data yang dicari sama dengan nilai yang ada di posisi mid berarti data ditemukan.

4.    Jika data yang dicari lebih kecil dari nilai yang ada di posisi mid maka pencarian data akan dilakukan dibagian kiri mid dengan melakukan pembandingan. dengan kondisi posisi high berubah yaitu (mid - 1) dan posisi low tetap.

5.    Jika data yang dicari lebih besar dari nilai yang ada mid  maka pencarian data akan dilakukan di bagian kanan dari mid dengan posisi low yang berubah yaitu (mid + 1) dan posisi high tetap.

Contoh Ilustrasi:

Setelah menentukan low dan high kemudian menentukan mid. perhitungan mid=(low+high)/2 jadi mid=(0+4)/2, artinya mid berada di data[2]. Kemudian data yang dicari yang ditampung di variabel x dibandingkan dengan data/nilai yang berada di mid. data yang dicari ialah 7<10 kemudian pencarian data dilakukan di bagian kiri mid.

Pencarian di bagian kiri mid masih dalam perulangan yang sama, namun indeksnya yang dipersempit. Karena data yang dicari lebih kecil dari data mid yang sebelumnya maka posisi high yang berubah yaitu (mid - 1) yang sebelumnya dan low tetap pada posisi yang sama. Kemudian menentukan mid =(0+1)/2 = 0. Artinya mid sekarang terletak di data[0]. lalu data yang dicari dibandingkan dengan mid. 7=7 artinya data telah ditemukan

Kelebihan dan Kekurangan Binary Search:

Ø Kelebihannya yaitu tidak perlu membandingkan data yang dicari dengan seluruh data array yang ada, cukup melalui titik tengah kemudian kita bisa menentukan ke mana selanjutnya mencari data yang ingin dicari.

Ø Kekurangan implementasi agak sedikit lebih rumit karena tidak bisa digunakan pada data array yang masih acak. Jadi harus melakukan sorting terlebih dahulu dalam implementasinya.

5.    Bentuk Umum Struktur Penulisan

a.    Bentuk Umum Struktur Penulisan Sequential Search

#include <iostream>

using namespace std;

///variabel global

int A[] = {2,6,3,5,12,14,1,7,20,21,19};

int cari;

int a;

int i;

int ketemu=0;

int main()

{

    cout<< "Input Data Yang Dicari : ";

    cin>>cari;

    a = sizeof(A)/ sizeof (A[0]);

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

    {

        if(A[i]==cari)

        {

            //cout<<cari<<" Ditemukan "<<endl;

            ketemu=!ketemu;

            break;

        }

        /*else

        {

            cout<<cari<<" Tidak Ditemukan "<<endl;

        }*/

    }

    if (ketemu>0)

    {

        cout<<cari<<" Ditemukan ";

    }

    else

    {

        cout<<cari<<" Tidak Ditemukan ";

    }

    return 0;

}

b.   Bentuk Umum Struktur Penulisan Binary Search

#include <iostream>

#include <conio.h>

using namespace std;

int BinarySearch(int Data[], int x, int n)

{

  int L = 0;

  int R = n-1;

  int m;

  int 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();

}

6.    Permasalahan/ Studi Kasus

a.    Studi Kasus Sequential Search

Menemukan data yang dicari dalam sebuah array 1 dimensi yang terdapat data di dalamnya dengan menggunakan Metode Sequential Search. Jika data yang dicari ditemukan di dalam array kemudian ditampilkan letak dari indexnya.

b.   Studi Kasus Binary Search

Menemukan data yang dicari dalam sebuah array 1 dimensi yang terdapat data di dalamnya dengan menggunakan Metode Binary Search. Jika data yang dicari ditemukan di dalam array kemudian ditampilkan letak dari indexnya.

7. Listing Program

a.    Listing Program Sequential Search

b.   Listing Program Binary Search

8.    Hasil Running

a.    Hasil Running Sequential Search

Tampilan awal saat running

Menginputkan data dan datanya ditemukan

 Menginputkan data dan datanya tidak ditemukan

b.   Hasil Running Binary Search

Tampilan awal saat running

Menginputkan data dan datanya ditemukan

Menginputkan data dan datanya tidak ditemukan

9.    Penjelasan

Code	Penjelasan
#include <iostream>	Header untuk cout dan cin
#include <conio.h>	Header untuk fungsi getch
using namespace std;	Pengganti std::cout atau std::cin
int main ( )	Fungsi main yang dijalankan terlebih dahulu jika program dirunning
{ dan }	Awal dan akhiran fungsi
int A[] = {2,6,3,5,12,14,1,7,20,21,19};	Inisialisasi data untuk search (data yang dapat dicari)
int cari;	Deklarasi untuk pencarian
int a;	Deklarasi pengganti sizeof(A)/ sizeof (A[0]);
int i;	Deklarasi untuk array
int ketemu=0;	Deklarasi untuk data yang ditemukan saat pencarian
int (integer)	Deklarasi variabel teks dengan tipe data int. Artinya variabel Untuk bilangan bulat.
cout	Merupakan sebuah objeck didalam C++ digunakan untuk menampilkan suatu data kelayar.
cin	Merupakan sebuah objeck didalam C++ digunakan untuk memasukkan suatu data.
endl atau \n	Untuk mengganti baris atau fungsi enter
for	Merupakan fungsi untuk operasi perulangan
if dan else if	Fungsi untuk operasi penyeleksian kondisi
break;	Pemisah antar aturan

10.         Diagram Alir (Flow chart) Program Searching

a.      Diagram Alir (Flow chart) Program Sequential Search

b. Diagram Alir (Flow chart) Program Binary Search

DAFTAR PUSTAKA

    

Frieyadie, S. (2007). Borland C++. Jakarta: DIKTAT KULIAH PEMROGRAMAN KOMPUTER.

TEKNIK, J. T. (2017/2018). Pengenalan Bahasa C++, Algoritma Pemrograman, Integrated Development Equipment (IDE) Visual C++ dan Dasar Dasar Bahasa C++. Retrieved from Modul Praktikum C++ Dasar Pemrograman Komputer: http://elektro.um.ac.id/wp-content/uploads/2016/04/Dasar-Pemrograman-Modul-1-Pengenalan-Pemrograman.pdf

"TI Politala Alpro 2 B"

“SORTING DALAM C++”

1.      Alat dan Bahan

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

2.      Teori Singkat

Algoritma pengurutan (sorting algorithm) adalah algoritma yang mengurutkan data menggunakan aturan tertentu. Ada 2 macam, yaitu urut naik (ascending) dan urut turun descending)

a.       urut naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling besar

b.      urut turun (descending) yaitu data yang mempunyai nilai paling besar sampai paling kecil.

Ada 2 metode sorting yang dipelajari, yaitu Buble dan Quick Sort.

2.1. Pengurutan Gelembung (Bubble Sort)

   Pengurutan gelembung adalah algoritma pengurutan yang paling tua dan sederhana untuk diimplementasikan. Algoritma ini juga cukup mudah untuk dimengerti. Algoritma pengurutan gelembung dalam implementasi bahasa C adalah sebagai berikut.

   Pengurutan gelembung ini menggunakan dua buah kalang (loop) for. Kalang yang pertama melakukan travesal dari indeks terkecil sedangkan kalang yang kedua melakukan traversal dari indeks terbesar. Kalang yang satu berada di dalam kalang yang lain dan panjang masing-masing tergantung pada banyaknya elemen. Siklus yang pertama melakukan n-1 perbandingan, siklus yang kedua melakukan n-2 perbandingan, siklus yang ketiga melakukan n-3, dan seterusnya. Sehingga total semua perbandingan

      (n-1) + (n-2) + .. +1

     yang dapat disederhanakan menjadi n(n-1)/2.

      Algoritma ini bekerja dengan cara membandingkan nilai tiap elemen dalam tabel dengan elemen setelahnya, dan menukar nilainya jika sesuai dengan kondisi yang diperlukan. Proses ini akan terus berulang hingga seluruh elemen dalam tabel telah diproses dan elemen dalam tabel telah terurut.

Algoritma pengurutan gelembung ini adalah algoritma yang paling lamban dan tidak mangkus dibandingkan dengan algoritma pengurutan yang lain dalam penggunaan secara umum. Dalam kasus terbaik (yaitu list sudah terurut), kompleksitas algoritma pengurutan gelembung adalah O(n). Namun, untuk kasus umum, kompleksitas algoritma pengurutan gelembung adalah O(n2 ).

Grafik di atas menggambarkan kompleksitas algoritma dari pengurutan gelembung.

2.2. Pengurutan Cepat (Quick Sort)

    Algoritma quick sort sangat sederhana dalam teori, tetapi sangat sulit untuk diterjemahkan ke dalam sebuah code karena pengurutan dilakukan dalam sebuah list dan diproses secara rekursif. Algoritma ini terdisi dari empat langkah (yang mana menyerupai merge sort) yaitu :

• Memilih sebuah elemen untuk dijadikan poros atau pivot point (biasanya elemen paling kiri dari tabel).
• Membagi tabel menjadi dua bagian, satu dengan elemen yang lebih besar dari poros, dan satu lagi untuk elemen yang lebih kecil dari poros.
• Mengulang algoritma untuk kedua buah tabel secara rekursif.

      Tingkat keefektifan dari algoritma ini dangat bergantung pada elemen yang dipilih menjadi poros. Kasus terburuk terjadi ketika tabel sudah terurut dan elemen terkecil di sebelah kiri menjadi poros. Kasus ini mempunyai kompleksitas algoritma O(n 2 ). Maka dari itu sangat disarankan untuk memilih poros bukan dari elemen paling kiri dari tabel, tetapi dipilih secara random. Selama poros dipilih secara random, algoritma quick sort mempunyai kompleksitas algoritma sebesar O(n log n).

        Algoritma quick sort mengurutkan dengan sangat cepat, namun algoritma ini sangat komplex dan diproses secara rekursif. Sanat memungkinkan untuk menulis algoritma yang lebih cepat untuk beberapa kasus khusus, namun untuk kasus umum, sampai saat ini tidak ada yang lebih cepat dibandingkan algoritma quick sort.

         Walaupun begitu algoritma quick sort tidak selalu merupakan pilihan yang terbaik. Seperti yang telah disebutkan sebelumnya, algoritma ini dilakukan secara rekursif yang berarti jika dilakukan untuk tabel yang berukuran sangat besar, walaupun cepat, dapat menghabiskan memori yang besar pula. Selain itu, algoritma ini adalah algoritma yang terlalu komplex untuk mengurutkan tabel yang berukuran kecil (hanya puluhan elemen misalnya). Selain itu algoritma quick sort mempunyai tingkat efisiensi yang buruk ketika dioperasikan pada tabel yang hampir terurut atau pada tabel yang terurut menurun.

         Grafik di atas menggambarkan kompleksitas algoritma dari quick sort.

2.3. Pengurutan Dengan Penggabungan (Merge Sort)

      Algoritma merge sort membagi (split) tabel menjadi dua tabel sama besar. Masing-masing tabel diurutkan secara rekursif, dan kemudian digabungkan kembali untuk membentuk tabel yang terurut.

     Implementasi dasar dari algoritma merge sort memakai tiga buah tabel, dua untuk menyimpan elemen dari tabel yang telah dibagi dua dan satu untuk menyimpan elemen yang telah teurut. Namun algoritma ini dapat juga dilakukan langsung pada dua tabel, sehingga menghemat ruang atau memori yang dibutuhkan. Di bawah ini adalah algoritma untuk merge sort yang dilakukan pada dua tabel.

       Karena algoritma merge sort adalah algoritma yang dijalankan secara rekursif maka T(n) dari algoritma ini adalah

Sehingga, algoritma merge sort memiliki kompleksitas algoritma O(n log n). Algoritma merge sort ini sebenernya lebih cepat dibandingkan heap sort untuk tabel yang lebih besar. Namun, algoritma ini membutuhkan setidaknya ruang atau memori dua kali lebih besar karena dilakukan secara rekursif dan memakai dua tabel. Hal ini menyebabkan algoritma ini kurang banyak dipakai.

Grafik di atas menggambarkan kompleksitas algoritma dari merge sort.

Sumber : 

http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2006-2007/Makalah/Makalah0607-77.pdf