MAKALAH

ALGORITMA & LOGIKA

SEARCHING & SORTING

Disusun oleh :

Akbar Wibowo                                :        12147549

Ervan Amaludin                               :        12141838

Rizki Romdan                                  :        12143493

Ikhsan aji akbar .s.                          :        12144383

Dosen Pembimbing:
AHMAD SINUN

PROGRAM STUDI MANAJEMEN INFORMATIKA 
BINA SARANA INFORMATIKA
TAHUN AJARAN 2014/2015

BAB I

PENDAHULUAN

1.I  LATAR BELAKANG.

          Dalam ilmu logika dan algoritma sering kali menemui masalah tentang bagaimana mendapatkan suatu data dalam kumpulan data. Dalam keperluannya untuk mencari data, terdapat beragam algoritma pencarian(search algoritm). Algoritma sendiri merupakan “algoritma yang menerima sebuah argumen ‘a’ dan mencoba untuk menemukan sebuah rekaman yang memiliki kunci ‘a’. Pencarian dapat dilakukan terhadap data yang secara keseluruhan berada dalam memory komputer ataupun yang berada dalam penyimpanan ekternal (hardisk). Pencarian yang dilakukan terhadap data yang berada dalam komputer di kenal dengan pencarian internal sedangkan pencarian yang dilakukan pada media penyimpanan eksternal disebut pencarian ekternal. Pencarian internal meliputi Pencarian sekuensial (sequential search) dan pencarian biner (binary search).

          Sorting array merupakan salah satu aplikasi yang paling penting dalam suatu sistem aplikasi perhitungan data. Biasanya suatu bank memiliki komputasi sorting array yang sudah biasa digunakan dalam aplikasinya sehari-hari. Bahkan telephone juga mengurutkan suatu list yang terdiri dari nama akhir , nama awal agar bisa memudahkan dalam perhitungan dalam mencari nomor telephone.

1.2 RUMUSAN MASALAH.

          A. Searching

                   1.Tehnik Sequential Search/Linier Search

                  2.Tehnik Binary Search

          B. Sorting

                   1.Metode Selection Sort

2.Metode Bubble Sort

3.Metode Merge Sort

4.Metode Quick Sort

5.Metode Insertion

1.3 TUJUAN & MANFAAT

          Makalah ini disusun untuk memaparkan tentang pengertian sorting dan searching array dalam aplikasi di dunia kerja. Dengan membaca makalah ini, pembaca akan mengetahui lebih dalam mengenai membuat algoritma dari searching dan sorting array yang bisa dijadikan sebagai referensi dalam pembuatan algoritma. Selain itu, pembaca juga akan mengetahui manfaat dari searching dan sorting array.

BAB II

LANDASAN TEORI

2.1 PENGERTIAN

          A.SEARCHING  

1.LINER SEARCH.

Algoritma pencarian secara linear adalah algoritma untuk mencari sebuah nilai pada table sambarang dengan cara melakukan pass atau transversal. Transversal dari awal sampai akhir table. Ada dua macam cara pencarian pada table. Algoritma mempunyai dua jenis metode yaitu dengan Boolean dan tanpa Boolean.

          Ilustrasi Metode Linier Search :

Misalnya terdapat array satu dimensi sebagai berikut:

     0                1              2               3              4                5                6                   7            index

8

10

12

6

7

1

50

100

 Value
 

              Kemudian program akan meminta data yang akan dicari, misalnya 6(x = 6).

Iterasi :

            6 = 8 (tidak!)

            6 = 10 (tidak!)

            6 = 6 (Ya!) => output : “Ada” pada index ke-2

Jika sampai data terakhir tidak ditemukan data yang sama maka output : “ data yang dicari tidak ada”.

          CONTOH PROGRAM SEARCHING METODE C++ :

#include <conio.h>
#include <iostream.h>
main(){
int c,i,posisi;
int A[20]={3,2,4,10,20,1,5,8,7,9,6,5,11,12,14,13,16,15,17,19};
cout<<"Data : ";
for(i=0;i<20;i++){
 cout<<A[i]<<" ";
}
cout<<"\nData yang ingin dicari : ";
cin>>c;
i=0;
posisi=0;
while(i<19 && A[i]!=c){
 i++;
}
if (A[i]!=c){
 cout<<"Maaf data yang dicari tidak ada";
}else if(posisi=i+1)
   cout<<"ditemukan pada posisi ke "<<posisi;
getch();
}       

          Metode flowchart :

2.BINARY SEARCH

 Algoritma pencarian biner adalah algoritma untuk mencari sebuah nilai pada tabel teurut dengan cara menghilangkan setengah data pada setiap langkah. Algoritma ini mencari nilai yang dicari dengan tiga langkah yaitu :
• Mencari nilai tengah dari tabel (median)
• Melakukan perbandingan nilai tengah dengan nilai yang dicari untuk menentukan
  apakah nilai yang dicari ada pada sebelum atau setelah nilai tengah
• Mencari setengah sisanya dengan cara yang sama.

          CONTOH PROGRAM BINARY SEARCHING METODE C++ :

#include <iostream.h>

#include <conio.h>

main ()

{

 int jd, cari,no, kiri,kanan,tengah,data[50];

cout<<" Input Jumlah Data  : ";

 cin>>jd;

 cout<<endl;

 for (no=0;no<jd;no++)

     {

 cout<<" Input Data Ke-"<<(no+1)<<"    : ";

    cin>>data[no];

     }

cout<<endl;

cout<<" Input Nilai Dicari : ";

cin>>cari;

 kiri=0;

 kanan=jd-1;

 tengah=(kanan-kiri)/2;

while ((data[tengah]!=cari) && (kiri>=0)&& (kanan<jd) && (kanan>=kiri))

 {

          if (cari>data[tengah])

         {

              kiri=tengah+1;

         }

         else if (cari<data[tengah])

         {

              kanan=tengah-1;

         }

         tengah=kiri+(kanan-kiri)/2;

     }

cout<<endl;

    if (data[tengah]==cari)

     {

          cout<<" Keterangan         : Data Ditemukan";

     }

     else

     {

          cout<<" Keterangan         : Data Tidak Ditemukan";

getch();

     }}

B. SORTING

          1.SELECTION SORT

                   Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai darii dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.

          Contoh program sorting selection sort metode c++ :

#include <iostream.h>  

#include <conio.h>  

main()  

{  

int i,j,n,data[10],simpan,min,posisi;  

cout<<"masukkan banyak data= ";cin>>n;  

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

{  

cout<<"data "<<i<<" = ";cin>>data[i];  

}  

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

{  

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

{  

if(data[i]>data[j])  

{  

simpan=data[i];  

data[i]=data[j];  

data[j]=simpan;  

}

}

}  

cout<<"hasil= ";  

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

cout<<data[i]<<" ";  

getch(); 

\}

2. BUBBLE SORT.

          Bubble sort adalah proses pengurutan sederhana yang bekerja dengan cara berulang kali membandingkan dua elemen data pada suatu saat dan menukar elemen data yang urutannya salah. Ide dari Bubble sort adalah gelembung air yang akan "mengapung" untuk table yang terurut menaik (ascending). Elemen bernilai kecil akan "diapungkan"(ke indeks terkecil), artinya diangkat ke "atas" (indeks terkecil) melalui pertukaran. Karena algoritma ini melakukan pengurutan dengan cara membandingkan elemenelemen.

          Contoh program bubble sort metode c++ :

#include <iostream.h>
#include <iomanip.h>
void main ()
{
     int nilai[8];
     int temp;
     cout<<"Data sebelum diurutkan"<<endl;
     for (int ctr=1;ctr<=8;ctr++)
     {
          cout<<"Masukkan Data ke "<<ctr<<" : ";
        cin>>nilai[ctr];
     }
     cout<<endl;
    cout<<endl;
     for (int i=0;i<=8;i++)
    {
          for (int ii=0;ii<=8;ii++)
        {
            if (nilai[ii]>nilai[ii+1])
                {
                     temp=nilai[ii];
                     nilai[ii]=nilai[ii+1];
                     nilai[ii+1]=temp;
                }
          }
     }
     cout<<"Data setelah diurutkan"<<endl;
          for (int iii=0;iii<8;iii++)
          {
                cout<<setw(3)<<nilai[iii];
          }
}

3. MERGE SORT.

          Merge sort menggunakan pola divide and conquer. Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah
berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.
1. Divide
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
2. Conquer
Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif
3. Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan
Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.

4.QUICK SORT.

          Quicksort ditemukan oleh C.A.R Hoare. Seperti pada merge sort, algoritma ini juga berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai berikut :
1. Divide
Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.
2. Conquer
Mengurutkan elemen pada sub-rangkaian secara rekursif
Pada algoritma quicksort, langkah “kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array

5. INSERTION SORT.

          Insertion sort adalah sebuah algoritma pengurutan yang membandingkan dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Karena algoritma ini bekerja
dengan membandingkan elemen-elemen data yang akan diurutkan, algoritma ini termasuk pula dalam comparison-based sort.
Ide dasar dari algoritma Insertion Sort ini adalah mencari tempat yang "tepat" untuk setiap elemen array, dengan cara sequential search. Proses ini
kemudian menyisipkan sebuah elemen array yang diproses ke tempatnya ang seharusnya. Proses dilakukan sebanyak N-1 tahapan (dalam sorting
disebut sebagai "pass"), dengan indeks dimulai dari 0.
Proses pengurutan dengan menggunakan algoritma Insertion Sort dilakukan dengan cara membandingkan data ke-i (dimana i dimulai dari data
ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan
posisi yang seharusnya.

          Contoh program insertion sort metode c++ :

#include <iostream.h>
#include <conio.h>
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 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;
    }
}
void main()
{
    cout<<"  PROGRAM INSERTION SORT"<<endl;
    cout<<"Masukkan Jumlah Data : ";    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cout<<"Masukkan data ke "<<i<<"   : ";    cin>>data[i];
        data2[i]=data[i];
    }
    insertion_sort();
    cout<<"Data Setelah di Sort : ";
    for(i=1; i<=n; i++)
    {
        cout<<" "<<data[i];
    }
}

Metode flowchart sorting :

BAB III

PENUTUP

3.1 KESIMPULAN

          Berdasarkan uraian bahasan “jenis-jenis algoritma searching dan sorting” dapat disimpulkan bahwa :
1. Terdapat banyak algoritma searching dan sorting yang bisa programmer gunakan sehingga dapat digunakan dalam situasi dan kondisi masalah tertentu
2. Pembuat algoritma baru dirasakan sangat penting karena setiap masalah akan memerlukan teknik sorting dan searching yang baik dan sesuai