Algoritma Bubble Sort

Pendahuluan

Algoritma Bubble Sort adalah salah satu algoritma penyortiran yang paling sederhana. Algoritma ini bekerja dengan cara membandingkan elemen-elemen yang berdekatan dalam sebuah daftar dan menukarnya jika mereka berada dalam urutan yang salah. Proses ini diulangi terus menerus sampai daftar menjadi terurut.

Cara Kerja Pass Pertama

Diagram di bawah ini menggambarkan cara kerja pass pertama dari algoritma Bubble Sort.

Indeks dimulai dari posisi pertama (0) hingga posisi terakhir dari daftar yang belum diurutkan (n-2). Dalam daftar dengan 9 elemen di atas, loop berjalan dari 0 hingga 7. Untuk setiap pasangan elemen yang bersebelahan, kita bandingkan elemen saat ini dengan elemen berikutnya. Setelah pass pertama selesai, elemen terbesar (93) telah “mengambang” ke posisi terakhir dalam daftar. Untuk pass selanjutnya, n dikurangi 1 karena setelah setiap pass, elemen terbesar dari bagian yang tidak terurut sudah “mengambang” ke posisi akhir yang benar dalam daftar. Oleh karena itu, tidak perlu membandingkan elemen terakhir tersebut dalam pass berikutnya.

Penjelasan Langkah demi Langkah Semua Pass

Daftar Awal:

[54, 26, 93, 17, 77, 31, 44, 55, 20]

Pass 1:

Bandingkan 54 dan 26: 54 > 26, tukar. Daftar menjadi: [26, 54, 93, 17, 77, 31, 44, 55, 20]
Bandingkan 54 dan 93: 54 < 93, tidak ada perubahan.
Bandingkan 93 dan 17: 93 > 17, tukar. Daftar menjadi: [26, 54, 17, 93, 77, 31, 44, 55, 20]
Bandingkan 93 dan 77: 93 > 77, tukar. Daftar menjadi: [26, 54, 17, 77, 93, 31, 44, 55, 20]
Bandingkan 93 dan 31: 93 > 31, tukar. Daftar menjadi: [26, 54, 17, 77, 31, 93, 44, 55, 20]
Bandingkan 93 dan 44: 93 > 44, tukar. Daftar menjadi: [26, 54, 17, 77, 31, 44, 93, 55, 20]
Bandingkan 93 dan 55: 93 > 55, tukar. Daftar menjadi: [26, 54, 17, 77, 31, 44, 55, 93, 20]
Bandingkan 93 dan 20: 93 > 20, tukar. Daftar menjadi: [26, 54, 17, 77, 31, 44, 55, 20, 93]

Pass 2:

Bandingkan 26 dan 54: 26 < 54, tidak ada perubahan.
Bandingkan 54 dan 17: 54 > 17, tukar. Daftar menjadi: [26, 17, 54, 77, 31, 44, 55, 20, 93]
Bandingkan 54 dan 77: 54 < 77, tidak ada perubahan.
Bandingkan 77 dan 31: 77 > 31, tukar. Daftar menjadi: [26, 17, 54, 31, 77, 44, 55, 20, 93]
Bandingkan 77 dan 44: 77 > 44, tukar. Daftar menjadi: [26, 17, 54, 31, 44, 77, 55, 20, 93]
Bandingkan 77 dan 55: 77 > 55, tukar. Daftar menjadi: [26, 17, 54, 31, 44, 55, 77, 20, 93]
Bandingkan 77 dan 20: 77 > 20, tukar. Daftar menjadi: [26, 17, 54, 31, 44, 55, 20, 77, 93]

Pass 3:

Bandingkan 26 dan 17: 26 > 17, tukar. Daftar menjadi: [17, 26, 54, 31, 44, 55, 20, 77, 93]
Bandingkan 26 dan 54: 26 < 54, tidak ada perubahan.
Bandingkan 54 dan 31: 54 > 31, tukar. Daftar menjadi: [17, 26, 31, 54, 44, 55, 20, 77, 93]
Bandingkan 54 dan 44: 54 > 44, tukar. Daftar menjadi: [17, 26, 31, 44, 54, 55, 20, 77, 93]
Bandingkan 54 dan 55: 54 < 55, tidak ada perubahan.
Bandingkan 55 dan 20: 55 > 20, tukar. Daftar menjadi: [17, 26, 31, 44, 54, 20, 55, 77, 93]

Pass 4:

Bandingkan 17 dan 26: 17 < 26, tidak ada perubahan.
Bandingkan 26 dan 31: 26 < 31, tidak ada perubahan.
Bandingkan 31 dan 44: 31 < 44, tidak ada perubahan.
Bandingkan 44 dan 54: 44 < 54, tidak ada perubahan.
Bandingkan 54 dan 20: 54 > 20, tukar. Daftar menjadi: [17, 26, 31, 44, 20, 54, 55, 77, 93]

Pass 5:

Bandingkan 17 dan 26: 17 < 26, tidak ada perubahan.
Bandingkan 26 dan 31: 26 < 31, tidak ada perubahan.
Bandingkan 31 dan 44: 31 < 44, tidak ada perubahan.
Bandingkan 44 dan 20: 44 > 20, tukar. Daftar menjadi: [17, 26, 31, 20, 44, 54, 55, 77, 93]

Pass 6:

Bandingkan 17 dan 26: 17 < 26, tidak ada perubahan.
Bandingkan 26 dan 31: 26 < 31, tidak ada perubahan.
Bandingkan 31 dan 20: 31 > 20, tukar. Daftar menjadi: [17, 26, 20, 31, 44, 54, 55, 77, 93]

Pass 7:

Bandingkan 17 dan 26: 17 < 26, tidak ada perubahan.
Bandingkan 26 dan 20: 26 > 20, tukar. Daftar menjadi: [17, 20, 26, 31, 44, 54, 55, 77, 93]

Pass 8:

Bandingkan 17 dan 20: 17 < 20, tidak ada perubahan.

Hasil Akhir:

Setelah semua pass selesai, daftar menjadi terurut:
[ [17, 20, 26, 31, 44, 54, 55, 77, 93] ]

Algoritma Bubble Sort memastikan bahwa pada setiap pass, elemen terbesar “mengambang” ke posisi akhir dari subdaftar yang belum terurut. Dengan cara ini, daftar menjadi semakin terurut pada setiap pass.

Implementasi Python

Berikut ini adalah program Python yang mengimplementasikan Bubble Sort:

def bubble_sort(a_list):
   # Looping dari akhir list ke awal list (pass_num adalah jumlah elemen yang akan diproses dalam setiap iterasi)
   for pass_num in range(len(a_list) - 1, 0, -1):
      # Looping untuk membandingkan dan menukar elemen-elemen yang berdekatan
      for i in range(pass_num):
         # Jika elemen saat ini lebih besar dari elemen berikutnya, tukar elemen-elemen tersebut
         if a_list[i] > a_list[i + 1]:
            temp = a_list[i]
            a_list[i] = a_list[i + 1]
            a_list[i + 1] = temp

# Daftar yang akan diurutkan
a_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]

# Memanggil fungsi bubble_sort untuk mengurutkan a_list
bubble_sort(a_list)

# Mencetak daftar yang sudah diurutkan
print(a_list)

Mari kita lihat bagaimana algoritma ini bekerja langkah demi langkah:

Inisialisasi dan Loop Utama:
- Fungsi bubble_sort menerima sebuah daftar (a_list) sebagai argumen.
- Loop utama (for pass_num in range(len(a_list) - 1, 0, -1)) berjalan dari panjang daftar dikurangi 1 hingga 1, secara berkurang. Ini menentukan jumlah elemen yang akan diproses dalam setiap iterasi.
Loop Dalam untuk Membandingkan dan Menukar Elemen:
- Loop kedua (for i in range(pass_num)) berjalan dari indeks 0 hingga pass_num - 1. Di sinilah perbandingan dan penukaran elemen-elemen dilakukan.
- Jika elemen di indeks i lebih besar dari elemen di indeks i + 1, kedua elemen tersebut ditukar menggunakan variabel sementara (temp).
Proses Penukaran:
- Jika a_list[i] > a_list[i + 1], maka:

temp = a_list[i]
a_list[i] = a_list[i + 1]
a_list[i + 1] = temp

Elemen di i dan i + 1 ditukar sehingga elemen yang lebih besar bergerak ke posisi yang lebih tinggi dalam daftar.

Program ini adalah implementasi dasar dari algoritma Bubble Sort yang bekerja dengan kompleksitas waktu O(n^2) dalam kasus terburuk, di mana n adalah jumlah elemen dalam daftar.

algorithm programming python

Algoritma Bubble Sort