Pengertian Algoritma Bubble Sort
Algoritma Bubble Sort adalah teknik pengurutan data yang menukar dua data yang berdekatan jika urutan datanya salah. Untuk Algoritma ini dapat mengurutkan data dari besar ke kecil (ascending) dan dari kecil ke besar (descending). Algoritma ini tidak cocok untuk kumpulan data yang besar karena kompleksitas algoritma ini adalah 0 () dimana n adalah jumlah elemen.
Jadi, Algoritma bubble sort adalah proses pengurutan yang secara bertahap memindahkan data ke lokasi yang benar. Oleh karena itu, algoritma ini disebut “bubble” atau dalam bahasa Indonesia disebut gelembung. Fungsi dari algoritma ini adalah untuk mengurutkan data dari yang terkecil sampai yang terbesar (ascending) atau sebaliknya (descending).
Konsep Algoritma Bubble Sort
- Algoritma dimulai dari elemen tertua.
- Bandingkan 2 elemen pertama dari daftar. Jika elemen pertama lebih besar dari yang kedua atau sebaliknya (dalam urutan menaik atau menurun), swap dilakukan.
- Langkah 2 dan 3 diulang untuk elemen kedua dan ketiga, dan seterusnya sampai akhir elemen.
- Jika tidak ada lagi pertukaran elemen, daftar elemen diurutkan.
- Setiap pasangan data: x[j] dengan x[j 1], untuk setiap j = 1, …, n-1 harus memenuhi urutan, yaitu urutkan:
Ascending: x[j] < x[j+1]
Descending: x[j] > x[j+1]
Proses Algoritma Bubble Sort
Algoritma bubble sort memiliki dua jenis proses, yaitu Ascending (pengurutan data dari terkecil ke terbesar) dan Decreasing proses ascending (pengurutan data dari terbesar ke terkecil). Apa perbedaan antara proses bottom-up dan top-down? Lihat pembahasan di bawah ini:
1. Proses Ascending
Kami akan memberikan contoh agar Anda memahami proses ascending dalam algoritma bubble sort. Berikut adalah rangkaian angka yang kita lakukan misalnya: [5, 12, 3, 19, 1, 47].
Ini adalah langkah bubble sort dengan metode ascending:
2. Proses Descending
Kami akan memberikan contoh yang mirip dengan satu di atas agar Anda memahami proses descending dalam algoritma bubble sort, yang merupakan urutan angka: [5, 12, 3, 19, 1, 47] Ini adalah langkah pengurutan bubble sort dengan metode descending:
Kompleksitas Algoritma Bubble Sort
Kompleksitas algoritma Bubble sort dapat dilihat dari beberapa jenis kasus, yaitu kasus terburuk, kasus rata-rata lapangan dan kasus terbaik.
1. Kondisi Best Case
Dalam hal ini, data yang diurutkan dicadangkan. Sehingga perbandingan hanya dilakukan (n-1) kali, dengan satu kali iterasi. Perbandingan hanya dilakukan untuk mengecek urutan data. Contohnya dapat dilihat pada susunan data “1 2 3 4” di bawah ini:
Di atas proses dapat dilihat bahwa tidak ada pertukaran lokasi data. Oleh karena itu, iterasi berikutnya tidak dijalankan. Perbandingan faktor dilakukan sebanyak tiga kali. Proses perbandingan pada kondisi ini hanya dilakukan (n-1) kali. Persamaan Big-O yang diperoleh dari proses ini adalah O(n).
2. Kondisi Worst-Case
Dalam hal ini, data terkecil berada di bagian bawah tabel. Contohnya dapat dilihat pada pengurutan data “4 3 2 1” di bawah ini:
lebih kecil bergerak ke awal langkah. Dengan kata lain, untuk memindahkan data yang lebih kecil dari urutan keempat ke urutan pertama membutuhkan tiga iterasi, ditambah satu untuk memverifikasi data. Sehingga banyaknya proses pada kondisi terburuk dapat dirumuskan sebagai berikut:
“Jumlah proses = n2+n” (3)
Pada persamaan (3) di atas, n adalah banyaknya elemen yang akan diurutkan. Oleh karena itu, notasi Big-O yang diperoleh adalah O(n2).
3. Kondisi Average-Case
Dalam kondisi kasus rata-rata, jumlah iterasi ditentukan dari data mana yang memiliki pergeseran kiri paling banyak. Ini dapat direpresentasikan dengan mengurutkan array, misalnya string angka (1 8 6 2). Dari (1 8 6 2) dapat dilihat bahwa penjumlahan akan mengalami transisi sebagai bilangan prima 2, ganda.
iterasi, ditambah satu iterasi untuk memeriksa data. Dengan kata lain, jumlah proses perbandingan dapat dihitung sebagai berikut.
“Jumlah proses = x2+x” (4)
Pada persamaan (4) di atas, x adalah selisih maksimum. Dalam hal ini, x tidak pernah lebih besar dari n.
Algoritma Bubble Sort untuk Pengurutan.
Pengurutan merupakan proses dasar yang ada dalam algoritma dan stuktur data. Terdapat banyak algoritma pengurutan yang sering digunakan, namun pada tulisan kali ini akan dibahas mengenai dasar algoritma Bubble Sort. Algortima ini merupakan algortima pengurutan sederhana dan biasanya dipelajari sebagai pokok bahasan seputar pengurutan.
Algoritma Bubble Sort ini merupakan proses pengurutan yang secara berangsur-angsur berpindah ke posisi yang tepat karena itulah dinamakan Bubble yang artinya gelembung. Algoritma ini akan mengurutkan data dari yang terbesar ke yang terkecil (ascending) atau sebaliknya (descending).
Secara sederhana, bisa didefenisikan algoritma Bubble Sort adalah pengurutan dengan cara pertukaran data dengan data disebelahnya secara terus menerus sampai dalam satu iterasi tertentu tidak ada lagi perubahan.
Untuk belajar algoritma Bubble Sort ini kita hanya perlu memahami cara yang digunakan untuk mengurutkan data, sederhananya algoritma ini menggunakan perbandingan dalam operasi antar elemennya. Di bawah ini merupakan gambaran dari algoritma Bubble Sort dengan array “3 1 4 2 8”.
Proses pertama
(3 1 4 2 8) menjadi (1 3 4 2 8)
(1 3 4 2 8) menjadi (1 3 4 2 8)
(1 3 4 2 8) menjadi (1 3 2 4 8)
(1 3 2 4 8) menjadi (1 3 2 4 8)
Proses kedua
(1 3 2 4 8) menjadi (1 3 2 4 8)
(1 3 2 4 8) menjadi (1 2 3 4 8)
(1 2 3 4 8) menjadi (1 2 3 4 8)
(1 2 3 4 8) menjadi (1 2 3 4 8)
Proses ketiga
(1 2 3 4 8) menjadi (1 2 3 4 8)
(1 2 3 4 8) menjadi (1 2 3 4 8)
(1 2 3 4 8) menjadi (1 2 3 4 8)
(1 2 3 4 8) menjadi (1 2 3 4 8)
Jika kita perhatikan proses diatas, para proses kedua data sudah terurut dengan benar. Tetapi algoritma Bubble Sort tetap berjalan hingga proses kedua berakhir. Proses ketiga masih terus berjalan karena pada algoritma Bubble Sort maksud terurut itu adalah tidak ada satupun penukaran pada suatu proses. Proses ketiga ini dilakukan untuk verifikasi data.
Algoritma Bubble Sort ini mempunyai kelebihan dan kekurangan, untuk kelebihannya metode ini merupakan metode paling sederhana untuk mengurutkan data. Selain sederhana, algoritma Bubble Sort mudah dipahami. Sementara itu, kekurangannya terletak pada efisiensi.
Bubble Sort ini merupakan metode pengurutan yang tidak efisien karena ketika mengurutkan data yang sangat besar akan sangat lambat prosesnya. Selain itu, jumlah pengulangan akan tetap sama jumlahnya meskipun data sudah cukup terurut.
