Struktur Data - Algoritma Bubble Sort
Bubble sort adalah algoritme pengurutan sederhana. Algoritme pengurutan ini adalah algoritme berbasis perbandingan di mana setiap pasangan elemen yang berdekatan dibandingkan dan elemen tersebut ditukar jika tidak berurutan. Algoritma ini tidak cocok untuk kumpulan data besar karena kompleksitas kasus rata-rata dan terburuknya adalah Ο (n 2 ) di manan adalah jumlah item.
Bagaimana Cara Kerja Bubble Sort?
Kami mengambil array yang tidak disortir untuk contoh kami. Pengurutan gelembung membutuhkan waktu Ο (n 2 ) jadi kami menjaganya agar tetap singkat dan tepat.
Jenis gelembung dimulai dengan dua elemen pertama, membandingkannya untuk memeriksa mana yang lebih besar.
Dalam hal ini, nilai 33 lebih besar dari 14, jadi sudah ada di lokasi yang diurutkan. Selanjutnya, kami membandingkan 33 dengan 27.
Kami menemukan bahwa 27 lebih kecil dari 33 dan kedua nilai ini harus ditukar.
Array baru akan terlihat seperti ini -
Selanjutnya kami membandingkan 33 dan 35. Kami menemukan bahwa keduanya berada pada posisi yang sudah diurutkan.
Kemudian kami pindah ke dua nilai berikutnya, 35 dan 10.
Kita tahu bahwa 10 lebih kecil 35. Oleh karena itu mereka tidak diurutkan.
Kami menukar nilai-nilai ini. Kami menemukan bahwa kami telah mencapai akhir larik. Setelah satu iterasi, array akan terlihat seperti ini -
Tepatnya, kami sekarang menunjukkan bagaimana sebuah array akan terlihat setelah setiap iterasi. Setelah iterasi kedua, akan terlihat seperti ini -
Perhatikan bahwa setelah setiap iterasi, setidaknya satu nilai bergerak di akhir.
Dan ketika tidak ada swap yang diperlukan, bubble sort mengetahui bahwa array sudah diurutkan sepenuhnya.
Sekarang kita harus melihat beberapa aspek praktis dari jenis gelembung.
Algoritma
Kami berasumsi list adalah larik nelemen. Kami selanjutnya berasumsi bahwaswap fungsi menukar nilai elemen array yang diberikan.
begin BubbleSort(list)
for all elements of list
if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
return list
end BubbleSort
Pseudocode
Kami mengamati dalam algoritme bahwa Bubble Sort membandingkan setiap pasangan elemen array kecuali jika seluruh array sepenuhnya diurutkan dalam urutan menaik. Ini dapat menyebabkan beberapa masalah kompleksitas seperti bagaimana jika array tidak perlu lagi bertukar karena semua elemen sudah naik.
Untuk mengatasi masalah ini, kami menggunakan satu variabel bendera swappedyang akan membantu kami melihat apakah ada pertukaran yang terjadi atau tidak. Jika tidak ada pertukaran yang terjadi, yaitu array tidak memerlukan pemrosesan lagi untuk disortir, itu akan keluar dari loop.
Pseudocode dari algoritma BubbleSort dapat ditulis sebagai berikut -
procedure bubbleSort( list : array of items )
loop = list.count;
for i = 0 to loop-1 do:
swapped = false
for j = 0 to loop-1 do:
/* compare the adjacent elements */
if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true
end if
end for
/*if no number was swapped that means
array is sorted now, break the loop.*/
if(not swapped) then
break
end if
end for
end procedure return list
Penerapan
Satu lagi masalah yang tidak kami tangani dalam algoritme asli kami dan kodesemu improvisasinya, adalah bahwa, setelah setiap iterasi, nilai tertinggi berada di akhir larik. Karenanya, iterasi berikutnya tidak perlu menyertakan elemen yang sudah diurutkan. Untuk tujuan ini, dalam implementasi kami, kami membatasi loop dalam untuk menghindari nilai yang sudah diurutkan.
Untuk mengetahui tentang implementasi bubble sort dalam bahasa pemrograman C, silakan klik disini .