Pengurutan adalah proses dasar yang dipelajari di dalam algoritma dan stuktur data. Terdapat banyak algoritma pengurutan yang sering digunakan di dalam program. Setelah kami pernah membahas algoritma percabangan di situs ini, pada artikel kali ini, kami akan membahas mengenai dasar algoritma Bubble Sort. Algortima ini merupakan algortima pengurutan sederhana dan biasanya dipelajari sebagai materi bahasan seputar pengurutan.
Algoritma Bubble Sort merupakan proses pengurutan yang secara berangsur-angsur memindahkan data ke posisi yang tepat. Karena itulah, algoritma ini dinamakan “bubble” atau yang jika diterjemahkan ke dalam Bahasa Indonesia, artinya yaitu gelembung. Fungsi algoritma ini adalah untuk mengurutkan data dari yang terkecil ke yang terbesar (ascending) atau sebaliknya (descending).
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.
Sebelum kita masuk untuk membuat program, berikut ini adalah syarat dan langkah-langkah yang harus diperhatikan pada metode Bubble Sort:
- Jumlah iterasi sama dengan banyaknya bilangan dikurang 1.
- Di setiap iterasi, jumlah pertukaran bilangannya sama dengan jumlah banyaknya bilangan.
- Dalam algoritma Bubble Sort, meskipun deretan bilangan tersebut sudah terurut, proses sorting akan tetap dilakukan.
- Tidak ada perbedaan cara yang berarti untuk teknik algoritma Bubble Sort Ascending dan Descending.
Untuk mempelajari algoritma Bubble Sort ini, Anda hanya perlu memahami cara yang digunakan untuk mengurutkan data. Logika sederhananya, algoritma ini menggunakan perbandingan dalam operasi antar elemennya. Kita simak salah satu contoh di bawah ini, yang merupakan gambaran dari penerapan 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 Anda memperhatikan proses yang terjadi di atas, ketika proses kedua data di dalam array sudah terurut dengan benar. Tetapi, algoritma Bubble Sort akan terus berjalan hingga proses kedua berakhir. Proses ketiga ini akan terus berjalan, karena pada algoritma Bubble Sort, yang dimaksud “data sudah terurut” adalah tidak ada satupun pertukaran data pada suatu proses. Proses ketiga ini dimaksudkan untuk verifikasi data.
Algoritma Bubble Sort ini mempunyai kelebihan dan kekurangan. Dua hal inilah yang menjadi pertimbangan programmer ketika membuat program. Berikut ini beberapa kelebihan yang dimiliki oleh algoritma ini:
- Algoritma ini adalah metode paling sederhana untuk mengurutkan data.
- Selain sederhana, algoritma ini juga mudah dipahami.
Sedangkan, kekurangan dari algortima ini adalah sebagai berikut:
- Tingkat efisiensinya yang kurang. Bubble Sort ini merupakan metode pengurutan yang tidak efisien, khususnya ketika menangani data yang berjumlah besar. Hal tersbeut karena ketika mengurutkan data yang sangat besar akan sangat lambat prosesnya.
- Jumlah pengulangan yang dilakukan oleh algortima ini akan tetap sama jumlahnya, meskipun data yang diurutkan sudah cukup terurut.
Algoritma Bubble Sort memiliki dua jenis proses, yaitu proses Ascending (pengurutan data dari yang terkecil ke yang terbesar) dan Descending (pengurutan data dari yang terbesar ke yang terkecil). Apa sih perbedaan proses Ascending dan Descending? Simak pembahasannya di bawah ini:
1. Proses Ascending
Kami akan memberikan contoh untuk memberikan pemahaman kepada Anda seputar proses Ascending di dalam algoritma Bubble Sort. Berikut ini adalah sebuah deretan bilangan yang kami jadikan contoh: [5, 12, 3, 19, 1, 47]
Ini dia langkah Bubble Sort dengan metode Ascending:
Iterasi 1:
5, 12, 3, 19, 1, 47 –> Tidak ada pertukaran. (5 < 12 == true)
5, 3, 12, 19, 1, 47 –> Ada pertukaran. (12 < 3 == false)
5, 3, 12, 19, 1, 47 –> Tidak ada pertukaran. (12 < 19 == true)
5, 3, 12, 1, 19, 47 –> Ada pertukaran. (19 < 1 == false)
5, 3, 12, 1, 19, 47 –> Tidak ada pertukaran. (19 < 47 == true)
Iterasi 2:
3, 5, 12, 1, 19, 47 –> Ada petukaran. (5 < 3 == false)
3, 5, 12, 1, 19, 47 –> Tidak ada pertukaran. (5 < 12 == true)
3, 5, 1, 12, 19, 47 –> Ada pertukaran. (12 < 1 == false)
3, 5, 1, 12, 19, 47 –> Tidak ada pertukaran. (12 < 19 == true)
3, 5, 1, 12, 19, 47 –> Tidak ada pertukaran. (19 < 47 == true)
Iterasi 3:
3, 5, 1, 12, 19, 47 –> Tidak ada pertukaran. (3 < 5 == true)
3, 1, 5, 12, 19, 47 –> Ada pertukaran. (5 < 1 == false)
3, 1, 5, 12, 19, 47 –> Tidak ada pertukaran. (5 < 12 == true)
3, 1, 5, 12, 19, 47 –> Tidak ada pertukaran. (12 < 19 == true)
3, 1, 5, 12, 19, 47 –> Tidak ada pertukaran. (19 < 47 == true)
Iterasi 4:
1, 3, 5, 12, 19, 47 –> Ada pertukaran. (3 < 1 == false)
1, 3, 5, 12, 19, 47 –> Tidak ada pertukaran. (3 < 5 == true)
1, 3, 5, 12, 19, 47 –> Tidak ada pertukaran. (5 < 12 == true)
1, 3, 5, 12, 19, 47 –> Tidak ada pertukaran. (12 < 19 == true)
1, 3, 5, 12, 19, 47 –> Tidak ada pertukaran. (19 < 47 == true)
Iterasi 5:
1, 3, 5, 12, 19, 47 –> Tidak ada pertukaran. (1 < 3 == true)
1, 3, 5, 12, 19, 47 –> Tidak ada pertukaran. (3 < 5 == true)
1, 3, 5, 12, 19, 47 –> Tidak ada pertukaran. (5 < 12 == true)
1, 3, 5, 12, 19, 47 –> Tidak ada pertukaran. (12 < 19 == true)
1, 3, 5, 12, 19, 47 –> Tidak ada pertukaran. (19 < 47 == true)
Iterasi 6:
1, 3, 5, 12, 19, 47 –> Tidak ada pertukaran. (1 < 3 == true)
1, 3, 5, 12, 19, 47 –> Tidak ada pertukaran. (3 < 5 == true)
1, 3, 5, 12, 19, 47 –> Tidak ada pertukaran. (5 < 12 == true)
1, 3, 5, 12, 19, 47 –> Tidak ada pertukaran. (12 < 19 == true)
1, 3, 5, 12, 19, 47 –> Tidak ada pertukaran. (19 < 47 == true)
Jadi, hasil akhir deretan bilangan di atas setelah diurutkan dengan algoritma Bubble Sort secara Ascending ialah [1, 3, 5, 12, 19, 47]
2. Proses Descending
Kami akan memberikan contoh yang sama seperti contoh di atas untuk memberikan pemahaman kepada Anda seputar proses Descending di dalam algoritma Bubble Sort, yaitu sebuah deretan bilangan: [5, 12, 3, 19, 1, 47]
Ini dia langkah Bubble Sort dengan metode Descending:
Iterasi 1:
12, 5, 3, 19, 1, 47 –> Ada pertukaran. (5 > 12 == false)
12, 5, 3, 19, 1, 47 –> Tidak ada pertukaran. (5 > 3 == true)
12, 5, 19, 3, 1, 47 –> Ada pertukaran. (3 > 19 == false)
12, 5, 19, 3, 1, 47 –> Tidak ada pertukaran. (3 > 1 == true)
12, 5, 19, 3, 47, 1 –> Ada pertukaran. (1 > 47 == false)
Iterasi 2:
12, 5, 19, 3, 47, 1 –> Tidak ada pertukaran. (12 > 5 == true)
12, 19, 5, 3, 47, 1 –> Ada pertukaran. (5 > 19 == false)
12, 19, 5, 3, 47, 1 –> Tidak ada pertukaran. (5 > 3 == true)
12, 19, 5, 47, 3, 1 –> Ada pertukaran. (3 > 47 == false)
12, 19, 5, 47, 3, 1 –> Tidak ada pertukaran. (3 > 1 == true)
Iterasi 3:
19, 12, 5, 47, 3, 1 –> Ada pertukaran. (12 > 19 == false)
19, 12, 5, 47, 3, 1 –> Tidak ada pertukaran. (12 > 5 == true)
19, 12, 47, 5, 3, 1 –> Ada pertukaran. (5 > 47 == false)
19, 12, 47, 5, 3, 1 –> Tidak ada pertukaran. (5 > 3 == true)
19, 12, 47, 5, 3, 1 –> Tidak ada pertukaran. (3 > 1 == true)
Iterasi 4:
19, 12, 47, 5, 3, 1 –> Tidak ada pertukaran. (19 > 12 == true)
19, 47, 12, 5, 3, 1 –> Ada pertukaran. (12 > 47 == false)
19, 47, 12, 5, 3, 1 –> Tidak ada pertukaran. (12 > 5 == true)
19, 47, 12, 5, 3, 1 –> Tidak ada pertukaran. (5 > 3 == true)
19, 47, 12, 5, 3, 1 –> Tidak ada pertukaran. (3 > 1 == true)
Iterasi 5:
47, 19, 12, 5, 3, 1 –> Ada pertukaran. (19 > 47 == false)
47, 19, 12, 5, 3, 1 –> Tidak ada pertukaran. (19 > 12 == true)
47, 19, 12, 5, 3, 1 –> Tidak ada pertukaran. (12 > 5 ==true)
47, 19, 12, 5, 3, 1 –> Tidak ada pertukaran. (5 > 3 == true)
47, 19, 12, 5, 3, 1 –> Tidak ada pertukaran. (3 > 1 == true)
Iterasi 6:
47, 19, 12, 5, 3, 1 –> Tidak ada pertukaran. (47 > 19 == true)
47, 19, 12, 5, 3, 1 –> Tidak ada pertukaran. (19 > 12 == true)
47, 19, 12, 5, 3, 1 –> Tidak ada pertukaran. (12 > 5 == true)
47, 19, 12, 5, 3, 1 –> Tidak ada pertukaran. (5 > 3 == true)
47, 19, 12, 5, 3, 1 –> Tidak ada pertukaran. (3 > 1 == true)
Jadi, hasil akhir deretan bilangan di atas setelah diurutkan dengan algoritma Bubble Sort secara Descending ialah [47, 19, 12, 5, 3, 1]
Kompleksitas Algoritma Bubble Sort
Kompleksitas sebuah algoritma Bubble Sort dapat dilihat dari beberapa jenis kasus, yaitu worst-case, average-case, dan best-case.
- Kondisi Best-Case
Dalam kasus ini, data yang akan diurutkan telah terurut sebelumnya. Sehingga proses perbandingan hanya dilakukan sebanyak (n-1) kali, dengan satu kali iterasi. Proses perbandingan dilakukan hanya untuk memverifikasi keurutan data. Contoh kasus ini dapat dilihat pada pengurutan data “1 2 3 4” di bawah ini.
Iterasi pertama:
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
Dalam proses di atas, dapat dilihat bahwa tidak terjadi penukaran posisi data apapun. Sehingga tidak dilakukan iterasi selanjutnya. Perbandingan elemen dilakukan sebanyak tiga kali. Proses perbandingan pada kondisi ini hanya dilakukan sebanyak (n-1) kali. Persamaan Big-O yang diperoleh dari proses ini adalah O(n).
- Kondisi Worst-Case
Dalam kasus ini, data terkecil berada pada ujung array. Contoh dari kasus ini dapat dilihat pada pengurutan data “4 3 2 1” di bawah ini:
Iterasi Pertama:
(4 3 2 1) menjadi (3 4 2 1)
(3 4 2 1) menjadi (3 2 4 1)
(3 2 4 1) menjadi (3 2 1 4)
Iterasi Kedua:
(3 2 1 4) menjadi (2 3 1 4)
(2 3 1 4) menjadi (2 1 3 4)
(2 1 3 4) menjadi (2 1 3 4)
Iterasi Ketiga:
(2 1 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
Iterasi Keempat:
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
(1 2 3 4) menjadi (1 2 3 4)
Di dalam langkah-langkah pengurutan di atas, terlihat bahwa setiap kali melakukan satu iterasi, data terkecil akan bergeser ke arah awal sebanyak satu step. Dengan kata lain, untuk menggeser data terkecil dari urutan keempat menuju urutan pertama, dibutuhkan iterasi sebanyak tiga kali, ditambah satu kali iterasi untuk verifikasi data. Sehingga jumlah proses pada kondisi worst-case dapat dirumuskan sebagai berikut:
“Jumlah proses = n2+n” (3)
Dalam persamaan (3) di atas, n adalah jumlah elemen yang akan diurutkan. Sehingga notasi Big-O yang didapatkan adalah O(n2).
- Kondisi Average-Case
Pada kondisi average-case, jumlah iterasi ditentukan dari data mana yang mengalami pergeseran ke kiri paling banyak. Hal ini dapat ditunjukkan oleh proses pengurutan suatu array, misalkan saja deretan bilangan (1 8 6 2). Dari (1 8 6 2), dapat dilihat bahwa yang akan mengalami proses penggeseran paling banyak adalah elemen 2, yaitu sebanyak dua kali.
Iterasi Pertama:
(1 8 6 2) menjadi (1 8 6 2)
(1 8 6 2) menjadi (1 6 8 2)
(1 6 8 2) menjadi (1 6 2 8)
Iterasi Kedua:
(1 6 2 8) menjadi (1 6 2 8)
(1 6 2 8) menjadi (1 2 6 8)
(1 2 6 8) menjadi (1 2 6 8)
Iterasi Ketiga:
(1 2 6 8) menjadi (1 2 6 8)
(1 2 6 8) menjadi (1 2 6 8)
(1 2 6 8) menjadi (1 2 6 8)
Dari proses pengurutan di atas, dapat dilihat bahwa untuk mengurutkan data di dalam array tersebut, diperlukan dua buah iterasi, ditambah satu iterasi untuk verifikasi data. Dengan kata lain, jumlah proses perbandingan dapat dihitung sebagai berikut.
“Jumlah proses = x2+x” (4)
Dalam persamaan (4) di atas, x adalah jumlah penggeseran terbanyak. Dalam hal ini, x tidak pernah lebih besar dari n.
Jika Anda hendak mempelajari algoritma Bubble Sort, Anda bisa mempraktekkannya menggunakan macam-macam bahasa pemrograman, mulai dari Java, C++, Python, dan lainnya. Berikut ini adalah contoh dari program C++ yang menggunakan algoritma Bubble Sort ini:
#include <iostream.h>
int main()
{
int data[10];
int i, j, k, tmp, jumlah=0;
cout<<“PROGRAM PENGURUTAN BILANGAN BUBBLE SORT\n\n”;
cout<<“Masukkan jumlah bilangan : “; cin>>k;
for(i=0; i<k; i++)
{
cout<<“Masukkan Angka ke “<<(i+1)<<” : “;
cin>>data[i];
if(data[i]%2==0)
{jumlah+=data[i];}
}
cout<<“\nData sebelum diurutkan : “<<endl;
for(i=0; i<k; i++)
{
cout<<data[i]<<” “;
}
cout<<endl;
for( i=0;i<k;i++)
{
for(j=i+1;j<k;j++)
{
if(data[i]>data[j])
{
tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}
}
}
cout<<“\nData setelah diurutkan : “<<endl;
for(i=0; i<k; i++)
{
{
cout<<data[i]<<” “;
}
}
cout<<“\nData setelah diurutkan (Genap): “<<endl;
for(i=0; i<k; i++)
{
if (data[i]%2==0)
{
cout<<data[i]<<” “;
}
}
cout<<“\nData setelah diurutkan (Ganjil): “<<endl;
for(i=0; i<k; i++)
{
if (data[i]%2!=0)
{
cout<<data[i]<<” “;
}
}
cout<<“\n\nJumlah dari bilangan genap = “<<jumlah;
return 0;
}
Anda bisa mencari lebih lanjut mengenai metode algoritma Bubble Sort ini melalui internet. Dengan internet, Anda bisa mendapatkan manfaat mempelajari ilmu komputer. Siapa tahu, dari belajar hal-hal kecil, Anda jadi bisa membuat program yang berguna untuk masyarakat.
Oh iya, jika Anda sudah terbayang bagaimana algortima Bubble Sort ini dibuat, langkah selanjutnya Anda perlu membuat flowchartnya. Anda bisa melihat beberapa contoh flowchart program yang menerapkan algoritma Bubble Sort ini di internet.
Sekian pembahasan kami kali ini seputar algoritma Bubble Sort. Semoga artikel kami ini dapat menjadi bahan belajar Anda dalam mempelajari algoritma pengurutan.
