Algoritma Pemrograman "Sorting"

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-metode sorting yaitu antara lain:
1.      Bubble Sort
2.      Quick Sort

• Bubble Sort adalah Metode pengurutan gelembung (Bubble Sort) ini terinspirasi oleh gelembung sabun yang berada di permukaan air. Karena berat jenis gelembung sabun yang lebih ringan ketimbang berat jenis air, maka gelembung sabun akan selalu terapung ke atas permukaan. Prinsip inilah yang dipakai pada algoritma pengurutan gelembung. Secara sederhana, bisa didefinisikan bahwa algoritma Bubble Sort adalah pengurutan dengan cara pertukaran data dengan data di sebelahnya secara terus menerus sampai pada satu iterasi tertentu dimana tidak ada lagi perubahan yang signifikan. 

Program Buble Sort :

#include<iostream>
using namespace std;

int main()
{
    int n, i,j;
    int data[20], buble, pilih;
    string yt;


    cout << " Banyak Data Yang Ingin dimasukkan : "; cin>>n;

    for (i=0; i<n; i++)
    {
         cout << " Masukkan Data Ke- " <<i+1<<" : "; cin>>data[i];
    }

    ulang:
    cout << " Pilih Cara Pengerjaan : " <<endl;
    cout << " 1. Ascending" <<endl;
    cout << " 2. Descending" <<endl;
    cout << " Masukkan Cara yang ingin dipilih : "; cin>>pilih;

    if (pilih==1)
    {
        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;
                }
            }
        }
                cout<<"Data yang telah diurutkan secara Ascending"<<endl;
                for(i=0; i<n; i++)
                {
                 cout << " Data ke- " <<i+1<< " : "<<data[i]<<endl;
                }
    }

    else if (pilih==2)
    {
        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;
              }
           }
        }
                cout<<"Data yang telah diurutkan secara Descending"<<endl;
                for(i=0; i<n; i++)
                {
                 cout << " Data ke- " <<i+1<< " : "<<data[i]<<endl;
                }
    }

     else
    {
      cout<<"Pilihan yang Anda Masukkan Salah."<<endl;
      cout<<"Jika ingin mengulang Pilih Y jika tidak pilih T : ";cin>>yt;
      cout<<endl;
      if(yt=="Y"||yt=="y")
      {
          goto ulang;
      }
      else
      {
          cout << "STOP"<<endl;
      }
    }
}

 

• Quick Sort Adalah Metode Quick sering disebut juga metode partisi (partition exchange sort). Metode ini diperkenalkan pertama kali oleh C.A.R. Hoare pada tahun 1962. Untuk mempertinggi efektifitas dari metode ini, digunakan teknik menukarkan dua elemen dengan jarak yang cukup besar. Proses penukaran dengan metode quick dapat dijelaskan sebagai berikut.: mula-mula dipilih data tertentu yang disebut pivot, misalnya x. Pivot dipilih untuk mengatur data di sebelah kiri agar lebih kecil daripada pivot dan data di sebelah kanan agar lebih besar daripada pivot. Pivot ini diletakkan pada posisi ke j sedemikian sehingga data antara 1 sampai dengan j-1 lebih kecil daripada x. Sedangkan data pada posisi ke j+1 sampai N lebih besar daripada x. Caranya dengan menukarkan data diantara posisi 1 sampai dengan j-1 yang lebih besar daripada x dengan data diantara posisi j+1 sampai dengan N yang lebih kecil daripada x. Ilustrasi dari metode quick dapat dilihat pada Gambar berikut: Gambar diatas menunjukkan pembagian data menjadi sub-subbagian. Pivot dipilih dari data pertama tiap bagian maupun sub bagian, tetapi sebenarnya kita bisa memilih sembarang data sebagai pivot. Dari ilustrasi diatas bisa kita lihat bahwa metode Quick Sort ini bisa kita implementasikan menggunakan dua cara, yaitu dengan cara non rekursif dan rekursif. Pada kedua cara diatas, persoalan utama yang perlu kita perhatikan adalah bagaimana kita meletakkan suatu data pada posisinya yang tepat sehingga memenuhi ketentuan diatas dan bagaimana menyimpan batas-batas subbagian. Dengan cara seperti yang diperlihatkan pada Gambar 6.1, kita hanya menggerakkan data pertama sampai di suatu tempat yang sesuai. Dalam hal ini kita hanya bergerak dari satu arah saja. Untuk mempercepat penempatan suatu data, kita bisa bergerak dari dua arah, kiri dan kanan. Caranya adalah sebagai berikut : misalnya kia mempunyai 10 data (N=9) 

12 35 9 11 3 17 23 15 31 20

 i=0                                                 j=9

Pertama kali ditentukan i=0 (untuk bergerak dari kiri ke kanan), dan j=N (untuk bergerak dari kanan ke kiri). Proses akan dihentikan jika nilai i lebih besar atau sama dengan j. Sebagai contoh, kita akan menempatkan elemen pertama, 12 pada posisinya yang tepat dengan bergerak dari dua arah, dari kiri ke kanan dan dari kanan ke kiri secara bergantian. Dimulai dari data terakhir bergerak dari kanan ke kiri (j dikurangi 1), dilakukan pembandingan data sampai ditemukan data yang nilainya lebih kecil dari 12 yaitu 3 dan kedua elemen data ini kita tukarkan sehingga diperoleh

3 35 9 11 12 17 23 15 31 20  

i=0                                         j=4  

Setelah itu bergerak dari kiri ke kanan dimulai dari data 3 (i ditambah 1), dilakukan pembandingan pada setiap data yang dilalui dengan 12, sampai ditemukan data yang nilainya lebih besar dari 12 yaitu 35. Kedua data kita tukarkan sehingga diperoleh

 3 12 9 11 35 17 23 15 31 20

 i=1                                         j=4  

Berikutnya bergerak dari kanan ke kiri dimulai dari 11. Dan ternyata data 11 lebih kecil dari 12, kedua data ini ditukarkan sehingga diperoleh

 3 11 9 12 35 17 23 15 31 20  

i=1                                        j=3  

Kemudian dimulai dari 9 bergerak dari kiri ke kanan. Pada langkah ini ternyata tidak ditemukan data yang lebih besar dari 12 sampai nilai i=j. Hal ini berarti proses penempata data yang bernilai 12 telah selesai, sehingga semua data yang lebih kecil dari 12 berada di sebelah kiri dan data yang lebih besar dari 12 berada di sebelah kanan seperti terlihat di bawah ini :

 

Pemrograman Quick Sort:

 #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);
}

 

Referensi: http://yuliana.lecturer.pens.ac.id/Struktur%20Data/PRAKTIKUM%202015/Praktikum%2013%20-%20Sorting%20Quick%20Sort.pdf