Pengantar Algoritma Bubble Sort

Penyortiran adalah salah satu operasi paling dasar yang dapat Anda terapkan pada data. Anda dapat mengurutkan elemen dalam bahasa pemrograman yang berbeda menggunakan berbagai algoritme pengurutan seperti Quick Sort, Bubble Sort, Merge Sort, Insertion Sort, dll. Bubble Sort adalah algoritma yang paling sederhana di antara semua ini.

Dalam artikel ini, Anda akan belajar tentang cara kerja algoritma Bubble Sort, pseudocode dari Bubble Sort algoritma, kompleksitas ruang dan waktu, dan implementasinya dalam berbagai bahasa pemrograman seperti C++, Python, C, dan JavaScript.

Bagaimana Algoritma Bubble Sort Bekerja?

Bubble Sort adalah algoritme pengurutan paling sederhana yang berulang kali menelusuri daftar, membandingkan elemen yang berdekatan, dan menukarnya jika urutannya salah. Konsep ini dapat dijelaskan lebih efisien dengan bantuan sebuah contoh. Pertimbangkan array yang tidak disortir dengan elemen berikut: {16, 12, 15, 13, 19}.

Contoh:

Di sini elemen yang berdekatan dibandingkan dan jika tidak dalam urutan menaik, mereka ditukar.

Pseudocode dari Algoritma Bubble Sort

Dalam kode semu, algoritma Bubble Sort dapat dinyatakan sebagai:

bubbleSort (Arr[], ukuran)
// loop untuk mengakses setiap elemen array
untuk i=0 hingga ukuran-1 lakukan:
// loop untuk membandingkan elemen array
untuk j=0 hingga ukuran-i-1 lakukan:
// membandingkan elemen yang berdekatan
jika Arr[j] > Arr[j+1] maka
// tukar mereka
tukar (Arr[j], Arr[j+1])
berakhir jika
berakhir untuk
berakhir untuk
akhir

Algoritma di atas memproses semua perbandingan bahkan jika array sudah diurutkan. Ini dapat dioptimalkan lebih lanjut dengan menghentikan algoritme jika loop dalam tidak menyebabkan pertukaran apa pun. Ini akan mengurangi waktu eksekusi algoritma.

Dengan demikian, pseudocode dari algoritma Bubble Sort yang dioptimalkan dapat dinyatakan sebagai:

bubbleSort (Arr[], ukuran)
// loop untuk mengakses setiap elemen array
untuk i=0 hingga ukuran-1 lakukan:
// periksa apakah terjadi pertukaran
ditukar = salah
// loop untuk membandingkan elemen array
untuk j=0 hingga ukuran-i-1 lakukan:
// membandingkan elemen yang berdekatan
jika Arr[j] > Arr[j+1] maka
// tukar mereka
tukar (Arr[j], Arr[j+1])
ditukar = benar =
berakhir jika
berakhir untuk
// jika tidak ada elemen yang tertukar itu berarti array diurutkan sekarang, lalu putuskan loop.
jika (tidak ditukar) maka
istirahat
berakhir jika
berakhir untuk
akhir

Kompleksitas Waktu dan Ruang Bantu dari Algoritma Bubble Sort

Kompleksitas waktu kasus terburuk dari Algoritma Bubble Sort adalah O(n^2). Itu terjadi ketika array dalam urutan menurun dan Anda ingin mengurutkannya dalam urutan menaik atau sebaliknya.

Kompleksitas waktu kasus terbaik dari Algoritma Bubble Sort adalah O(n). Itu terjadi ketika array sudah diurutkan.

Terkait: Apa itu Notasi Big-O?

Kompleksitas waktu kasus rata-rata dari Algoritma Bubble Sort adalah O(n^2). Itu terjadi ketika elemen-elemen array berada dalam urutan campur aduk.

Ruang tambahan yang diperlukan untuk algoritma Bubble Sort adalah O(1).

Implementasi C++ dari Algoritma Bubble Sort

Di bawah ini adalah implementasi C++ dari algoritma Bubble Sort:

// implementasi C++ dari of
// algoritma Bubble Sort yang dioptimalkan
#sertakan 
menggunakan namespace std;
// Fungsi untuk melakukan Bubble Sort
void bubbleSort (int arr[], int ukuran) {
// Loop untuk mengakses setiap elemen array
untuk (int i=0; i// Variabel untuk memeriksa apakah terjadi swapping
bool ditukar = salah;
// loop untuk membandingkan dua elemen array yang berdekatan
untuk (int j = 0; j < (ukuran-i-1); j++) {
// Membandingkan dua elemen array yang berdekatan
jika (arr[j] > arr[j + 1]) {
// Tukar kedua elemen jika mereka
// tidak dalam urutan yang benar
int suhu = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = suhu;
ditukar = benar;
}
}
// Jika tidak ada elemen yang ditukar itu berarti array diurutkan sekarang,
// lalu putuskan loop.
if (ditukar == salah) {
istirahat;
}
}
}
// Mencetak elemen array
void printArray (int arr[], int ukuran) {
untuk (int i = 0; saya < ukuran; saya++) {
cout << arr[i] << " ";
}
cout<}
int utama() {
int arr[] = {16, 12, 15, 13, 19};
// Mencari panjang array length
int ukuran = ukuran (arr) / ukuran (arr[0]);
// Mencetak array tak terurut yang diberikan
cout << "Array Tidak Diurutkan: " << endl;
printArray (arr, ukuran);
// Memanggil fungsi bubbleSort()
bubbleSort (arr, ukuran);
// Mencetak array yang diurutkan
cout << "Array Diurutkan dalam Urutan Ascending:" << endl;
printArray (arr, ukuran);
kembali 0;
}

Keluaran:

Array yang tidak disortir: 
16 12 15 13 19 
Array yang Diurutkan dalam Urutan Ascending:
12 13 15 16 19

Implementasi Python dari Algoritma Bubble Sort

Di bawah ini adalah implementasi Python dari algoritma Bubble Sort:

# Implementasi Python dari
# algoritma Bubble Sort yang dioptimalkan
# Fungsi untuk melakukan Bubble Sort
def bubbleSort (arr, ukuran):
# Loop untuk mengakses setiap elemen daftar
untuk i dalam rentang (ukuran-1):
# Variabel untuk memeriksa apakah terjadi pertukaran
ditukar = Salah
# loop untuk membandingkan dua elemen daftar yang berdekatan
untuk j dalam rentang (ukuran-i-1):
# Membandingkan dua elemen daftar yang berdekatan
jika arr[j] > arr[j+1]:
suhu = arr[j]
arr[j] = arr[j+1]
arr[j+1] = suhu
ditukar = Benar
# Jika tidak ada elemen yang ditukar itu berarti daftar diurutkan sekarang,
# lalu putuskan lingkarannya.
jika ditukar == Salah:
istirahat
# Mencetak elemen daftar
def printArray (arr):
untuk elemen di arr:
cetak (elemen, akhir=" ")
mencetak("")
arr = [16, 12, 15, 13, 19]
# Menemukan panjang daftar
ukuran = len (arr)
# Mencetak daftar yang tidak disortir yang diberikan
print("Daftar Tidak Diurutkan:")
printArray (arr)
# Memanggil fungsi bubbleSort()
bubbleSort (arr, ukuran)
# Mencetak daftar yang diurutkan
print("Daftar yang Diurutkan dalam Urutan Naik:")
printArray (arr)

Keluaran:

Daftar yang tidak disortir:
16 12 15 13 19 
Daftar yang Diurutkan dalam Urutan Ascending:
12 13 15 16 19

Terkait: Cara Menggunakan For Loop dengan Python

C Implementasi Algoritma Bubble Sort

Di bawah ini adalah implementasi C dari algoritma Bubble Sort:

// C implementasi dari
// algoritma Bubble Sort yang dioptimalkan
#sertakan 
#sertakan 
// Fungsi untuk melakukan Bubble Sort
void bubbleSort (int arr[], int ukuran) {
// Loop untuk mengakses setiap elemen array
untuk (int i=0; i// Variabel untuk memeriksa apakah terjadi swapping
bool ditukar = salah;
// loop untuk membandingkan dua elemen array yang berdekatan
untuk (int j = 0; j < (ukuran-i-1); j++) {
// Membandingkan dua elemen array yang berdekatan
jika (arr[j] > arr[j + 1]) {
// Tukar kedua elemen jika mereka
// tidak dalam urutan yang benar
int suhu = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = suhu;
ditukar = benar;
}
}
// Jika tidak ada elemen yang ditukar itu berarti array diurutkan sekarang,
// lalu putuskan loop.
if (ditukar == salah) {
istirahat;
}
}
}
// Mencetak elemen array
void printArray (int arr[], int ukuran) {
untuk (int i = 0; saya < ukuran; saya++) {
printf("%d", arr[i]);
}
printf("\n");
}
int utama() {
int arr[] = {16, 12, 15, 13, 19};
// Mencari panjang array length
int ukuran = ukuran (arr) / ukuran (arr[0]);
// Mencetak array tak terurut yang diberikan
printf("Array Tidak Diurutkan: \⁠n");
printArray (arr, ukuran);
// Memanggil fungsi bubbleSort()
bubbleSort (arr, ukuran);
// Mencetak array yang diurutkan
printf("Array Diurutkan dalam Urutan Ascending: \⁠n");
printArray (arr, ukuran);
kembali 0;
}

Keluaran:

Array yang tidak disortir: 
16 12 15 13 19 
Array yang Diurutkan dalam Urutan Ascending: 
12 13 15 16 19

Implementasi JavaScript dari Algoritma Bubble Sort

Di bawah ini adalah implementasi JavaScript dari algoritma Bubble Sort:

// implementasi JavaScript dari of
// algoritma Bubble Sort yang dioptimalkan
// Fungsi untuk melakukan Bubble Sort
fungsi bubbleSort (arr, ukuran) {
// Loop untuk mengakses setiap elemen array
untuk (misalkan i=0; saya// Variabel untuk memeriksa apakah terjadi swapping
var ditukar = salah;
// loop untuk membandingkan dua elemen array yang berdekatan
untuk (misalkan j=0; j// Membandingkan dua elemen array yang berdekatan
jika (arr[j] > arr[j+1]) {
// Tukar kedua elemen jika mereka
// tidak dalam urutan yang benar
biarkan suhu = arr[j];
arr[j] = arr[j+1];
arr[j+1] = suhu;
ditukar = benar;
}
// Jika tidak ada elemen yang ditukar itu berarti array diurutkan sekarang,
// lalu putuskan loop.
if (ditukar == salah) {
istirahat;
}
}
}
}
// Mencetak elemen array
fungsi printArray (arr, ukuran) {
untuk (misalkan i=0; sayadocument.write (arr[i] + " ");
}
dokumen.tulis("
")
}
var arr = [16, 12, 15, 13, 19];
// Mencari panjang array length
var ukuran = arr.length;
// Mencetak array tak terurut yang diberikan
document.write("Array Tidak Diurutkan: 
");
printArray (arr, ukuran);
// Memanggil fungsi bubbleSort()
bubbleSort (arr, ukuran);
// Mencetak array yang diurutkan
document.write("Array Diurutkan dalam Urutan Ascending: 
");
printArray (arr, ukuran);

Keluaran:

Array yang tidak disortir:
16 12 15 13 19
Array yang Diurutkan dalam Urutan Ascending:
12 15 13 16 19

Sekarang Anda Memahami Cara Kerja Algoritma Bubble Sort

Bubble Sort adalah algoritma pengurutan paling sederhana dan terutama digunakan untuk memahami dasar-dasar pengurutan. Bubble Sort juga dapat diimplementasikan secara rekursif, tetapi tidak memberikan keuntungan tambahan untuk melakukannya.

Menggunakan Python, Anda dapat mengimplementasikan algoritma Bubble Sort dengan mudah. Jika Anda tidak terbiasa dengan Python dan ingin memulai perjalanan Anda, memulai dengan skrip "Hello World" adalah pilihan yang tepat.

Bagaimana Memulai Dengan Python Menggunakan Skrip "Hello World"

Python adalah salah satu bahasa pemrograman yang paling populer digunakan saat ini. Ikuti tutorial ini untuk memulai dengan skrip Python pertama Anda.

Baca Selanjutnya

Tentang Penulis