Mengenal Algoritma Bubble Sort

Salah satu algoritma yang populer digunakan untuk melakukan data sorting (pengurutan data) adalah algoritma bubble sort. Bubble sort mudah dipahami oleh pemula, sehingga sering dijadikan sebagai materi dasar dalam pelajaran algoritma bagi para pelajar algoritma. Bubble sort adalah algoritma yang sederhana tetapi lambat, sehingga sebenarnya cukup jarang digunakan dalam aplikasi nyata. 

Konsep bubble sort

Konsep kerja bubble sort adalah dengan membandingkan elemen-elemen bersebelahan dalam daftar dan menukar posisi mereka jika urutannya salah. Pengurutan ini berulang-ulang hingga seluruh daftar terurut dengan benar. Ide di balik bubble sort adalah elemen-elemen yang lebih besar nilainya seakan “menggelembung” (bubble) ke akhir bagian akhir dari list. Seperti gelembung yang naik ke permukaan air.

Langkah-langkah dasar dalam mencoba algoritma Bubble sort adalah sebagai berikut:

1. Buat list data yang belum terurut. Setiap elemen dalam list ini akan dibandingkan dengan elemen berikutnya.
2. Bandingkan elemen pertama dengan elemen kedua. Jika elemen pertama lebih besar, tukar posisinya.
3. Lanjutkan langkah sebelumnya untuk elemen kedua dan ketiga, kemudian elemen ketiga dan keempat, dan seterusnya, hingga mencapai elemen terakhir dalam list.
4. Sekarang, elemen terbesar berada di posisi terakhir. Ulangi langkah-langkah sebelumnya untuk semua elemen dalam list, kecuali elemen terakhir.
5. Terus lakukan langkah-langkah tersebut hingga seluruh list terurut dengan benar. Setelah setiap iterasi, elemen terbesar akan naik ke posisi terakhir.
6. Ketika tidak ada lagi pertukaran yang terjadi dalam satu iterasi, proses pengurutan dianggap selesai.

Berikut adalah contoh implementasi bubble sort dalam bahasa Python:

def bubble_sort(arr):
    n = len(arr)

    for i in range(n):
        # Melakukan iterasi untuk setiap elemen kecuali elemen terakhir

        for j in range(0, n-i-1):
            # Membandingkan elemen bersebelahan
            if arr[j] > arr[j+1]:
                # Jika urutannya salah, tukar posisi
                arr[j], arr[j+1] = arr[j+1], arr[j]

    return arr

# Contoh penggunaan Bubble Sort

my_list = [64, 34, 25, 12, 22, 11, 90]
sorted_list = bubble_sort(my_list)
print(sorted_list)

Dalam contoh di atas, kita memiliki list dengan nama my_list yang belum terurut. Setelah menjalankan fungsi bubble_sort, list akan diurutkan dengan menggunakan bubble sort, dan hasilnya akan dicetak di baris terakhir. 

List my_list dalam skrip di atas akan mengalami perubahan sebagai berikut:

64 34 25 12 22 11 99
34 64 25 12 22 11 99
34 25 64 12 22 11 99
25 34 64 12 22 11 99
25 34 12 64 22 11 99
25 12 34 64 22 11 99
12 25 34 64 22 11 99
12 25 34 22 64 11 99
12 25 22 34 64 11 99
12 22 25 34 64 11 99
12 22 25 34 11 64 99
12 22 25 11 34 64 99
12 22 11 25 34 64 99
12 11 22 25 34 64 99
11 12 22 25 34 64 99

Contoh di atas adalah jika pengurutan yang diinginkan berupa pengurutan ascending (dari rendah ke tinggi). Bubble sort juga bisa melakukan pengurutan descending (dari tinggi ke rendah).

Berikut adalah contoh implementasi bubble sort untuk pengurutan descending :

def bubble_sort(arr):
    n = len(arr)

    for i in range(n):
        # Melakukan iterasi untuk setiap elemen kecuali elemen terakhir
        for j in range(0, n-i-1):
            # Membandingkan elemen bersebelahan
            if arr[j] < arr[j+1]:
                # Jika urutannya salah, tukar posisi
                arr[j], arr[j+1] = arr[j+1], arr[j]

    return arr

# Contoh penggunaan Bubble Sort

my_list = [64, 34, 25, 12, 22, 11, 90]
sorted_list = bubble_sort(my_list)
print(sorted_list)

List my_list dalam skrip di atas akan mengalami perubahan sebagai berikut:

64 34 25 12 22 11 99
64 34 25 22 12 11 99
64 34 25 22 12 11 99
64 34 25 22 12 99 11
64 34 25 22 99 12 11
64 34 25 99 22 12 11
64 34 99 25 22 12 11
64 99 34 25 22 12 11
99 64 34 25 22 12 11

Meskipun bubble sort sederhana untuk dipahami, algoritma ini tidak efisien untuk list yang besar. Bubble sort memiliki kompleksitas waktu O(n^2), yang berarti waktu eksekusinya meningkat secara kuadrat seiring dengan jumlah elemen dalam daftar. 

Selamat mencoba!

Yulian Purnama