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:
- Fungsi tukar data
tukar(int &a, int &b)
, untuk menukar antara data yang indexnya berdekatan - 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. - Fungsi bubble sorting
bubbleSort(int *array, int jumlah)
, dimana logika sorting diimplementasikan. - 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.
- 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 kefalse
pada setiap fase. -
Selanjutnya pada iterasi pengurutan data kita menentukan kondisi pengurutan (
array[j] > array[j+1]
).Jika data
a
(array[j]
) lebih besar datab
(array[j+1]
) maka tukar data menggunakan fungsitukar(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++)
), kondisij<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])
). -
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 variabelditukar
masih bernilaifalse
. Maka nilai tidak ditukar (!ditukar
) pada pengecekanif(!ditukar)
adalahtrue
(negasi) dengan begitu argumenbreak
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
Untuk memudahkan teman - teman menguji kode tersebut, jadi full kodenya dapat di lihat di link berikut : cpp bubble sort demo