Panduan Lengkap Implementasi Bubble Sort di Pemrograman

Membedah Bubble Sort: Panduan Lengkap Implementasi di Pemrograman

Bubble Sort, atau sering disebut juga Sinking Sort, adalah salah satu algoritma pengurutan paling sederhana dan mudah dipahami. Algoritma ini bekerja dengan berulang kali membandingkan pasangan elemen yang berdekatan dan menukarnya jika urutannya salah. Proses ini diulang hingga tidak ada lagi pertukaran yang diperlukan, menandakan bahwa larik telah terurut dengan benar. Meskipun efisiensinya tidak sebaik algoritma pengurutan yang lebih canggih seperti Merge Sort atau Quick Sort, Bubble Sort tetap memiliki nilai penting dalam pembelajaran dasar-dasar algoritma dan pemahaman konsep pengurutan. Ia sering digunakan sebagai contoh awal dalam pengajaran ilmu komputer karena kemudahan implementasinya.

Logika Dasar di Balik Bubble Sort

Bayangkan sebuah wadah berisi gelembung-gelembung sabun dengan ukuran berbeda. Gelembung yang lebih besar akan naik ke atas permukaan air. Bubble Sort melakukan hal yang serupa dengan elemen-elemen dalam sebuah larik. Ia “menggelembungkan” elemen terbesar ke akhir larik pada setiap iterasi.

Prosesnya terdiri dari beberapa tahapan (atau pass):

1. Perbandingan: Algoritma memulai dengan membandingkan elemen pertama dan kedua dalam larik.
2. Pertukaran (Swap): Jika elemen pertama lebih besar dari elemen kedua, mereka ditukar.
3. Iterasi: Proses perbandingan dan pertukaran ini diulang untuk pasangan elemen berikutnya (elemen kedua dan ketiga, elemen ketiga dan keempat, dan seterusnya) hingga mencapai akhir larik.
4. Pass Berulang: Setelah satu pass selesai, elemen terbesar dijamin berada di posisi terakhir larik. Algoritma kemudian mengulangi proses dari awal larik, tetapi kali ini tanpa menyertakan elemen terakhir (karena sudah terurut).
5. Penghentian: Proses diulang hingga tidak ada lagi pertukaran yang terjadi dalam satu pass. Ini menandakan bahwa semua elemen telah terurut dengan benar.

Implementasi Bubble Sort dalam Kode

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]:
        data[j], data[j+1] = data[j+1], data[j]  # Menukar elemen

# Contoh penggunaan
data = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(data)
print("Array yang terurut:", data) # Output: [11, 12, 22, 25, 34, 64, 90]

Mari bedah kode di atas:

• def bubble_sort(data): mendefinisikan sebuah fungsi bernama bubble_sort yang menerima sebuah larik (data) sebagai input.
• n = len(data) menyimpan panjang larik dalam variabel n.
• for i in range(n-1): adalah loop luar yang berjalan sebanyak n-1 kali. Setiap iterasi mewakili satu pass melalui larik.
• for j in range(n-i-1): adalah loop dalam yang membandingkan pasangan elemen yang berdekatan. Perhatikan bahwa batas akhir loop j berkurang setiap pass karena elemen-elemen di akhir larik sudah terurut.
• if data[j] > data[j+1]: adalah kondisi yang memeriksa apakah elemen data[j] lebih besar dari elemen data[j+1].
• data[j], data[j+1] = data[j+1], data[j] menukar posisi elemen data[j] dan data[j+1] jika kondisi di atas terpenuhi. Ini adalah operasi swap yang penting dalam Bubble Sort.

Optimasi Bubble Sort: Deteksi Ketidakteraturan

Implementasi Bubble Sort standar dapat dioptimalkan dengan menambahkan mekanisme untuk mendeteksi apakah larik sudah terurut. Jika tidak ada pertukaran yang terjadi dalam satu pass, ini berarti larik sudah terurut dan kita dapat menghentikan algoritma lebih awal. Optimasi ini dapat meningkatkan kinerja Bubble Sort dalam kasus di mana larik sudah hampir terurut.

Berikut adalah contoh implementasi Bubble Sort yang dioptimalkan:

def bubble_sort_optimized(data):
  n = len(data)
  for i in range(n-1):
    swapped = False  # Flag untuk menandai apakah ada pertukaran dalam pass ini
    for j in range(n-i-1):
      if data[j] > data[j+1]:
        data[j], data[j+1] = data[j+1], data[j]
        swapped = True
    if not swapped:  # Jika tidak ada pertukaran, larik sudah terurut
      break

# Contoh penggunaan
data = [64, 34, 25, 12, 22, 11, 90]
bubble_sort_optimized(data)
print("Array yang terurut:", data)

Perbedaan utama dalam implementasi yang dioptimalkan adalah penggunaan variabel swapped. Variabel ini diatur ke False di awal setiap pass dan diatur ke True jika ada pertukaran yang terjadi. Setelah loop dalam selesai, kita memeriksa nilai swapped. Jika swapped tetap False, ini berarti tidak ada pertukaran yang terjadi dalam pass tersebut, dan kita dapat menghentikan algoritma dengan menggunakan pernyataan break.

Kompleksitas Waktu Bubble Sort

Kompleksitas waktu adalah cara untuk mengukur seberapa cepat algoritma berjalan seiring dengan bertambahnya ukuran input. Bubble Sort memiliki kompleksitas waktu berikut:

• Kasus Terbaik (Best Case): O(n) – Terjadi ketika larik sudah terurut. Dalam kasus ini, algoritma hanya perlu melakukan satu pass untuk memverifikasi bahwa larik sudah terurut.
• Kasus Rata-rata (Average Case): O(n^2) – Terjadi ketika larik tidak terurut secara signifikan.
• Kasus Terburuk (Worst Case): O(n^2) – Terjadi ketika larik terurut terbalik.

Karena kompleksitas waktu kuadratiknya, Bubble Sort tidak efisien untuk larik berukuran besar. Untuk larik berukuran besar, algoritma pengurutan yang lebih canggih seperti Merge Sort atau Quick Sort lebih disarankan.

Kapan Bubble Sort Berguna?

Meskipun efisiensinya terbatas, Bubble Sort masih memiliki kegunaan dalam beberapa skenario:

• Larik Berukuran Kecil: Untuk larik berukuran kecil, perbedaan kinerja antara Bubble Sort dan algoritma pengurutan yang lebih canggih mungkin tidak signifikan. Dalam kasus ini, kemudahan implementasi Bubble Sort dapat menjadi keuntungan.
• Larik Hampir Terurut: Jika larik sudah hampir terurut, implementasi Bubble Sort yang dioptimalkan dapat berjalan dengan cukup cepat.
• Tujuan Pendidikan: Bubble Sort merupakan algoritma yang sangat baik untuk dipelajari sebagai langkah awal dalam memahami konsep pengurutan.

Kesimpulan

Bubble Sort adalah algoritma pengurutan sederhana yang mudah dipahami dan diimplementasikan. Meskipun tidak efisien untuk larik berukuran besar, ia memiliki kegunaan dalam kasus-kasus tertentu, seperti larik berukuran kecil atau larik yang hampir terurut. Memahami Bubble Sort adalah langkah penting dalam mempelajari algoritma pengurutan dan konsep-konsep dasar ilmu komputer. Sekarang, coba implementasikan Bubble Sort dengan berbagai variasi dan ukur performanya! Apakah performanya sesuai dengan teori yang sudah dibahas?