Bubble Sort adalah algoritma Sorting yang paling populer, paling gampang diimplementasikan dan juga paling rakus memakan resource.
Algoritma ini mengiterasi seluruh elemen array dari awal sampai akhir dan membandingkan setiap dua buah elemen array yang bertetanggaan.
Jika didapati kedua elemen yang bertetanggaan itu berbeda (salah satu elemen lebih besar/kecil dari elemen lain), maka kedua elemen itu akan “ditempatkan” pada urutan yang benar.
Jika metode pengurutan yang diinginkan adalah ascending (dari kecil ke besar), maka elemen yang lebih besar akan ditempatkan setelah elemen yang lebih kecil.
Begitu juga sebaliknya, jika metode pengurutan yang diinginkan adalah descending (dari besar ke kecil), maka elemen yang lebih besar akan ditempatkan sebelum elemen yang lebih kecil.
Untuk lebih jelasnya silahkan perhatikan dua buah ilustrasi di bawah ini (ascending)
- Ilustrasi dengan angka (dari Wikipedia)
Iterasi pertama:
( 5 1 4 2 8 ) -> ( 1 5 4 2 8 ) Algoritma ini membandingkan dua elemen pertama dan menukarnya
( 1 5 4 2 8 ) -> ( 1 4 5 2 8 ) swap
( 1 4 5 2 8 ) -> ( 1 4 2 5 8 ) swap
( 1 4 2 5 8 ) -> ( 1 4 2 5 8 )
Iterasi kedua:
( 1 4 2 5 8 ) -> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) -> ( 1 2 4 5 8 ) swap
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
Sebenarnya, array ini sudah terurut dengan baik, tetapi algoritma kita belum tau. Algoritma kita hanya tahu bahwa dia harus mengiterasi lagi dan baru berhenti jika tidak terjadi swap sama sekali.
Iterasi ketiga:
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
Akhirnya, algoritma kita sadar bahwa tidak ada swap lagi dan algoritma pun berhenti mengiterasi.
- Ilustrasi dengan gambar (refresh browser anda jika gambar tidak bergerak)
Berikut ini saya sediakan implementasi Bubble Sort dalam Java..
public class Sort {
private Sort(){}
public static <T extends Comparable<T>> T[] bubble(T[] arr){
boolean swapped;
for (int i = 0; i < arr.length; i++){
swapped = false;
for (int j = arr.length - 1; j >= i + 1; j--){
if (arr[j - 1].compareTo(arr[j]) > 0){
T t = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = t;
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}
}
Sayangnya, method bubble di atas hanya bisa mengurutkan ascending dan ini kurang baik. Untuk mengembangkan method bubble di atas agar bisa mengurutkan secara ascending dan descending, kita tambahkan beberapa perubahan seperti ini :
public class Sort {
private Sort(){}
public static <T extends Comparable<T>> T[] bubble(T[] arr, boolean isAscending){
boolean swapped;
for (int i = 0; i < arr.length; i++){
swapped = false;
for (int j = arr.length - 1; j >= i + 1; j--){
if ((isAscending && (arr[j - 1].compareTo(arr[j]) > 0)) ||
(!isAscending && (arr[j - 1].compareTo(arr[j]) < 0)))
{
T t = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = t;
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}
public static <T> T[] bubble(T[] arr, Comparator<T> comparator, boolean isAscending){
boolean swapped;
for (int i = 0; i < arr.length; i++){
swapped = false;
for (int j = arr.length - 1; j >= i + 1; j--){
if ((isAscending && (comparator.compare(arr[j - 1], arr[j]) > 0)) ||
(!isAscending && (comparator.compare(arr[j - 1], arr[j]) < 0)))
{
T t = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = t;
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}
}
Penjelasan kode program di atas masih agak rumit, mengingat blog ini belum membahas tentang Generic. Sebagai gambaran saja, method bubble pada kode program di atas
akan meminta input berupa array of T. Dimana T adalah suatu kelas yang mengimplement interface Comparable. Mengapa Comparable? Karena
interface inilah yang mampu menjanjikan bahwa suatu object yang mengimplement dirinya akan dapat dibandingkan dengan object lain.
public class Student {
private String name;
private int point;
public Student (String name, int point){
this.name = name;
this.point = point;
}
public String getName() {return name;}
public int getPoint() {return point;}
@Override
public String toString(){
return name + ":" + point;
}
public static void main(String[] args) {
Integer[] integers = new Integer[]{1, -10, 3, 0, 6, 7, 4, 2, 1, 15, 5, -6};
String[] strings = new String[]{"pisang", "apel", "nangka",
"jambu", "rambutan", "melon", "nanas"};
Student[] students = new Student[]{
new Student("basana", 64), new Student("tika", 68), new Student("ingel", 98),
new Student("bule", 45), new Student("septa", 78), new Student("hartoyo", 85),
new Student("jaya", 97), new Student("lukas", 25), new Student("lia", 77),
new Student("akub", 68)
};
for (Integer i : Sort.bubble(integers, true))System.out.print(i + " ");
System.out.println();
// Mengeluarkan output -10 -6 0 1 1 2 3 4 5 6 7 15
for (String s : Sort.bubble(strings, false))System.out.print(s + " ");
System.out.println();
// Mengeluarkan output rambutan pisang nangka nanas melon jambu apel
}
for (Student st : Sort.bubble(students, new StudentComparator(), true))
System.out.print(st + " ");
System.out.println();
// Mengeluarkan output lukas:25 bule:45 basana:64 akub:68 tika:68 lia:77
// septa:78 hartoyo:85 jaya:97 ingel:98
}
Ini kelas comparatornya :
public class StudentComparator implements Comparator<Student> {
@Override
public int compare(Student s1, Student s2) {
int i = s1.getPoint() - s2.getPoint();
if (i == 0) return s1.getName().compareTo(s2.getName());
return i;
}
}
Sekedar tambahan, ada pengembangan dari Bubble Sort dimana algoritma tidak hanya mengiterasi array dari elemen paling awal, tetapi juga dari elemen paling akhir. Pengembangan ini dikenal dengan nama “Bidirectional Bubble Sort” dan inilah implementasinya di Java
public class Sort {
private Sort(){}
public static <T extends Comparable> T[] bidirectionalBubble(T[] arr, boolean isAscending){
int top = arr.length;
int bot = -1;
boolean swapped;
while (bot < top) {
swapped = false;
bot++;
top--;
for (int i = bot; i < top; i++) {
if ((isAscending && (arr[i].compareTo(arr[i + 1]) > 0)) ||
(!isAscending && (arr[i].compareTo(arr[i + 1]) < 0)))
{
T t = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = t;
swapped = true;
}
}
if (!swapped) break;
for (int j = top; --j >= bot;) {
if ((isAscending && (arr[j].compareTo(arr[j + 1]) > 0)) ||
(!isAscending && (arr[j].compareTo(arr[j + 1]) < 0)))
{
T t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}
public static T[] bidirectionalBubble(T[] arr, Comparator comparator, boolean isAscending){
int top = arr.length;
int bot = -1;
boolean swapped;
while (bot < top) {
swapped = false;
bot++;
top--;
for (int i = bot; i < top; i++) {
if ((isAscending && (comparator.compare(arr[i], arr[i + 1]) > 0)) ||
(!isAscending && (comparator.compare(arr[i], arr[i + 1]) < 0)))
{
T t = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = t;
swapped = true;
}
}
if (!swapped) break;
for (int j = top; --j >= bot;) {
if ((isAscending && (comparator.compare(arr[j], arr[j + 1]) > 0)) ||
(!isAscending && (comparator.compare(arr[j], arr[j + 1]) < 0)))
{
T t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}
}
