Jumat, 22 Juli 2016

Macam-Macam Sorting

Bubble Sort

Bubble sort adalah salah satu teknik sorting (pengurutan) data. Pengurutan menggunakan Bubble Sort ini sangat mudah untuk dipahami dan diprogramkan, namun dari semua metode pengurutan, metode Bubble Sort ini merupakan yang paling tidak efisien.
Pengurutan data Bubble Sort dilakukan dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Jika elemen sekarang lebih besardari elemen berikutnya maka kedua elemen tersebut ditukar (untuk pengurutan ascending). Jika elemen sekarang lebih kecildari elemen berikutnya, maka kedua elemen tersebut ditukar (untuk 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, demikianseterusnya. 
Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.
 
Contoh pengurutan data yang dilakukan dengan metode bubble sort sebagai berikut :

Proses 1 :
22 10 15 3 8 2
22 10 15 3 2 8
22 10 15 2 3 8
22 10 2 15 3 8
22 10 2 15 3 8

22 2 10 15 3 8
2 22 10 15 3 8
Pengecekan dimulai dari data yang paling akhir, kemudian dibandingkan dengan data di depannya,jika data didepannya lebih besar maka akan di tukar.
Proses 2:
2 22 10 15 3 8
2 22 10 15 3 8
2 22 10 3 15 8
2 22 3 10 15 8
2 3 22 10 15 8

pengecekan dilakukan sampai dengan data ke-2 karena data pertama pasti sudah paling kecil.

Proses 3 :
2 3 22 10 15 8
2 3 22 10 8 15
2 3 22 8 10 15
2 3 8 22 10 15

Proses 4 :
2 3 8 22 10 15
2 3 8 22 15 10
2 3 8 15 22 10

Proses 5 :
2 3 8 15 22 10
2 3 8 15 10 22

Pengurutan berhenti.
berikut programnya c++ bubble sort:
 
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>

bubble_acak()
{
    clrscr();
    int arr[1000];
    int x, i; //untuk array
   int s, t, temp; //untuk sorting

   //input jumlah data yang diproses
   cout<<"angka yang akan dimasukkan : "; cin>>x;

   //input nilai masing" array
   srand(time(NULL));
   for (i=0; i<x; i++)
      arr[i] = rand() %1000;

   //output nilai" array
   clrscr();
   cout<<"====== array ======"<<endl<<endl;
    cout<<"angka angkanya :"<<endl;
   for (i=0; i<x; i++)
      cout<<arr[i]<<", ";


   //sorting
   cout<<endl<<endl<<endl<<endl;
   cout<<"====== sorting ======"<<endl<<endl;
   s = 0;
   for (s=0; s<x; s++)
       {
      for (t = s+1; t<x; t++)
         {
              if (arr[s]>arr[t])
             {
               temp = arr[s];
                    arr[s] = arr[t];
                 arr[t] = temp;
             }
         }
      }
   cout<<"setelah sorting :"<<endl;
   for (i=0; i<x; i++)
      cout<<arr[i]<<", ";

   getch();
}


bubble_manual()
{
    clrscr();
    int arr[1000];
    int x, i; //untuk array
   int s, t, temp; //untuk sorting

   //input jumlah data yang diproses
   cout<<"angka yang akan dimasukkan : "; cin>>x;

   //input nilai masing" array
   for (i=0; i<x; i++)
       {
      cout<<"masukkan angka ke-"<<i<<" : ";
      cin>>arr[i];
      }

   //output nilai" array
   clrscr();
   cout<<"====== array ======"<<endl<<endl;
    cout<<"angka angkanya :"<<endl;
   for (i=0; i<x; i++)
      cout<<arr[i]<<", ";


   //sorting
   cout<<endl<<endl<<endl<<endl;
   cout<<"====== sorting ======"<<endl<<endl;
   s = 0;
   for (s=0; s<x; s++)
       {
      for (t = s+1; t<x; t++)
         {
              if (arr[s]>arr[t])
             {
               temp = arr[s];
                    arr[s] = arr[t];
                 arr[t] = temp;
             }
         }
      }
   cout<<"setelah sorting :"<<endl;
   for (i=0; i<x; i++)
      cout<<arr[i]<<", ";

   //mission complete
   getch();
}


main ()
{
    int pilih;
   char ulang;

   do
   {
      clrscr ();
       cout<<"tekan 1 : bilangan yang disorting dimasukan secara acak"<<endl;
       cout<<"tekan 2 : bilangan yang disorting dimasukan secara manual"<<endl;
       cout<<"masukkan pilihan : "; cin>>pilih;

      switch (pilih)
      {
          case 1:
             bubble_acak();
         break;

         case 2:
             bubble_manual();
         break;

         default:
            clrscr();
            cout<<"\"maaf\""<<endl;
             cout<<"\"pilihan yang dimasukkan salah\"";
         break;
      }
      cout<<endl<<endl<<"tekan \"Y\" lalu \"ENTER\" untuk ulang ---> "; cin>>ulang;
   }
   while (ulang=='Y');
}

Selection Sort

Selection Sort merupakan kombinasi antara sorting dan searching. Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array. Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]). Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

Proses Selection Sort :




 
Prosedur selection Sort



void selection_sort (int data[])
{
for(int i=0;i<n-1;i++)
{
pos=i;
for(int j=i+1;j<n;j++)
{
if (data[j]<data[pos] pos=j; //ascending
}
if(pos!=i) tukar(&data[pos],&data[i]);
}
}

Insertion Sort

Insertion Sort jika dibandingkan menggunakan kartu remi. Seperti ketika Anda mengambil setiap kartu, kemudian Anda masukkan kartu ke posisi yang benar di tangan anda hingga terorganisir urutannya dengan rapi. Insertion Sort membagi array menjadi dua sub-array. Array sub pertama(diibaratkan kartu yang ditangan anda) yang diurutkan dan peningkatan ukuran dan semacamnya. Sub array kedua(seperi kartu yang akan diambil) kartu yang belum terurutkan, mengandung semua elemen yang belum dimasukkan ke dalam array sub pertama dan berkurang sesuai ukuran.

Contoh source code untuk Insertion Sort yang diterapkan di C++, menggunakan compiler Borland C++ 5.02 :
 
#include<iostream.h>
#include<conio.h>
main()
{
 int x,a[100],i,t,j,k;

 cout<<"Insertion Sort - Desc\n";
   cout<<"Masukkan banyak bilangan = ";cin>>x;
   for(i=1;i<=x;i++)
   {
    cout<<"\n Bilangan ke-"<<i<<" : ";cin>>a[i];
   }
   cout<<"\n\n data Sebelum diurutkan :";
   for(i=1;i<=x;i++)
   {
    cout<<"  "<<a[i];
   }
   cout<<endl;
   for(i=1;i<=x;i++)
   {
    for(j=1;j<=i;j++)
    {
       if(a[i]>a[j])
         {
          t=a[i];
            a[i]=a[j];
            a[j]=t;
         }
      }
      cout<<"\n # "<<i<<" : ";
      for(k=1;k<=i;k++)
      {
       cout<<"  "<<a[k];
      }
   }
   cout<<"\n\n data Setelah diurutkan secara descending : ";
   for(i=1;i<=x;i++)
   {
    cout<<"  "<<a[i];
   }
 getch();
}
 
Hasilnya adalah : 
 
 

Shell Sort

Tingkat kehandalan suatu algoritma, diukur berdasarkan seberapa baik algoritma itu melakukan pengurutan, dan seberapa cepat prosesnya dilakukan. Shell Sort, salah satu algoritma pengurutan yang lebih handal dibandingkan Selection Sort dan Bubble Sort.
Kehandalannya yaitu : “Membagi deret data menjadi dua bagian. Masing-masing bagian diurutkan menggunakan Bubble Sort. Tidak menggunakan iterasi melainkan increment. Perulangan diakukan sesuai nilai increment.”
 
 
Visualisasi Algoritma nya :



Quick Sort


Salah satu algoritma yang menggunakan paradigma Divide and Conquer adalah Algoritma Quick  Sort. Algoritma ini mengambil salah satu elemen secara acak (biasanya dari tengah) yang disebut dengan pivot  lalu menyimpan semua elemen yang lebih kecil di sebelah kiri pivot  dan semua elemen yang lebih besar di sebelah kanan pivot. Hal ini dilakukan secara rekursif terhadap elemen di sebelah kiri dan kanannya sampai semua elemen sudah terurut.
Ide dari algoritma ini adalah sebagai berikut:
  1. Pilih satu elemen secara acak sebagai pivot
  2. Pindahka semua elemen yang lebih kecil ke sebelah kiri pivot dan semua elemen yang lebih besar ke sebelah kanan pivot. Elemen yang nilainya sama bisa disimpan di salah satunya.
  3. Lakukan sort secara rekursif terhadap sub-array sebelah kiri dan kanan pivot

Berikut ini implementasi Algoritma Quick Sort menggunakan C++ dengan Tool yang digunakan Code Block 8.02 :

#include <iostream>
#define n 20
using namespace std;
int Ar[n];
void quickSort(int arr[], int left, int right);
int main()
{   int jumlahBil=5;
cout<<”Masukkan jumlah bilangan dalam arry [Maksimal 20]“<<endl;
cin>>jumlahBil;
int Ar[jumlahBil];
for(int i=0; i<jumlahBil;i++)
{
cout<<”Bilangan ke-”<< i+1 << endl;
cin>>Ar[i];
}
quickSort(Ar,0,jumlahBil-1 );
cout<<”Data yang telah diurutkan”<<endl;
for(int i=0; i<jumlahBil;i++)
{
cout<<Ar[i]<<”\n”;
}
}
void quickSort(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j–;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j–;
}
};
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}


Merge Sort

erge sort merupakan algoritma pengurutan dalam ilmu komputer yang dirancang untuk memenuhi kebutuhan pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori komputer karena jumlahnya yang terlalu besar. Algoritma ini ditemukan oleh John von Neumann pada tahun 1945.
Prinsip utama yang diimplementasikan pada algoritma merge-sort seringkali disebut sebagai pecah-belah dan taklukkan ( 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.
 
Contoh Koding nya :
#include <stdio.h>
#define MAX 10
int Data[MAX];
int temp[MAX];
// Prosedur merge sort
void merge(int Data[], int temp[], int kiri, int tengah, int kanan)
{
            int i, left_end, num_elements, tmp_pos;
            left_end = tengah - 1;
            tmp_pos = kiri;
            num_elements = kanan - kiri + 1;
            while ((kiri <= left_end) && (tengah <= kanan))
            {
                        if (Data[kiri] <= Data[tengah])
                        {
                                    temp[tmp_pos] = Data[kiri];
                                    tmp_pos = tmp_pos + 1;
                                    kiri = kiri +1;
                        }
                        else
                        {
                        temp[tmp_pos] = Data[tengah];
                        tmp_pos = tmp_pos + 1;
                        tengah = tengah + 1;
                        }
            }
            while (kiri <= left_end)
            {
                        temp[tmp_pos] = Data[kiri];
                        kiri = kiri + 1;
                        tmp_pos = tmp_pos + 1;
            }
            while (tengah <= kanan)
            {
                        temp[tmp_pos] = Data[tengah];
                        tengah = tengah + 1;
                        tmp_pos = tmp_pos + 1;
            }
            for (i=0; i <= num_elements; i++)
            {
                        Data[kanan] = temp[kanan];
                        kanan = kanan - 1;
            }
}
// Prosedur membuat kumpulan data
void m_sort(int Data[], int temp[], int kiri, int kanan)
{
            int tengah;
            if (kanan > kiri)
            {
                        tengah = (kanan + kiri) / 2;
                        m_sort(Data, temp, kiri, tengah);
                        m_sort(Data, temp, tengah+1, kanan);
                        merge(Data, temp, kiri, tengah+1, kanan);
            }
}
void mergeSort(int Data[], int temp[], int array_size)
{
            m_sort(Data, temp, 0, array_size - 1);
}
int main()
{
            int i;
            printf("Masukkan DATA SEBELUM TERURUT : \n");
            for (i = 0; i < MAX; i++)
            {
                        printf ("Data ke %i : ", i+1);
                        scanf ("%d", &Data[i]);
            }
            mergeSort(Data, temp, MAX);
            printf("\nDATA SETELAH TERURUT : ");
            for (i = 0; i < MAX; i++)
            printf("%d  ", Data[i]);
            printf("\n");
            //scanf("%d");
            return(0);
};
 
Dan Hasilnya :
 
Sumber : http://novianiusrickywijaya.blogspot.co.id/2013/02/macam-macam-sorting.html
Diposting oleh di Tidak ada komentar:
Langganan: Postingan (Atom)