Penjelasan algoritma Bubble Sort dan contoh implementasinya | by Anaf Naufalian

Anaf Naufalian

Sep 5, 2023

Kali ini saya akan menjelaskan apa itu algoritma bubble sort dan bagaimana cara kerja algoritma tersebut dan bagaimana mengimplementasikannya, disini saya akan menggunakan bahasa kotlin untuk mengimplementasikan dan menjelaskannya.

[other]Bubble Sort Visualization[/other]

Algoritma bubble sort atau bisa juga disebut pengurutan tenggelam (sinking sort) adalah algoritma pengurutan yang paling mudah dibandingkan algoritma pengurutan lainnya seperti selection sort, merge sort, radix sort, dll. Algoritma bubble sort ini mengurutkan nilai dengan cara membandingkan nilai saat ini dengan nilai selanjutnya, jika kedua nilai tersebut lebih besar atau lebih kecil (sesuai implementasinya, ascending order atau descending order) maka kedua nilai tersebut di swap atau ditukar posisinya sampai semua nilainya sudah terurut. Agar lebih mudah untuk memahami, lihat contoh dibawah.

Misalnya kita mempunyai array dengan nilai [6, 2, 1, 5, 4, 3], dan kita ingin mengurutkannya dengan ascending order atau dari nilai yang terkecil sampai yang terbesar.

Langkah pertama, buat fungsi “swap”:

fungsi ini akan kita gunakan untuk menukar nilai didalam array tanpa membuat instance array baru. Cara kerjanya yaitu:

1. buat variable “temp”, variable ini akan kita gunakan untuk menyimpan elemen dari array di index ke-i
2. tukar elemen diindex ke-i dengan elemen diindex ke-j
3. tukar elemen diindex ke-j dengan nilai dari variable “temp” (elemen diindex ke-i sebelum diubah)

/**
 * Swap value dari index i ke j, dan index j ke i
 */
private fun swap(arr: Array<Int>, i: Int, j: Int) {
    val temp = arr[i] // simpan nilai arr[i] ke dalam variable temp
    arr[i] = arr[j] // ganti nilai di index ke-i dengan nilai di index ke-j
    arr[j] = temp // ganti nilai di index j dengan nilai dari variable temp (nilai di index ke-i sebelum diubah)
}

Langkah kedua, buat fungsi “shouldSwap”:

karena kita ingin algoritma bubble sort yang kita buat bisa mengurutkan nilai dari yang terkecil ke yang terbesar (ascending) atau dari yang terbesar ke yang terkecil (descending), maka kita membuat fungsi shouldSwap yang berfungsi untuk mengecek apakah kedua nilai yang diberikan (n1 dan n2) harus ditukar atau tidak. Fungsi ini mengembalikan nilai true jika kedua nilai yang diberikan harus ditukar, false jika kedua nilai tidak boleh ditukar

Fungsi ini mempunyai 3 parameter yaitu n1, n2, dan ascending.

1. n1: nilai yang akan dibandingkan dengan n2
2. n2: nilai yang akan dibandingkan dengan n1
3. ascending: order pengurutan, true jika ingin mengurutkan dari yang terkecil ke yang terbesar (ascending), false jika ingin mengurutkan dari yang terbesar ke yang terkecil (descending)

/**
 * Cek apakah kedua nilai [n1] dan [n2] harus ditukar
 *
 * @param n1 nilai ke-1
 * @param n2 nilai ke-2
 * @param ascending sort order
 *
 * @return true jika kedua nilai tersebut harus ditukar, false otherwise
 */
private fun shouldSwap(n1: Int, n2: Int, ascending: Boolean): Boolean {
    return if (ascending) n1 < n2 else n1 > n2
}

Langkah ketiga, buat fungsi “bubbleSort”:

Di fungsi inilah algoritma penyortiran akan dilakukan. Fungsi ini memiliki 2 parameter yaitu arr dan ascending.

1. arr: Array yang akan disortir, bertipe Integer
2. ascending: order pengurutan

/**
 * @param arr array
 * @param ascending sort order, ascending (true) smallest to greatest, descending (false) otherwise
 */
fun bubbleSort(arr: Array<Int>, ascending: Boolean = true) {
    // Jika array kosong atau hanya berisi satu elemen saja, batalkan penyortiran
    if (arr.size <= 1) return
    // Iterasi sebanyak size array
    // Variable "x" tidak dipakai
    for (x in 0 until arr.size) {
        for (i in 0 until arr.size) {
            // Jika "i" adalah index terakhir, maka hentikan perulangan
            // Jika tidak dihentikan, maka akan terjadi error IndexOutOfBoundsException di bagian "arr[i + 1]"
            if (i == arr.size - 1) break
            
            // Cek apakah kedua nilai harus di tukar
            val shouldSwap = shouldSwap(arr[i + 1], arr[i], ascending)
            // Jika kedua nilai harus ditukar, maka tukar kedua nilai tersebut
            if (shouldSwap) swap(arr, i, i + 1)
        }
    }
}

Lihat kode diatas, dibaris pertama didalam blok kode fungsi bubbleSort kita mengecek apakah array mempunyai elemen yang lebih kecil atau sama dengan satu, jika benar maka kita tidak akan melakukan penyortiran, jika salah maka penyortiran akan dilakukan.

Selanjutnya kita melakukan iterasi/perulangan sebanyak x kali atau sebanyak jumlah elemen didalam array.

Didalam blok kode perulangan for selanjutnya kita akan melakukan iterasi lagi, dengan variabel i adalah index, dibaris selanjutnya kita akan memeriksa apakah index saat ini adalah index terakhir, jika iya, maka hentikan iterasi, jika tidak, lanjutkan iterasi. Mengapa kita harus memeriksa apakah index saat ini adalah index terakhir?.

Ingat! indeks pertama itu dimulai dari NOL (0), tetapi ada juga dibeberapa bahasa pemrograman yang dimulai dari SATU (1).

Coba perhatikan kode dibagian arr[i + 1], maksud dari kode ini adalah kita akan mengambil elemen yang berada diindex selanjutnya dari index i, Contoh misalnya kita mempunyai array dengan isi sebagai berikut [6, 2, 1, 5, 4, 3], misal index i saat ini berada diindex ke-2 (1), maka index selanjutnya atau arr[i + 1] berada diindex ke-3 (5).

Balik lagi ke pertanyaan diatas, mengapa kita harus memeriksa apakah index saat ini adalah index terakhir?, supaya saat index i berada diindex terakhir, program akan menghentikan iterasinya, jika kita tidak memeriksa kondisi tersebut, maka saat index i berada diindex terakhir program akan melempar error IndexOutOfBoundsException yaitu error yang didapat ketika kita ingin mengambil elemen yang berada diluar jangkauan.

Oke, selanjutnya kita akan memeriksa apakah kedua nilai yang berada diindex i dan i + 1 harus ditukar, disini kita akan menggunakan fungsi shouldSwap yang sudah kita buat, untuk penjelasannya baca diatas.

Lalu dibaris selanjutnya, jika value dari variabel shouldSwap bernilai “true”, maka tukar elemen yang berada diindex i dan index i + 1, jika tidak maka jangan ditukar.

Jika kita menjalankan fungsi bubbleSort diatas dengan array yang kita buat tadi, maka setiap iterasi, elemen-elemen yang berada didalam array akan berubah seperti dibawah.

Seperti itulah cara kerja algoritma bubble sort dan contoh implementasinya, terima kasih sudah membaca, semoga bermanfaat.

Full code

/**
 * Swap value dari index i ke j, dan index j ke i
 */
private fun swap(arr: Array<Int>, i: Int, j: Int) {
    val temp = arr[i] // simpan nilai arr[i] ke dalam variable temp
    arr[i] = arr[j] // ganti nilai di index ke-i dengan nilai di index ke-j
    arr[j] = temp // ganti nilai di index j dengan nilai dari variable temp (nilai di index ke-i sebelum diubah)
}
/**
 * Cek apakah kedua nilai [n1] dan [n2] harus ditukar
 *
 * @param n1 nilai ke-1
 * @param n2 nilai ke-2
 * @param ascending sort order
 *
 * @return true jika kedua nilai tersebut harus ditukar, false otherwise
 */
private fun shouldSwap(n1: Int, n2: Int, ascending: Boolean): Boolean {
    return if (ascending) n1 < n2 else n1 > n2
}
/**
 * @param arr array
 * @param ascending sort order, ascending (true) smallest to greatest, descending (false) otherwise
 */
fun bubbleSort(arr: Array<Int>, ascending: Boolean = true) {
    // Jika array kosong atau hanya berisi satu elemen saja, batalkan penyortiran
    if (arr.size <= 1) return
    // Iterasi sebanyak size array
    // Variable "x" tidak dipakai
    for (x in 0 until arr.size) {
        for (i in 0 until arr.size) {
            // Jika "i" adalah index terakhir, maka hentikan perulangan
            // Jika tidak dihentikan, maka akan terjadi error IndexOutOfBoundsException di bagian "arr[i + 1]"
            if (i == arr.size - 1) break
            // Cek apakah kedua nilai harus di tukar
            val shouldSwap = shouldSwap(arr[i + 1], arr[i], ascending)
            // Jika kedua nilai harus ditukar, maka tukar kedua nilai tersebut
            if (shouldSwap) swap(arr, i, i + 1)
        }
    }
}

Kode yang dipersingkat

/**
 * Swap value dari index i ke j, dan index j ke i
 */
private fun swap(arr: Array<Int>, i: Int, j: Int) {
    arr[i] = arr[j].also { arr[j] = arr[i] }
}
/**
 * Cek apakah kedua nilai [n1] dan [n2] harus ditukar
 *
 * @param n1 nilai ke-1
 * @param n2 nilai ke-2
 * @param ascending sort order
 *
 * @return true jika kedua nilai tersebut harus ditukar, false otherwise
 */
private fun shouldSwap(n1: Int, n2: Int, ascending: Boolean): Boolean = if (ascending) n1 < n2 else n1 > n2
/**
 * @param arr array
 * @param ascending sort order, ascending (true) smallest to greatest, descending (false) otherwise
 */
fun bubbleSort(arr: Array<Int>, ascending: Boolean = true) {
    if (arr.size <= 1) return
    for (x in arr.indices) {
        for (i in arr.indices) {
            if (i == arr.size - 1) break
            if (shouldSwap(arr[i + 1], arr[i], ascending)) swap(arr, i, i + 1)
        }
    }
}