Definisi Sorting (Pengurutan) dan BUBBLE SORT

SORTING (PENGURUTAN)

-> Sorting (pengurutan) adalah proses mengatur sekumpulan objek menurut urutan atau susunan tertentu. 

Masalah pengurutan dapat ditulis menjadi 2 jenis, yaitu:

1. Ascending (Tersusun / terurut secara menaik)

Diberikan larik L dengan n elemen yang sudah terdefinisi elemen-elemennya.

Urutan larik tersebut sehingga tersusun secara menaik (dari urutan nilai terkecil ke urutan nilai terbesar), yaitu: L[0] ≤ L[1] ≤ L[2] ≤ ... ≤ L[n-1]

2. Descending (Tersusun / terurut secara menurun)

Diberikan larik L dengan n elemen yang sudah terdefinisi elemen-elemennya.

Urutan larik tersebut sehingga tersusun secara menurun (dari urutan nilai terbesar ke urutan nilai terkecil), yaitu: L[0] ≥ L[1] ≥ L[2] ≥ ... ≥ L[n-1]

Contoh data yang belum terurut : 70, 12, 45, 10, 11, 60, 13, 33, 50

Ascending = 10, 11, 12, 13, 33, 45, 50, 60, 70

Descending = 70, 60, 50, 45, 33, 13, 12, 11, 10

*Pengurutan dikatakan STABIL, jika dua atau lebih data yang sama (identik) tetap pada urutan yang sama setelah pengurutan. Misalnya didalam sekelompok data integer berikut terdapat 3 buah nilai 12 (diberi tanda petik ', '', ''' untuk mengidentifikasi urutannya.

Contoh : 70, 12', 45, 10, 12'', 60, 12''', 33, 50

Dikatakan STABIL jika hasil pengurutannya menjadi : 10, 12', 12'', 12''', 33, 45, 50, 60, 70

Dikatakan TIDAK STABIL jika hasil pengurutannya menjadi : 10, 12'', 12', 12''', 33, 45, 50, 60, 70

ALGORITMA SORTING (PENGURUTAN)

-----------------------------------------------------------

Macam-macam algoritma sorting (pengurutan), yaitu:

1. Bubble Sort

2. Selection Sort

3. Insertion Sort

4. Heap Sort

5. Shell Sort

6. Quick Sort

7. Merge Sort

8. Radix Sort

9. Tree Sort 

Tetapi kali ini eta hanya akan membahas Bubble Sort saja, karena itulah tugas yang harus dikumpul kali ini *hahaha*

1. BUBBLE SORT

Diberi nama "bubble" karena proses pengurutan secara berangsur-angsur bergerak / berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelar 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 (untuk pengurutan ascending). 

- Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar (untuk pengurutan descending).

Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau dari kiri ke kanan, tergantung jenis pengurutannya. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya.

Bubble Sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapainya perurutan yang telah diinginkan.

Algoritma Bubble Sort beroperasi sebagai berikut :

1. Membandingkan data ke-i dengan data ke-(i+1) (tepat bersebelahan). Jika tidak sesuai maka tukar (data ke-i = data ke-(i+1) dan data ke-(i+1) = data ke-i). Apa maksudnya tidak sesuai? Jika kita menginginkan algoritma menghasilkan data dengan urutan ascending (A-Z), kondisi tidak sesuai adalah data ke-i > data ke-i+1, dan sebaliknya untuk urutan descending (A-Z), data ke-i < data ke-i+1.

2. Membandingkan data ke-(i+1) dengan data ke-(i+2). Kita melakukan pembandingan ini sampai data terakhir. Contoh: 1 dengan 2; 2 dengan 3; 3 dengan 4; 4 dengan 5 … ; n-1 dengan n.
3. Selesai satu proses, yang dimana kita sudah selesai membandingkan antara (n-1) dengan n. Setelah selesai satu proses, kita lanjutkan lagi proses berikutnya sesuai dengan aturan ke-1. Mulai dari data ke-1 dengan data ke-2, dan seterusnya.
4. Proses akan berhenti jika tidak ada pertukaran dalam satu proses.

Contoh Program Bubble Sort C++ (Ascending):
#include <iostream>
#include <conio.h>

using namespace std;

int data[10],data2[10];
int n;

void swap(int a,int b)
{
    int swap;
    swap = data[b];
    data[b] = data[a];
    data[a] = swap;
}

void Input()
{
    cout<<"Masukkan jumlah data yang diinginkan : ";
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cout<<"Masukkan data ke-"<<(i+1)<<" : ";
        cin>>data[i];
        data2[i] = data[i];
    }
    cout<<endl;
}

void Tampil()
{
    for(int i=0;i<n;i++)
    {
        cout<<data[i]<<" ";
    }
    cout<<endl;
}

void Bubble_Sort()
{
    for(int i=1;i<n;i++)
    {
        cout<<"Proses ke-"<<(i+1)<<" : ";
        for(int j=n-1;j>=i;j--)
        {
            if(data[j]<data[j-1]) swap(j,j-1);
        }
        Tampil();
    }
    cout<<endl;
}

int main()
{
    cout<<"------------------------------------------"<<endl;
    cout<<"BUBBLE SORT C++"<<endl;
    cout<<"------------------------------------------"<<endl<<endl;
        Input();
    cout<<"Bubble Sort : ";
        Tampil();
        Bubble_Sort();
    cout<<"Hasil Pengurutan Bubble Sort : ";
        Tampil();
    cout<<"------------------------------------------"<<endl;

    getch();
}

Output Setelah di Run : 

Referensi:
Munir, Rinaldi. (2011). Algoritma dan Pemrograman Dalam Bahasa Pascal dan C. Edisi Revisi. Bandung: Informatika.

Krisna, Putu. (23 May 2012). Sorting-Program Bubble Sort. http://belajarohbelajar.blogspot.com/2012/05/program-bubble-sort.html. 20 Februari 2014

Nurhayati, OD. (2010). Algoritma dan Pemrograman Sorting dan Searching. http://eprints.undip.ac.id/19736/1/sorting.pdf. 20 Februari 2014

Susanto, Ilham. (3 April 2013). Analisa Algoritma | Bubble Sort. http://buublesort.blogspot.com/2013/04/analisa-algoritma.html. 20 Februari 2014

Tunk, Tunk. (22 November 2013). Sekedar Berbagi. http://aina-tunk.blogspot.com/. 20 Februari 2014

Santoso, Rachmat. (3 May 2013). Algoritma Sorting (Algoritma dan Struktur Data). http://rachmatsn.blogspot.com/2013/05/algoritma-sorting-algoritma-dan.html. 20 Februari 2014