Materi Algoritma

I.       SORTING

A.      Pengertingan Sorting

Sorting (pengurutan data) didefinisikan sebagai suatu proses untuk menyusun kembali humpunan obyek menggunakan aturan tertentu.

B.      Macam-macam Sorting

1.       Selection Sorting

Metode seleksi melakukan pengurutan dengan cara mencari data yang terkecil kemudian menukarkannya dengan data yang digunakan sebagai acuan atau sering dinamakan pivot.

Proses pengurutan dengan metode seleksi dapat dijelaskan sebagai berikut :

Langkah pertama dicari data terkecil dari data pertama sampai data terakhir. Kemudian data terkecil ditukar dengan data pertama. Dengan demikian, data pertama sekarang mempunyai nilai paling kecil dibanding data yang lain. Langkah kedua, data terkecil kita cari mulai dari data kedua sampai terakhir. Data terkecil yang kita peroleh ditukar dengan data kedua dan demikian seterusnya sampai semua elemen dalam keadaan terurutkan.

ü  Contoh Programnya yaitu :

#include<iostream.h>

void main()

{

int temp;

int nilai[]={5,3,1,4,1,1,0,7,0};

cout<<"Nilai Sebelum diurutkan :"<<endl;

for(int k=0;k<=8;k++)

                {

                                cout<<nilai[k]<<" ";

                }

                                cout<<endl;

                                for(int r=0;r<=8;r++)

                {

                                for(int d=r;d<=7;d++)

                {

                                if(nilai[r]>=nilai[d+1])

                {

                                temp=nilai[d+1];

                                nilai[d+1]=nilai[r];

                                nilai[r]=temp;

                }

                }

                }

                                cout<<endl;

                                cout<<"Nilai Setelah diurutkan :"<<endl;

                                for(int f=0;f<=8;f++)

                {

                                cout<<nilai[f]<<" ";

                }

}

Output dari program tersebut adalah :

Nilai sebelum diurutkan : 5 3 1 4 1 1 0 7 0 Nilai setelah diurutkan : 0 0 1 1 1 3 4 5 7

 

2.       Bubble Sorting

Bubble sort (metode gelembung) adalah metode/algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.

v  Kelebihan Bubble Sort

~         Metode Buble Sort merupakan metode yang paling simpel

~         Metode Buble Sort mudah dipahami algoritmanya

v  Kelemahan Bubble Sort

Meskipun simpel metode Bubble sort merupakan metode pengurutanyang paling tidak efisien. Kelemahan buble sort adalah pada saat mengurutkan data yang sangat besar akan mengalami kelambatan luar biasa, atau dengan kata lain kinerja memburuk cukup signifikan ketika data yang diolah jika data cukup banyak. Kelemahan lain adalah jumlah pengulangan akan tetap sama jumlahnya walaupun data sesungguhnya sudah cukup terurut. Hal ini disebabkan setiap data dibandingkan dengan setiap data yang lain untuk menentukan posisinya.

v  Proses Pengurutan Bilangan Dengan Metode Bubble Sort

·         Bubble Sort adalah nama yang diberikan pada prosedur untuk mengatur sekelompok bilangan dengan urutan dari kecil ke besar.

·         Untuk mengurutkan bilangan diperlukan variabel array yang digunakan untuk menampung semua bilangan yang akan diurutkan.

·         Proses pengurutan dilakukan dengan membandingkan semua elemen array satu persatu.

ü  Contoh Programnya yaitu :

#include<iostream.h>

#include<conio.h>

#define c 9

void main()

{

             int e[c]={5,3,1,4,1,1,0,7,0};

             cout<<">>> Sorting dengan Metode Bubble <<<\n";

             cout<<endl;

             int m,p,r;

             r=0;

             while(r<=c-2)

             {

                             p=0;

                             while(p<=c-2-r)

                             {

                                             if(e[p]>e[p+1])

                                             {

                                                             m=e[p];

                                                             e[p]=e[p+1];

                                                             e[p+1]=m;

                                             }

                                             p++;

                             }

                             r++;

             }

             for(p=0;p<=c-1;p++)

             cout<<"Nilai Indeks"<<p<<"="<<e[p]<<endl;

}

Output dari program tersebut adalah :

>>> Sorting dengan Metode Bubble Sort<<< Nilai Indeks0=0 Nilai Indeks1=0 Nilai Indeks2=1 Nilai Indeks3=1 Nilai Indeks4=1 Nilai Indeks5=3 Nilai Indeks6=4 Nilai Indeks7=5 Nilai Indeks8=7

 

3.       Insertion Sorting

Insertion sort ini memiliki waktu penyelesaian yang lebih cepat di bandingkan selection sort dan buble sort, sedangkan cara kerjanya adalah seperti metode sorting yang lain, yaitu melakukan literasi (pengulangan) hingga hasil yang sesuai ditemukan, namun insertion sort ini akan menginsert atau menyisipkan setiap elemen ketempat yang sesuai (setelah dibandingkan dengan elemen kiri dan kanannya)
atau simpelnya, kita bisa mengumpamakan metode ini seperti orang yang sedang mengurutkan kartu, maka dia akan mengambilnya, satu demi satu dan akan menginsertnya ketempat yang sesuai.

ü  Contoh Programnya yaitu :

#include <iostream.h>

#include <conio.h>

#define jumlah 8

void jenis_sisipan(int a[], int jarak)

{

               int c, p;

               for(int r=0; r<jarak;r++)

               {

                               c=a[r];

                               p=r-1;

                               while(a[p]>c&&p>=0)

                               {

                                               a[p+1]=a[p];

                                               p--;

                               }

                               a[p+1]=c;

               }

}

int main()

{

               int A[jumlah]={2,5,3,1,6,4,7,0};

               int a;

               cout<<"Nilai yang belum di urut : ";

               for(a=0;a<jumlah;a++)

               {

                               cout<<A[a];

   }

               cout<<endl;

               jenis_sisipan(A,jumlah);

               cout<<"Nilai yang sudah di urut : ";

               for(a=0;a<jumlah;a++)

               {

                               cout<<A[a];

               }

   getch();

   return 0;

}

Output dari program tersebut adalah :

Nilai yang belum di urut : 25316470 Nilai yang sudah di urut : 01234567

 

4.       Shell Sorting

Distribusi sort mengacu pada algoritma sorting dimana data didistribusikan dari input untuk struktur peralihan beberapa yang kemudian dikumpulkan dan ditempatkan pada output.

5.       Merge Sorting

Prinsip utama yang diimplementasikan pada algoritma merge-sort seringkali disebut sebagai pecah-belah dan taklukkan (bahasa Inggris: divide and conquer). Cara kerja algoritma merge sort adalah membagi larik data yang diberikan menjadi dua bagian yang lebih kecil. Kedua larik yang baru tersebut kemudian akan diurutkan secara terpisah. Setelah kedua buah list tersusun, maka akan dibentuk larik baru sebagai hasil penggabungan dari dua buah larik sebelumnya. Menurut keefektifannya, alogaritma ini bekerja dengan tingkat keefektifan O(nlog(n)).

6.       Counting Sorting

Counting Sort adalah salah satu metode mengurutkan data yang dikenal. Ide dasarnya adalah seperti kita melakukan perhitungan pemilu yaitu dengan mencatat frekuensi atau banyaknya kemunculan data. Namun metode ini hanya cocok digunakan bila data yang digunakan bertipe integer dan dibatasi pada range tertentu.

ü                               Contoh Programnya yaitu :

#include <iostream.h>

#include <conio.h>

void Counting_sort(int [], int, int);

void main()

{

             int r,m = 0, A[15];

              cout << "Nilai yang di input : ";

              cin  >> r;

              cout << "\nElemen yang akan di Sort :\n";

              for ( int i = 1; i <= r; i++)

              {

                             cin >> A[i];

                             if(A[i] > m)

                             {

                                             m = A[i];

                             }

              }

              Counting_sort(A, m, r);

              getch();

}

void Counting_sort(int A[], int m, int n)

{

              int i, j;

    int B[15], C[100];

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

                             C[i] = 0;

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

                             C[A[j]] = C[A[j]] + 1;

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

                             C[i] = C[i] + C[i-1];

              for(j = n; j >= 1; j--)

             {

                             B[C[A[j]]] = A[j];

                             C[A[j]] = C[A[j]] - 1;

              }

              cout << "\nHasilnya : ";

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

              cout << B[i] << "  " ;

}

Output dari program tersebut adalah :

Nilai yang di input :

 

7.       Bucket Sorting

Bucket sort adalah algoritma sorting yang bekerja dengan partisi array ke dalam jumlah terbatas sort. Setiap kotak ini kemudian diurutkan secara individual, baik menggunakan algoritma sorting yang berbeda, atau dengan rekursif menerapkan algoritma bucket sort. Sebuah variasi dari metode ini disebut semacam hitungan tunggal buffered lebih cepat dari jenis cepat dan membutuhkan waktu sekitar waktu yang sama untuk berjalan pada set data.

8.       Radix Sorting

Radix Sort merupakan salah satu algoritma Non-Comparasion Sort (pengurutan tanpa pembandingan). Proses ynang dilakukan dalam metode ini adalah mengklasifikasikan data sesuai dengan kategori terurut yang tertentu, dan tiap kategori dilakukan pengklasifikasian lagi, dan seterusnya sesuai kebutuhan, lalu subkategori-kategori tersebut digabungkan kembali. 
Secara harfiah Radix dapat diartikan sebagai posisi dalam angka, karena metode ini pertamakalinya mengurutkan nilai-nilai input berdasarkan radix pertamanya, lalu pengurutan dilakukan berdasarkan radix keduanya, dan begitu seterusnya. Pada system decimal, radix adalah digit dalam angka decimal.

ü  Contoh Programnya yaitu :

#include<iostream.h>

#include <stdio.h>

#define MAX 4

#define SHOWPASS

void print(int *r,int p)

{

             int j;

             for(j=0;j<p;j++)

             printf("%d\t",r[j]);

}

void radixsort(int *r,int p)

{

             int j,b[MAX],m=0,exp=1;

             for(j=0;j<p;j++)

             {

                             if(r[j]>m)

                             m=r[j];

             }

                             while(m/exp>0)

                             {

                                             int bucket[10]={0};

                                             for(j=0;j<p;j++)

                                                             bucket[r[j]/exp%10]++;

                                             for(j=1;j<10;j++)

                                                             bucket[j]+=bucket[j-1];

                                             for(j=p-1;j>=0;j--)

                                                             b[--bucket[r[j]/exp%10]]=r[j];

                                             for(j=0;j<p;j++)

                                                             r[j]=b[j];

                                             exp*=10;

#ifdef SHOWPASS

             printf("\nPASS   : ");

             print(r,p);

#endif

                             }

}

int main()

{

             int arr[MAX];

             int i,p;

             printf("Enter total elements (p < %d) : ",MAX);

             scanf("%d",&p);

             printf("Enter %d Elements : ",p);

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

             scanf("%d",&arr[i]);

             printf("\nARRAY  : ");

             print(&arr[0],p);

             radixsort(&arr[0],p);

             printf("\nSORTED : ");

             print(&arr[0],p);

             return 0;

}

Output dari program tersebut adalah :

Enter total elements (p < 4) :

 

9.       Heap Sorting

HeapSort adalah algoritma pengurutan data berdasarkan perbandingan, dan termasuk golongan selection sort. Walaupun lebih lambat daripada quick sort pada kebanyakan mesin , tetapi heap sort mempunyai keunggulan yaitu kompleksitas algoritma pada kasus terburuk adalah n log n. Algoritma pengurutan heap sort ini mengurutkan isi suatu larik masukan dengan memandang larik masukan sebagai suatu Complete Binary Tree (CBT). Setelah itu Complete Binary Tree (CBT) ini dapat dikonversi menjadi suatu heap tree. Setelah itu Complete Binary Tree (CBT) diubah menjadi suatu priority queue

ü  Contoh Programnya yaitu :

#include <iostream.h>

#include <stdio.h>

#include <conio.h>

void read(int a[10],int n)

{

    cout<<"reading\n";

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

                                  cin>>a[i];

}

void display(int a[10],int n)

{

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

        cout<<a[i]<<"\t";

}

void shellsort(int a[10],int n)

{

    int gap=n/2;

                 do

                 {

                                  int swap;

                                  do

                                  {

                                                                swap=0;

            for(int i=0;i<n-gap;i++)

                if(a[i]>a[i+gap])

                {

                    int t=a[i];

                                       a[i]=a[i+gap];

                    a[i+gap]=t;

                    swap=1;

                }

        }

                                  while(swap);

    }

    while(gap=gap/2);

}

void main()

{

    int a[10];

                 int n;

    clrscr();

    cout<<"enter n\n";

    cin>>n;

    read(a,n);

    cout<<"before sorting\n";

    display(a,n);

                 shellsort(a,n);

    cout<<"\nafter sorting\n";

    display(a,n);

    getch();

}

Output dari program tersebut adalah :

enter n

 

10.    Quick Sorting

Quick sort adalah salah satu metode pengurutan dalam bahasa pemrograman. Proses sorting atau pengurutan dilakukan berdasarkan metode divide and conqueror. Quick sort ini mengurutkan data dengan sangat cepat. Tetapi tentu saja quick sort ini memiliki kekurangan. Misalnya, proses sorting yang dilakukan secara rekursif. Walaupun prosesnya sangat cepat, tapi menghabiskan memori yang besar jika data yang diurut banyak. Selain itu, quick sort juga tidak cocok jika digunakan untuk mengurutkan data dalam tabel yang berukuran kecil.

ü  Contoh Programnya yaitu :

#include<iostream.h>

#include<conio.h>

#include<iomanip.h>

#define n 8

class quick{

                static int data[n];

 public:

                void tukar(int a,int b);

                void QuickSort(int l, int r);

   void tampil();

};

void main(){

  quick x;

  cout<<endl<<"Data sebelum diurutkan:"<<endl;

  x.tampil();

  x.QuickSort(0,n-1);

  cout<<endl<<"Data setelah diurutkan:"<<endl;

  x.tampil();

  getch();

}

int quick::data[n]={7,4,98,9,2,1,17,20};

void quick::tukar(int a,int b){

  int t;

  t=data[b];

  data [b]=data[a];

  data[a]=t;

}

void quick::QuickSort(int l,int r){

  int i,j,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 quick::tampil(){

                for(int j=0;j<n;j++)              cout<<data[j]<<setw(3);

                                                cout<<endl;

}

Output dari program tersebut adalah :

Data sebelum diurutkan: 7  4   98  9  2  1  17  20 Data setelah diurutkan: 1  2  4  7  9  17  20  98

II.    SEARCHING

A.      Pengertingan Searching

Proses searching (pencarian) adalah menemukan harga (data) tertentu di dalam sekumpulan harga yang bertipe sama (tipe dasar atau tipe bentukan).

Pencarian terbagi Dua

1.       Pencarian Internal, adalah pencarian terhadap sekumpulan data yang disimpan di dalam memori utama (primary memory)

2.       Pencarian Eksternal adalah pencarian terhadap sekumpulan data yang disimpan di dalam memori sekunder (secondary memory), seperti tape atau disk

B.      Tiga (3) Metode Pencarian

1.       Pencarian Beruntun (Sequential Search)

Pencarian beruntun adalah proses membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa.

Pencarian beruntun terbagi dua:

·         Pencarian beruntun pada larik tidak terurut

Pencarian dilakukan dengan memeriksa setiap elemen larik mulai dari elemen pertama sampai elemen yang dicari ditemukan atau sampai seluruh elemen sudah diperiks

·         Pencarian beruntun pada larik terurut.

Jika larik sudah terurut (misal terurut menaik, yaitu untuk setiap I=1..N, Nilai[I-1]<Nilai[I] atau terurut mengecil, yaitu untuk setiap I=1..N, Nilai[I-1]>Nilai[I]), maka proses pencarian lebih singkat dibandingkan pencarian larik yang tidak terurut.

ü  Contoh Program Sequential Search yaitu :

#include<iostream.h>

#include<conio.h>

class sequential{

    int data[50];

    int jml;

  public:

    void input();

    void search();

};

void main(){

  sequential x;

  x.input();

  x.search();

  getch();

} 

void sequential::input(){

  cout<<"Masukkan banyaknya data : ";            cin>>jml;

  for (int i=0;i<jml;i++){

                         cout<<"masukkan data ke- "<<i<<" : ";

                                             cin>>data[i];

  }

}

void sequential::search(){

  int cari, flag=0;

  cout<<"masukkan data yang ingin dicari : ";    cin>>cari;

  for (int j=0;j<jml;j++){

     if(data[j]==cari) flag++;

  }

  if (flag!=0) cout<<"data yang ditemukan ada "<<flag<<endl;

  else if (flag==0) cout<<"data tidak ditemukan"<<endl;

}

Output dari program tersebut adalah :

Masukkan banyaknya data :

 

2.       Pencarian Beruntun dengan Sentinel

Sentinel adalah elemen fiktif yang sengaja ditambahkan sesudah elemen terakhir larik. Jika elemen larik terakhir L[N], maka sentinel dipasang pada elemen L[N+1]. Sentinel ini harganya sama dengan elemen yang dicari. Akibatnya proses pencarian selalu berhasil menemukan data yang dicari. Walaupun demikian harus diperiksa lagi letak data tersebut ditemukan, apakah:

Ø  Di atara elemen-elemen larik sesungguhnya, yaitu L[1]…L[N]

Ø  Pada elemen fiktif (L[N+1]) berarti X sesungguhnya tidak terdapat di dalam larik L.

3.       Pencarian Bagidua (Binary Search)

Pencarian bagidua atau pencarian biner adalah metode pencarian yang diterapkan pada sekumpulan data yang sudah terurut (terurut menaik atau terurut menurun). Data yang terurut syarat mutlak penerapan algoritma ini. Salah satu keuntungan data terurut adalah memudahkan pencarian, dalam hal ini pencarian bagidua.

ü  Contoh Program Sequential Search yaitu :

#include<iostream.h>

#define elemen 6

int mencari(int data[], int n, int x) {

             int iya, rd, down, rr, posisi;

             iya=0;  down=0;  rd=n-1;

             while (rd >= down)               {

             rr=(rd+down)/2;

             if (x > data[rr])

                             down=rr+1;

             else if (x < data [rr])

                             rd=rr-1;

             else         {

                             iya=1;

                             posisi=rr;

                             down=rd+1;  }  }

             if (!iya)

                             posisi=-1;

             return posisi;         }

void show(int data[], int n)   {

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

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

             cout<<endl;  }

void bubble(int data[], int n)   {

             for (int tahap=1; tahap<n; tahap++)   {

                             for(int j=0; j<n-tahap; j++)

                                             if (data[j]>data[j+1])  {

                                                             int tmp=data[j];

                                                             data[j]=data[j+1];

                                                             data[j+1]=tmp;   }    }   }

int main()  {

             int data[]= {2,1,9,4,3,7};

             bubble(data,elemen);

             cout<<"Hasil Pengurutan Data :"<<endl;

             show(data,elemen);

                             int find;

             cout<<"Input Data Yang Dicari : ";cin >>find;

             cout<<"Posisi "<<" "<<find<<" dalam array adalah : "

                             <<mencari(data, 6, find)<<endl;

             return 0;

}

Output dari program tersebut adalah :  Hasil Pengurutan Data : 1 2 3 4 7 9 Input  Data Yang DiCari :

III. QUEUE

Queue (Antrian) adalah list linier yang  :

1.      Dikenali elemen pertama (Head) dan elemen   terakhirnya (Tail)

2.      Aturan penyisipan dan penghapusan  elemennya           disefinisikan sebagai berikut :

·         Penyisipan selalu dilakukan setelah elemen terakhir

·         Penghapusan selalu dilakukan pada  elemen pertama

3.      Satu elemen dengan elemen lain dapat diakses  melalui informasi Next