Implementasi Bubble Sort Di C++

Bubble sorting merupakan algoritma pengurutan berbasis perbandingan, dengan cara membandingkan data yang berdekatan dan menukarnya hingga data tersebut ter-urut semua.

Proses Pengurutan Data

Bubble sort menggunakan proses pengurutan sederhana yaitu membandingkan index data berdasarkan iterasi dengan index data selanjutnya dan mengurutkannya berdasarkan kondisi yang diberikan, sebagai contoh iterasi pertama di gambarkan pada gambar 1.1 dibawah.

Pada contoh diatas semua data masih belum berurutan, maka perlu di lakukan pengurutan lagi pada fase selanjutnya. Fase pengurutan dilakukan beberapa kali hingga data terurut. maksimal fase pengurutan sama dengan jumlah datanya, pada contoh tersebut, maksimal fase pengurutannya adalah lima (5) kali.

Program Bubble Sort

Pada praktek kali ini kita akan membuat program yang mengimplementasikan bubble sort dengan membuat fungsi - fungsi berikut:

1. Fungsi tukar data tukar(int &a, int &b), untuk menukar antara data yang indexnya berdekatan
2. Fungsi tampil semua data tampil(int *array, int jumlah), untuk menampilkan semua data sebelum dan sesudah diurutkan. dengan fungsi ini kita juga akan menampilkan semua data pada masing - masing fase saat pengurutan.
3. Fungsi bubble sorting bubbleSort(int *array, int jumlah), dimana logika sorting diimplementasikan.
4. Fugsi utama program (main()), dimana kita mengimplementasikan penginputan data dan menggunakan fungsi - fungsi diatas.

Kode Program Bubble Sort

Preprocessor & Header File

#include <iostream>
using namespace std;

Disini kita hanya menggunakan satu preprocessor untuk mendefinisikan header file iostream untuk standard input/output stream.

Fungsi Tukar Data

// tukar data a ke b dan data b ke a
void tukar(int &a, int &b) { 
   int temp;
   temp = a;
   a = b;
   b = temp;
}

Pada fungsi ini kita menggunakan dua paramater untuk data a dan b untuk ditukar. pertukaran data dilakukan dengan cara menyimpan data a ke variable temp untuk cadangan (temp=a;), selanjutnya ubah nilai a dengan nilai b (a=b;), karena variabel a sudah menampung nilai variabel b, maka variabel b dapat menampung variabel a yang telah dicadangkan di variabel temp (b=temp;).

Fungsi Tampil Semua data

// menampilkan setiap data pada array
void tampil(int *array, int jumlah) {
   for(int i = 0; i<jumlah; i++)
      cout << array[i] << " ";
   cout << endl;
}

Pada fungsi ini kita cukup membuat iterasi (perulangan) untuk menampilkan semua data yang ditampung di dalam array. Ini akan memudahkan kita tanpa harus menuliskan perulangan tersebut berkali - kali.

Fungsi Logika Bubble Sorting

void bubbleSort(int *array, int jumlah) {
   for(int i = 0; i<jumlah; i++) { // <-- 1) iterasi fase pengurutan
      bool ditukar = false; // memeriksa apakah ada data yang ditukar pada setiap fase

      // jumlah-i artinya data terakhir sudah tidak perlu disorting
      for(int j = 0; j<jumlah-i-1; j++) {// <-- 2) iterasi pengurutan data

        // tukar jika data yang ditunjuk lebih besar dari data selanjutnya [ascending]
         if(array[j] > array[j+1]) {// <-- kondisi pengurutan
            tukar(array[j], array[j+1]);
            ditukar = true;    // tandai bahwa ada data yang di tukar
         }

      }

    // Jika tidak ada data yang ditukar pada fase ini maka keluar dari perulangan
    // Data sudah selesai diurutkan
    if(!ditukar) break;

    // opsional : tidak termasuk dalam logika pengurutan
    cout << "Hasil Pengurutan Fase "<< i+1 << ": ";
    tampil(array,jumlah); // lihat hasil sorting pada setiap fase

   }
}

Pada fungsi inilah logika bubble sort di implementasikan. disini kita membuat dua iterasi, iterasi pertama untuk fase pengurutan, dan iterasi di dalamnya untuk iterasi pengurutan data.

1. Pada awal iterasi fase pengurutan kita membuat variabel (ditukar) yang nantinya digunakan untuk memeriksa apakah pada fase tersebut ada data yang ditukar, varibel tersebut akan di set ulang ke false pada setiap fase.

2. Selanjutnya pada iterasi pengurutan data kita menentukan kondisi pengurutan (array[j] > array[j+1]).

   Jika data a (array[j]) lebih besar data b (array[j+1]) maka tukar data menggunakan fungsi tukar(int &a, int &b) dan tandai bahwa ada data yang ditukar pada fase tersebut (ditukar = true).

   Iterasi pengurutan tidak sama pada setiap fase (for(int j = 0; j<jumlah-i-1; j++)), kondisi j<jumlah - i berarti kita tidak akan mengurutkan data terakhir yang telah diurutkan. Dikurangkan satu (-1) karena kita akan mambandingkan data dengan data selanjutnya (if(array[j] > array[j+1])).

3. Pada akhir iterasi fase pengurutan, kita memeriksa apakah pada fase tersebut tidak ada data yang ditukar.

   Jika kondisi pengurutan pada iterasi pengurutan data tidak ada yang dipenuhi (if(array[j] > array[j+1])), berati semua data sudah urut dan variabel ditukar masih bernilai false. Maka nilai tidak ditukar (!ditukar) pada pengecekan if(!ditukar) adalah true (negasi) dengan begitu argumen break dijalankan untuk keluar dari iterasi.

Fungsi main

int main() {
    int jumlah;// jumlah data array
    cout << "Masukkan jumlah data: ";
    cin >> jumlah;

    int array[jumlah];//buat array dengan jumlah data yang telah ditentukan
    for(int i = 0; i<jumlah; i++) {
        cout << "Masukkan Data " << i+1 <<" : ";
        cin >> array[i];
    }
    cout << "Array data sebelum disorting: ";
    tampil(array, jumlah);
    bubbleSort(array, jumlah); // sorting data pada array
    cout << "Array data setelah disorting: ";
    tampil(array, jumlah);
}

Fungsi terakhir atau fungsi yang pertama kali oleh program (main()). Pertama kita membuat argumen untuk menginputkan jumlah data pada array, kemudian menginputkan masing - masing data ke dalam array sesuai jumlah yang ditentukan menggunakan perulangan. Terakhir menggunakan fungsi bubbleSort(int *array, int jumlah) untuk melakukan pengurutan data. Fungsi tampil(int *array, int jumlah) juga di panggil disini untuk menampilkan data sebelum dan sesudah di sorting.

Full Code Demo