Bubble Sort Cara Mudah Urutkan Data dengan Kode

Bubble Sort: Cara Mudah Urutkan Data dengan Kode

Bubble Sort, atau kadang disebut Sinking Sort, adalah algoritma pengurutan sederhana yang bekerja dengan cara berulang kali membandingkan pasangan elemen yang berdekatan dan menukarnya jika mereka berada dalam urutan yang salah. Proses ini diulangi melalui daftar sampai tidak ada lagi penukaran yang diperlukan, yang berarti daftar tersebut sudah terurut. Meskipun Bubble Sort tergolong mudah dipahami dan diimplementasikan, efisiensinya kurang jika dibandingkan dengan algoritma pengurutan yang lebih canggih, terutama untuk set data yang besar. Namun, pemahaman yang baik tentang Bubble Sort adalah fondasi penting untuk memahami konsep-konsep dasar algoritma dan pemrograman.

Bagaimana Bubble Sort Bekerja?

Inti dari Bubble Sort adalah proses iterasi yang membandingkan setiap pasangan elemen bersebelahan. Bayangkan kita memiliki sebuah array angka: [5, 1, 4, 2, 8]. Bubble Sort akan membandingkan 5 dan 1. Karena 5 lebih besar dari 1, mereka ditukar, menghasilkan [1, 5, 4, 2, 8]. Selanjutnya, 5 dan 4 dibandingkan dan ditukar, menghasilkan [1, 4, 5, 2, 8]. Proses ini berlanjut hingga akhir array. Satu iterasi penuh disebut pass. Setelah pass pertama, elemen terbesar akan “mengapung” ke akhir array, seperti gelembung (bubble) naik ke permukaan air – inilah asal nama Bubble Sort.

Proses ini diulangi untuk seluruh array, kecuali elemen terakhir yang sudah berada di posisi yang benar. Artinya, setiap pass, jangkauan perbandingan berkurang satu elemen. Iterasi berlanjut sampai tidak ada lagi penukaran yang terjadi dalam satu pass. Hal ini mengindikasikan bahwa array sudah terurut.

Contoh Implementasi Kode Bubble Sort

Berikut adalah contoh implementasi Bubble Sort dalam bahasa pemrograman Python:

def bubble_sort(data):
    n = len(data)
    for i in range(n-1):
        for j in range(n-i-1):
            if data[j] > data[j+1]:
                # Tukar jika elemen tidak dalam urutan yang benar
                data[j], data[j+1] = data[j+1], data[j]
    return data

# Contoh penggunaan
data = [5, 1, 4, 2, 8]
data_terurut = bubble_sort(data)
print("Data terurut:", data_terurut)  # Output: Data terurut: [1, 2, 4, 5, 8]

Dalam kode di atas:

• n = len(data) mendapatkan panjang array.
• Loop luar for i in range(n-1) melakukan iterasi sebanyak n-1 kali. Setiap iterasi memastikan elemen terbesar “mengapung” ke posisi yang tepat.
• Loop dalam for j in range(n-i-1) membandingkan elemen-elemen yang berdekatan.
• if data[j] > data[j+1] memeriksa apakah dua elemen bersebelahan berada dalam urutan yang salah.
• data[j], data[j+1] = data[j+1], data[j] melakukan penukaran elemen jika diperlukan.

Kompleksitas Waktu dan Ruang

Salah satu kekurangan utama Bubble Sort adalah kompleksitas waktunya.

• Kasus Terbaik (Best Case): O(n) – terjadi ketika array sudah terurut. Algoritma hanya perlu melakukan satu pass untuk memastikan bahwa tidak ada penukaran yang diperlukan.
• Kasus Rata-rata (Average Case): O(n²) – terjadi ketika array dalam urutan acak.
• Kasus Terburuk (Worst Case): O(n²) – terjadi ketika array terurut secara terbalik.

Kompleksitas ruang untuk Bubble Sort adalah O(1), yang berarti ia hanya membutuhkan ruang konstan tambahan, terlepas dari ukuran input. Ini karena Bubble Sort adalah algoritma in-place, yang berarti ia melakukan pengurutan langsung di array input tanpa memerlukan struktur data tambahan yang signifikan.

Kapan Menggunakan Bubble Sort?

Meskipun Bubble Sort tidak efisien untuk set data yang besar, ada beberapa situasi di mana ia mungkin cocok:

• Set data kecil: Jika Anda hanya perlu mengurutkan sejumlah kecil elemen, perbedaan kinerja antara Bubble Sort dan algoritma yang lebih canggih mungkin tidak signifikan.
• Implementasi sederhana: Bubble Sort mudah dipahami dan diimplementasikan, sehingga cocok untuk tujuan pendidikan atau ketika kompleksitas kode perlu dijaga seminimal mungkin.
• Deteksi array terurut (dengan sedikit modifikasi): Bubble Sort dapat dimodifikasi untuk mendeteksi apakah array sudah terurut dengan sangat efisien (O(n)). Dengan menambahkan flag yang menunjukkan apakah terjadi penukaran dalam satu pass, kita bisa menghentikan algoritma lebih awal jika tidak ada penukaran yang terjadi.

Perbandingan dengan Algoritma Pengurutan Lainnya

Dibandingkan dengan algoritma pengurutan lain seperti Merge Sort, Quick Sort, atau Heap Sort, Bubble Sort jauh lebih lambat, terutama untuk set data yang besar. Algoritma-algoritma ini memiliki kompleksitas waktu O(n log n), yang secara signifikan lebih efisien daripada O(n²) dari Bubble Sort.

Namun, beberapa algoritma pengurutan lain (seperti Insertion Sort) mungkin lebih efisien daripada Bubble Sort untuk set data yang hampir terurut. Dalam kasus seperti itu, jumlah penukaran yang diperlukan oleh Bubble Sort akan berkurang secara signifikan.

Tips untuk Optimasi Bubble Sort (Meskipun Terbatas)

Meskipun tidak dapat mengubah kompleksitas waktu asimptotik Bubble Sort, ada beberapa optimasi kecil yang dapat dilakukan:

• Menggunakan flag untuk deteksi array terurut: Seperti disebutkan sebelumnya, tambahkan flag yang menunjukkan apakah ada penukaran yang terjadi dalam satu pass. Jika tidak ada penukaran, hentikan algoritma.
• Mengurangi jangkauan iterasi: Setelah setiap pass, elemen terakhir sudah berada di posisi yang benar, jadi tidak perlu membandingkannya lagi. Kurangi jangkauan iterasi pada loop dalam setiap pass. (Sudah diimplementasikan pada kode contoh di atas dengan range(n-i-1)).

Kesimpulan

Bubble Sort adalah algoritma pengurutan yang sederhana dan mudah dipahami, tetapi efisiensinya terbatas, terutama untuk set data yang besar. Meskipun bukan pilihan terbaik untuk sebagian besar kasus praktis, pemahaman tentang Bubble Sort merupakan fondasi penting untuk mempelajari algoritma yang lebih kompleks. Memahami kelebihan dan kekurangan Bubble Sort membantu menghargai pentingnya pemilihan algoritma yang tepat untuk tugas yang diberikan, dan membuka jalan untuk eksplorasi algoritma pengurutan yang lebih canggih. Belajar Bubble Sort bukan hanya tentang mengurutkan data, tetapi juga tentang memahami konsep dasar algoritma dan logika pemrograman.