Kamis, 11 April 2019

Sorting Dalam Algoritma Pemrograman C++

| | 0 komentar

SORTING

TI Politala Algoritma Pemrograman 2B

Pengertian Sorting

Sorting adalah proses mengatur sekumpulan objek menurut aturan atau susunan tertentu. Urutan objek tersebut dapat menaik atau disebut juga ascending (dari data kecil ke data lebih besar) ataupun menurun/descending(dari data besar ke data kecil).
Metode Sorting :

  1. Bubble Sort (Metode Gelembung)
  2. Quick Sort atau Exchange Sort
  3. Merge Sort (Metode Penggabungan)
  4. Shell Sort 
  5. Insertion Sort (Metode Penyisipan)
  6. Selection Sort (Metode Seleksi)
Disini saya hanya akan membahas 3 metode yaitu Bubble Sort (Metode Gelembung),  Guick Sort atau Exchange Sort, dan Marge Sort (Metode Penggabungan).

Jenis-Jenis Metode Sorting

1.   Bubble Sort
      Merupakan metode sorting termudah, diberi nama “Bubble” karena proses pengurutan secara berangsur-angsur bergerak/berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda. Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar, jika pengurutan ascending. Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar, jika pengurutan descending. Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya. Kapan berhentinya? Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.
Pada gambar di atas, pengecekan dimulai dari data yang paling akhir, kemudian dibandingkan dengan data di depannya, jika data di depannya lebih besar maka akan ditukar.
Pada proses ke-2, pengecekan dilakukan sampai dengan data ke-2 karena data pertama pasting sudah paling kecil.
Untuk contoh program ini adalah
#include <iostream>
#include <conio.h>
using namespace std;
main()
{
     int nilai['n'];
     int temp;
     int n;
     cout<<"Banyak Data: "; cin>>n;
     cout<<endl;
     for (int a=1; a<=n; a++)
    {
         cout<<"nilai[“<<a<<“]: "; cin>>nilai[a];
    }
    cout<<"\n\n";
    cout<<"Data Sebelum diurutkan"<<endl;
    for(int a=1; a<=n; a++)
    {
         cout<<nilai[a]<<" ";
    }
    for(int a=n-1; a>=1; a--)
   {
        for(int b=1; b<=a; b++)
        {
              if(nilai[b]>nilai[b+1])
              {
                   temp=nilai[b+1];
                   nilai[b+1]=nilai[b];
                   nilai[b]=temp;
               }
          }
    }
    cout<<"\n\nData Setelah Diurutkan (Ascending)"<<endl;
    for (int a=1; a<=n; a++)
   {
        cout<<nilai[a]<<" ";
   }
   cout<<"\n\n";
   cout<<"\n\nData Setelah Diurutkan (Descending)"<<endl;
   for (int a=n; a>=1; a--)
   {
         cout<<nilai[a]<<" ";
   }
   getch();
}
Hasil Running :
2.   Quick Sort atau Exchange Sort
     Quick Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik pemecahan data menjadi partisi-partisi, sehingga metode ini disebut juga dengan nama partition exchange sort. Untuk memulai irterasi pengurutan, pertama-tama sebuah elemen dipilih dari data,  kemudian elemen-elemen data akan diurutkan diatur sedemikian rupa. Metode Quick sering disebut juga metode partisi (partition exchange sort). Metode ini mempunyai efektifitas yang tinggi dengan teknik menukarkan dua elemen dengan jarak yang cukup besar. Metode pengurutan quick sort dapat diimplementasikan dalam bentuk non rekursif dan rekursif. Berbagai varian dari quicksort pada intinya berupaya untuk mengembangkan teknik-teknik pembuatan partisi yang efektif untuk berbagai macam masukan.Hal ini merupakan bahan yang terus dipelajari hingga kini.Ditambah pula dengan perbaikan dari segi pemrograman sehingga lebih efisien (seperti mengurangi operasi pembandingan, pertukaran maupun perulangan).
     Sangat mirip dengan Bubble Sort, dan banyak yang mengatakan Bubble Sort sama dengan Exchange Sort. Perbedaan ada dalam hal bagaimana membandingkan antar elemen-elemennya. Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi elemen pusat (pivot). Sedangkan Bubble Sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen sebelum/sesudahnya itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.
untuk contoh program ini adalah
#include <iostream>
#include <conio.h>
using namespace std;
void tampilkan_data(int data[], int n)
{
     int i;
     for (i=1;i<=n;i++)
     cout<<data[i]<<" ";
     cout<<"\n";
}
int partisi (int data[], int awal, int akhir)
{
      int x,i,j,simpan;
      //www.nutekno.com
      i=awal;
      j=akhir;
while(1)
{
    while(data[i]<data[awal])
    i=i+1;
    while(data[j]>data[awal])
     j=j-1;
    if (i<j)
    {
        //tukarkan data
        simpan=data[i];
        data[i]=data[j];
        data[j]=simpan;
    }
   else
      return j;
   }
}
void quick_sort(int data[], int awal, int akhir)
{
      int q;
      if(awal<akhir)
   {
        q=partisi(data,awal,akhir);
        quick_sort(data,awal,q);
        quick_sort(data, q+1,akhir);
    }
}
int main()
{
    int i,j,n,data[100];
    cout<<"masukkan banyak data= ";cin>>n;
    for(i=1;i<=n;i++)
   {
         cout<<"data ke-"<<i<<" = ";cin>>data[i];
   }
   cout<<"Data sebelum diurut: "<<endl;
   for(j=1;j<=n;j++)
  {
       cout<<data[j]<<" ";
   }
   quick_sort(data,1,n);
    //hasil pengurutan
    cout<<endl<<endl;
    cout<<"hasil pengurutan:\n";
    tampilkan_data(data,n);
 getch();
}
Hasil Running :
3.   Merge Sort
Merge sort adalah algoritme divide-and-conquer berdasar kepada proses memecah list menjadi beberapa sublist hingga pada akhirnya tiap sublist hanya berisi satu elemen lalu sublist tersebut akan digabungkan dengan cara tertentu hingga list tersortir.
Konsep Dasar:
  • Membagi list acak menjadi NN sublist, masing-masing memiliki 11elemen.
  • Ambil sepasang list singleton dan gabungkan mereka menjadi list dengan 2 elemen. NN akan dikonversi menjadi N/2N/2 list dengan ukuran 2.
  • Ulangi proses ini hingga tersisa satu list yang sudah teratur.
Saat membandingkan dua sublist untuk digabungkan, elemen pertama pada kedua list akan dijadikan dasar pertimbangan. Saat melakukan penyortiran dengan urutan ascending, elemen dengan nilai yang lebih kecil akan menjadi elemen baru dari list tersortir. Prosedur ini diulangi hingga sublist yang lebih kecil kosong dan sublist hasil penggabungan baru memiliki semua elemen kedua sublist.
Sebagaimana yang dapat dipahami dari gambar di atas, pada setiap langkah, list dengan ukuran MM dibagi menjadi 22 sublist berukuran M/2M/2, hingga pembagian tidak dapat lagi dilakukan. Lebih mudahnya, diketahui terdapat array AA yang lebih kecil dengan elemen (9,7,8)(9,7,8).
Pada langkah pertama, list berukuran 33 dibagi menjadi 22 sublist dengan sublist pertama terdiri dari (9,7)(9,7) dan sublist kedua terdiri dari (8)(8). Sekarang, list pertama yang terdiri dari elemen (9,7)(9,7)dibagi lagi menjadi 22 sublist terdiri dari elemen (9)(9) dan (7)(7) secara berurutan.
Sublist tersebut tidak dapat dibagi lagi karena setiap sublist hanya memiliki 11 elemen, kini kita akan mulai menggabungkan list tersebut. 22 sublist yang terbentuk pada langkah terakhir akan digabungkan sesuai urutan menggunakan prosedur yang disebutkan di atas dan membentuk list baru (7,9)(7,9). Dengan melakukan backtracking, kita akan menggabungkan list yang berisi elemen (8)(8)dengan list ini, sehingga list baru yang tersortir terbentuk (7,8,9)(7,8,9).
Implementasi cara tersebut tersedia di bawah ini:
void merge(int A[ ] , int start, int mid, int end) 
{
    //menyimpan posisi awal kedua posisi awal kedua bagian dalam variabel temporer
    int p = start ,q = mid+1;
    int Arr[end-start+1] , k=0;
for(int i = start ;i &lt;= end ;i++)
{
     if(p &gt; mid)      //memeriksa apabila bagian pertama berakhir atau belum
     Arr[ k++ ] = A[ q++] ;
     else if ( q &gt; end)   //memeriksa apabila bagian kedua berakhir atau belum
     Arr[ k++ ] = A[ p++ ];
     else if( A[ p ] &lt; A[ q ])     //memeriksa bagian mana yang memiliki elemen yang lebih kecil
     Arr[ k++ ] = A[ p++ ];
     else
     Arr[ k++ ] = A[ q++];
 }
for (int p=0 ; p&lt; k ;p ++) 
{
    /* Sekarang array yang sebenarnya memiliki elemen yang tersortir untuk kedua bagian. */
    A[ start++ ] = Arr[ p ] ;                         
}
}
Di sini, pada fungsi merge, kita akan melakukan merge pada dua bagian array di mana satu bagian memiliki posisi dari awal hingga pertengahan dan bagian lain memiliki posisi mid+1 hingga akhir.
Awalan diambil dari bagian depan array, yaitu p dan q. Lalu elemen pada kedua bagian akan dibandingkan dan elemen dengan nilai yang lebih kecil akan disimpan di auxiliary array (Arr[ ]). Jika pada kondisi tertentu, salah satu bagian berakhir, maka semua elemen dari elemen yang satunya akan ditambahkan ke auxiliary array dengan urutan yang sama.
Amati 2 fungsi recursion bercabang berikut ini:
void merge_sort (int A[ ] , int start , int end )
{
     if( start &lt; end ) 
     {
           int mid = (start + end ) / 2 ;    // membagi array menjadi dua bagian
           merge_sort (A, start , mid ) ;  // menyortir bagian pertama array
           merge_sort (A,mid+1 , end ) ;// menyortir bagian kedua array
           // menyatukan kedua bagian dengan membandingkan elemen pada kedua bagian
          merge(A,start , mid , end );  
      }                   
}
untuk contoh program ini adalah
#include <iostream>
#include <conio.h>
using namespace std;
int a[50];
void merge(int,int,int);
void merge_sort(int low,int high)
{
     int mid;
     if(low<high)
     {
          mid=(low+high)/2;
          merge_sort(low,mid);
          merge_sort(mid+1,high);
          merge(low,mid,high);
     }
}
void merge(int low,int mid,int high)
{
     int h,i,j,b[50],k;
     h=low;
     i=low;
     j=mid+1;
    while((h<=mid)&&(j<=high))
    {
         if(a[h]<=a[j])
         {
              b[i]=a[h]; h++;
          }
         else
         {
              b[i]=a[j]; j++;
          } i++;
     }
 if(h>mid)
 {
       for(k=j;k<=high;k++)
       {
            b[i]=a[k]; i++;
        }
  }
        else
       {
             for(k=h;k<=mid;k++)
             {
                  b[i]=a[k]; i++;
              }
        }
              for(k=low;k<=high;k++)
              a[k]=b[k];
        }
main()
{
 int num,i;
 cout<<"*******************************************************************"<<endl;
 cout<<"                         MERGE SORT PROGRAM "<<endl;
 cout<<"*******************************************************************"<<endl;
 cout<<endl<<endl;
 cout<<"Masukkan Banyak Bilangan : ";cin>>num;
   cout<<endl;
 cout<<"Sekarang masukkan "<< num <<" Bilangan yang ingin Diurutkan :"<<endl;
 for(i=1;i<=num;i++)
 {
  cout<<"Bilangan ke-"<<i<<" : ";cin>>a[i] ;
 }
 merge_sort(1,num);
 cout<<endl;
 cout<<"Hasil akhir pengurutan : "<<endl;
 cout<<endl;
 for(i=1;i<=num;i++)
  cout<<a[i]<<" ";
 cout<<endl<<endl<<endl<<endl;
   getch();

}
Hasil Running :

DAFTAR PUSTAKA


Read more...

Jumat, 22 Maret 2019

Queue Dalam Algoritma Pemrograman C++

| | 0 komentar

QUEUE

TI Politala Algoritma Pemrograman 2B

A. Pengertian Queue


     Queue dalam struktur data atau yang diartikan sebagai antrian merupakan sekumpulan data dimana saat menambahkan elemen hanya bisa dilakukan pada suatu ujung disebut sisi belakang (rear) dan penghapusan (pengambilan elemen) dilakukan lewat ujung lain/sisi depan(front). Berbeda dengan stack yang bersifat LIFO maka queue bersifat FIFO (First In First Out), yaitu data yang pertama masuk maka akan menjadi yang pertama kali keluar begitu pun sebaliknya.
       Tumpukan disebut juga dengan "Waiting Line" yaitu suatu penambahan elemen baru dilakukan pada bagian belakang dan penghapus elemen dilakukan dilakukan pada bagian depan. Elemen-elemen dicdalam antrian dapat bertipe integer, real, record dalam bentuk sederhana atau terstruktur. Queue merupakan salah satu contoh aplikasi dari pembuatan double linked list yang cukup sering ditemui di kehidupan sehari-hari, midalnya saat pengantrian tiket. Istilah yang cukup sering dipakai adalah enqueue yaitu apabila seseorang masuk dalam sebuah antrian. Sedangkan dequeue adalah istilah yang dipakai saat seseorang keluar dari antrian.

B.  Deklarasi Queue dengan Array

      Proses pendeklarasian antrian adalah proses pembuatan struktur antrian dalam memori. Struktur antrian terdiri dari data dalam array, head untuk menunjukkan ujung dari antrian dan tail untuk menunjukkan akhir dari antrian.
#define MAX 5
#include <iostream>
using namespace std;
typedef struct
{
    int data [MAX];
    int head;
    int tail;
}Queue;

C. Inisialisasi Queue

     Inisialisasi antrian adalah proses pembuatan suatu antrian kosong. Proses inisialisasi untuk antrian yang menggunakan array adalah dengan mengisi nilai field head dan tail dengan nilai 0 (nol) jika elemen pertama diawali dengan nomor 1. Kalau elemen pertama array dimulai dengan nilai 0 (nol) maka head dan tail diisi dengan nilai -1.
void Create()
{
    antrian.head=antrian.tail=-1;
}

D. Operasi-Operasi pada Queue

1. Create Queue (Q)
    Untuk menciptakan dan menginisialisasi Queue, dengan cara membuat Head dan Tail = -1
    Berikut deklarasi prosedur create pada queue :
    void create()
   {
       antrian.HEAD = -1;
       antrian.TAIL = -1;
    }

2. Make NullQ (Q)
    Mengosongkan antrian Q, jika ada elemen maka semua elemen dihapus.

3. EnQueue
    Untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu ditambahkan di elemen paling belakang. Penambahan elemen selalu menggerakan variabel Tail dengan cara increment counter Tail terlebih dahulu.
    Berikut deklarasi prosedur EnQueue:
    void enqueue()
   {
       if (IsEmpty())
       {
           antrian.HEAD=antrian.TAIL=0;
           cout<<”Masukkan data : “;
           cin>>antrian.data[antrian.TAIL];
        }
       else
       if(IsFull())
      {
          cout<<”ANTRIAN SUDAH PENUH!”;
      }
   }

4. DeqQueue
   Digunakan untuk menghapus elemen terdepan/pertama (head) dari Antrian. Dengan cara menggeser semua elemen antrian kedepan dan mengurangi Tail dgn 1. Penggeseran dilakukan dengan menggunakan looping.
      Berikut deklarasi fungsi DeQueue:
      int Dequeue()
     {
          int i;
          int e = antrian.data[antrian.HEAD];
          for(i=antrian.HEAD;i<=antrian.Tail-1;i++)
         {
                antrian.data[i]=antrian.data[i+1];
          }Antrian.TAIL--;
          Return e;
      }

5. Clear
     Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan Head = -1
Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus arraynya, namun hanya mengeset indeks pengaksesan-nya ke nilai -1 sehingga elemen-elemen Antrian tidak lagi terbaca.
     Berikut deklarasi fungsi clear:
     void clear()
    {
         antrian.HEAD = -1;
         antrian.TAIL = -1
         cout<<"Antrian sudah dikosongkan! ";
     }

6. IsEmpty
    Untuk memeriksa apakah Antrian sudah penuh atau belum. Dengan cara memeriksa nilai Tail, jika      Tail = -1 maka empty. Kita tidak memeriksa Head, karena Head adalah tanda untuk kepala antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah. Pergerakan pada Antrian terjadi dengan penambahan elemen Antrian kebelakang, yaitu menggunakan nilai Tail.
    Berikut deklarasi fungsi IsEmpty :
    int IsEmpty()
   {
       if (antrian.HEAD=antrian.TAIL==-1)
      {
       return 1;
       }
       else
      {
       return 0;
       }
    }

7. IsFull
    Untuk mengecek apakah Antrian sudah penuh atau belum
    Dengan cara mengecek nilai Tail, jika Tail >= MAX-1 (karena MAX-1 adalah batas elemen array        pada C) berarti sudah penuh.
    Berikut deklarasi fungsi IsFull :
    int IsFull()
   {
       if (antrian.TAIL == max-1)
      {
          return 1;
      }
      else
     {
          return 0;
      }
   }

Contoh Program Queue



DAFTAR PUSTAKA

http://atokise.blogspot.com/2016/11/program-queue.html
http://suputradwipratama274.blogspot.com/2015/06/penjelasan-tentang-queue-contoh-program.html
http://sekilaslihat.blogspot.com/2015/06/rangkuman-materi-queue.html
http://blog-arul.blogspot.com/2012/01/queue-pada-struktur-data.html
https://blognyonyait.blogspot.com/2017/05/makalah-sistem-antrian-queue-dengan.html

Read more...

Stack Dalam Algoritma Pemrograman C++

| | 0 komentar

TI Politala Algoritma Pemrograman 2B

A. Pengertian Stack (Tumpukan)

    Stack (tumpukan) merupakan sebuah cara dalam mengorganisasikan data-data yang dimiliki. Stack digunakan sebagai penyimpanan data di dalam memori. Stack merupakan suatu tumpukan dari benda dengan konsep utamanya adalah LIFO (Last In First Out). Dalam artian benda yang masuk terakhir dalam stack akan menjadi benda pertama yang dikeluarkan dari stack.

B. Operasi Dasar Stack

Ada beberapa operasi-operasi dalam stack:
1. Push yaitu  untuk menambahkan item pada tumpukan paling atas.
    Langkah-langkah operasi stack yaitu:
    a. Memeriksa tumpukan apakah penuh atau tidak
   b. Jika tumpukan penuh dan tak ada ruang untuk memasukkan data, maka cukup tampilkan pesan bahwa tumpukan sudah penuh.
    c. Jika tumpukan tidak penuh dan masih ada ruang, maka tambahkan satu nilai pada tumpukan atas (top) untuk menunjukkan ke ruang kosong selanjutnya.
    d. Tambahkan data pada ruang kosong yang ditunjukan oleh top
    Contoh potongan program operasi push
    If (top < n-1)
   { 
       top = top + 1;
       S[top] = x;
    }
    Else
   {
       Cout<<”stack Penuh”;
   }

2. Pop yaitu untuk  mengambil item yang paling atas.
    Langkah-langkah operasi pop yaitu:
    a. Memeriksa tumpukan apakah kosong atau tidak
   b. Jika tumpukan kosong dan sudah tidak ada data untuk dihapus, maka cukup tampilkan pesan bahwa tumpukan kosong
    c. Jika tumpukan tidak kosong, maka akses data yang paling atas (top).
    d. Kemudian kurangi nilai dengan petunjuk dari top
    Contoh potongan program operasi pop :
    If (top > -1)
    { 
        x = S[top];
        Top= top-1;
     }
    Else
    {
        Cout<<”stack kosong”;
     }
3. Clear yaitu untuk mengosongkan stack.
4. IsEmpty yaitu fungsi yang digunakan untuk mengecek apakah stack sudah kosong. IsFull yaitu fungsi yang digunakan untuk mengecek apakah stack sudah penuh.
5. Selain operasi-operasi diatas, ada operasi lain yang dapat terjadi dalam stack yaitu:
6. Proses deklarasi yaitu proses pendeklarasian stack.
7. Proses inisialisasi yaitu proses pembuatan stack kosong, biasanya dengan pemberian nilai untuk top.

C. Program STACK

1.  Untuk mendeklarasikan program stack pada c++, dibutuhkan 3 metode yaitu fungsi push( );, pop( );, dan printStack( ); untuk menampilkan data yang ditumpukkan.
2. Selain fungsi diatas, buat 2 fungsi opsional untuk mengecek apakah tumpukan kosong isEmpty( ) dan tumpukan penuh isFull( ).
3. Untuk menyimpan data dapat menggunakan empety array dengan maksimum array yang akan didefinisikan sebagai maksimum tumpukan.
4. Agar data tumpukkan terstruktur kita bisa menggunakan struct sehingga mudah mengakses data top dan array data seperti sebuah object.
5. Karena merupakan program konsole maka juga akan dibuat fungsi main( ).

Contoh Program Stack
#include <iostream>
using namespace std;
#define MAXSTACK 5
typedef struct
{
    char item [MAXSTACK];
    int top;
}stack;
void InisialsasiStack (stack &s)
{
    s.top = 0;
}
int IsFull(stack &s)
{
    if (s.top == MAXSTACK)
        return 1;
    else
        return 0;
}
bool push (stack &s, char c)
{
    if (IsFull(s))
    {
        cout<<" Stack Penuh"<<endl;
        return 1;
    }
    else
    {
        s.top++;
        s.item[s.top]=c;
        return 0;
    }
}
bool IsEmpty(stack &s)
{
    if (s.top == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}
char pop (stack &s)
{
    char c =' ';
    if (!IsEmpty(s))
    {
        c = s.item[s.top];
        s.item[s.top]=' ';
        s.top=s.top-1;
    }
    return c;
}
int main()
{
    stack stack;
    InisialsasiStack(stack);
    push(stack, 'A');
    push(stack, 'D');
    push(stack, 'F');
    push(stack, 'C');
    push(stack, 'A');
    push(stack, 'X');
    push(stack, 'Y');
    push(stack, 'Z');
    cout<<" Urutan teratas     : "<<stack.top<<endl;
    cout<<" Isi urutan teratas : "<<stack.item[stack.top]<<endl;
    cout<<" Urutan yang keluar : "<<pop(stack)<<endl;
    return 0;
}
Hasil Running :

Download juga contoh program Stack lainya pada link dibawah ini :

DAFTAR PUSTAKA

http://www.klikartikel.com/2014/12/mengenal-stack-pada-c.html
https://bekti.net/blog/implementasi-stack-di-cpp/
https://primaangelsnote.blogspot.com/2019/03/algoritma-dan-pemrograman-2-stuck.html
Read more...
animasi  bergerak gif

Popular Posts

Blogger templates

Blogroll

About

Diberdayakan oleh Blogger.

Cari Blog Ini

Postingan lain

Translate

Blogger templates

Pages

Pages

Popular Posts

 

Designed by: Compartidísimo
Images by: DeliciousScraps©