Buble Sort dan Quick Sort C++

kali ini kita akan membahas metode pengurutan mengenai Algoritma Buble Sort dan Quick Sort :

1.  Buble Sort

Pengurutan merupakan proses dasar yang ada dalam algoritma dan stuktur data. Terdapat banyak algoritma pengurutan yang sering digunakan, namun pada tulisan kali ini akan dibahas mengenai dasar algoritma Bubble Sort. Algortima ini merupakan algortima pengurutan sederhana dan biasanya dipelajari sebagai pokok bahasan seputar pengurutan.

Algoritma Bubble Sort ini merupakan proses pengurutan yang secara berangsur-angsur berpindah ke posisi yang tepat karena itulah dinamakan Bubble yang artinya gelembung. Algoritma ini akan mengurutkan data dari yang terbesar ke yang terkecil (ascending) atau sebaliknya (descending).

Secara sederhana, bisa didefenisikan algoritma Bubble Sort adalah pengurutan dengan cara pertukaran data dengan data disebelahnya secara terus menerus sampai dalam satu iterasi tertentu tidak ada lagi perubahan.

Untuk belajar algoritma Bubble Sort ini kita hanya perlu memahami cara yang digunakan untuk mengurutkan data, sederhananya algoritma ini menggunakan perbandingan dalam operasi antar elemennya. Di bawah ini merupakan gambaran dari algoritma Bubble Sort dengan array “3 1 4 2 8”.

Proses pertama

(3 1 4 2 8) menjadi (1 3 4 2 8)

(1 3 4 2 8) menjadi (1 3 4 2 8)

(1 3 4 2 8) menjadi (1 3 2 4 8)

(1 3 2 4 8) menjadi (1 3 2 4 8)

Proses kedua

(1 3 2 4 8) menjadi (1 3 2 4 8)

(1 3 2 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

Proses ketiga

(1 2 3 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

(1 2 3 4 8) menjadi (1 2 3 4 8)

Jika kita perhatikan proses diatas, para proses kedua data sudah terurut dengan benar. Tetapi algoritma Bubble Sort tetap berjalan hingga proses kedua berakhir. Proses ketiga masih terus berjalan karena pada algoritma Bubble Sort maksud terurut itu adalah tidak ada satupun penukaran pada suatu proses. Proses ketiga ini dilakukan untuk verifikasi data.

Algoritma Bubble Sort ini mempunyai kelebihan dan kekurangan, untuk kelebihannya metode ini merupakan metode paling sederhana untuk mengurutkan data. Selain sederhana, algoritma Bubble Sort mudah dipahami. Sementara itu, kekurangannya terletak pada efisiensi.

             Bubble Sort ini merupakan metode pengurutan yang tidak efisien karena ketika mengurutkan               data yang sangat besar akan sangat lambat prosesnya. Selain itu, jumlah pengulangan akan                   tetap sama jumlahnya meskipun data sudah cukup terurut.

 Listing program

#include <iostream>
using namespace std;
int main()
{
    char pil,sl;
    int i,n,j,Buble;
    int data[10];
    up:
    cout<<"Masukkan Jumlah Data : ";cin>>n;
    for(i=0; i<n; i++)
    {
        cout<<"Data ke - "<<i+1<<" : " ; cin >>data[i];
    }
    up1:
    cout <<"Pilih Urutan Data "<<endl;
    cout <<"1. Ascending "<<endl;
    cout <<"2. Descending"<<endl;
    cout <<"Pilihan Pencarian(1/2) : "; cin >>pil;
    if(pil =='1')
    {
        cout<<"Anda Memilih Urutan Data Ascending "<<endl;
        for(i=0; i<=n-2; i++)
        {
            for(j=n-1; j>=i+1; j--)
            {
                if (data[j]<data[j-1])
                {
                    Buble = data [j];
                    data[j] = data[j-1];
                    data[j-1]=Buble;
                }
            }
        }
    }
    else if(pil =='2')
    {
        cout<<"Anda Memilih Urutan Data Descending "<<endl;
        for(i=0; i<=n-2; i++)
        {
            for(j=n-1; j>=i+1; j--)
            {
                if (data[j]>data[j-1])
                {
                    Buble = data [j];
                    data[j] = data[j-1];
                    data[j-1]=Buble;
                }
            }
        }
    }
    else
    {
        cout<<"Anda Salah Menginputkan Pilihan!!!"<<endl;
        goto up1;
    }
    for(i=0; i<n; i++)
        {
            cout<<data[i]<<"   ";
        }
    cout<<endl;
    cout<<"apakah anda ingin memasukkan data lagi ?[Y/T] : ";cin>>sl;
    if(sl=='Y' || sl=='y')
    {
        goto up;
    }
    else if (sl == 'T' || sl == 't')
    {
        return 0;
    }

}

2. Quick Sort

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

Pada algoritma quick sort, pemilihan pivot ialah hal yang menentukan apakah algoritma quick sort tersebut akan memberikan performa terbaik atau terburuk. Berikut beberapa cara pemilihan pivot :

1. Pivot merupakan elemen pertama, elemen terakhir, atau elemen tengah dalam array. Cara ini bagus jika elemen tabel tersusun secara acak, tetapi sebaliknya atau tidak bagus jika elemen tabel semula sudah terurut.
2. Pivot dipilih dengan cara acak dari salah satu elemen array. Cara ini baik tapi belum tentu maksimal, sebab diperlukan prosedur khusus untuk menentukan pivot secara acak.
3. Pivot adalah elemen median tabel. Cara ini yaitu cara paling bagus, sebab pada hasil partisi menghasilkan dua bagian tabel yang berukuran seimbang. Juga cara ini memberikan kompleksitas waktu yang minimum. Masalahnya, mencari median dari elemen tabel yang belum terurut adalah persoalan tersendiri

 Listing Program

#include <iostream>
#include <conio.h>
using namespace std;
void quick_sort(int arr[], int left, int right)
{
      int i = left, j = right;int tmp;
      int pivot = arr[(left+right)/2];/* partition */
  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--;
                                                    };
         }; /* recursion */
      if (left < j)
            quick_sort(arr, left, j);
      if (i < right)
            quick_sort(arr, i, right);
}
int main()
{
int i,n,data[50];
cout<<"Masukan banyak data: ";cin>>n;
for(i=0;i<n;i++)
{cout<<"Masukan data ["<<i<<"] : ";cin>>data[i];}
cout<<"\nData sebelum diurutkan: "<<endl;
for(i=0;i<n;i++)
{
cout<<data[i]<<" ";
}cout<<"\n";
quick_sort(data,0,n-1);//hasil pengurutan
cout<<"\nHasil pengurutan:\n";
{
int i;
for (i=0;i<n;i++)
cout<<data[i]<<" ";
cout<<"\n";
}getch();
}