Bubble Sort Dalam C++: Contoh Program Dan Penjelasannya

Bubble Sort dalam C++: Panduan Komprehensif untuk Pengurutan yang Efisien

Pendahuluan

Bubble sort merupakan salah satu algoritma pengurutan paling sederhana dan mudah dipahami. Algoritma ini bekerja dengan membandingkan elemen yang berdekatan dalam sebuah array dan menukarnya jika urutannya tidak benar. Proses ini diulang hingga tidak ada lagi pertukaran yang dilakukan, yang menandakan bahwa array telah diurutkan.

Cara Kerja Bubble Sort

Bubble sort bekerja dengan cara sebagai berikut:

1. Mulailah dari elemen pertama dalam array.
2. Bandingkan elemen tersebut dengan elemen berikutnya.
3. Jika elemen pertama lebih besar dari elemen kedua, tukar kedua elemen tersebut.
4. Lanjutkan membandingkan dan menukar elemen hingga mencapai akhir array.
5. Ulangi langkah 1-4 hingga tidak ada lagi pertukaran yang dilakukan.

Implementasi Bubble Sort dalam C++

Berikut adalah implementasi bubble sort dalam C++:

#include <iostream>#include <vector>using namespace std;void bubbleSort(vector<int>& arr) {  int n = arr.size();  bool swapped;  do {    swapped = false;    for (int i = 0; i < n - 1; i++) {      if (arr[i] > arr[i + 1]) {        swap(arr[i], arr[i + 1]);        swapped = true;      }    }    n--;  } while (swapped);}int main() {  vector<int> arr = {5, 3, 1, 2, 4};  bubbleSort(arr);  for (int i : arr) {    cout << i << " ";  }  return 0;}

Contoh Penggunaan

Contoh penggunaan bubble sort dapat dilihat pada kode berikut:

int main() {  vector<int> arr = {5, 3, 1, 2, 4};  bubbleSort(arr);  for (int i : arr) {    cout << i << " ";  }  return 0;}

Output dari kode tersebut adalah:

1 2 3 4 5

Analisis Kompleksitas

Kompleksitas waktu terburuk dari bubble sort adalah O(n^2), di mana n adalah jumlah elemen dalam array. Hal ini karena algoritma harus membandingkan setiap elemen dengan semua elemen lainnya.

Kelebihan dan Kekurangan Bubble Sort

Kelebihan:

• Sederhana dan mudah diimplementasikan.
• Stabil, artinya elemen dengan nilai yang sama mempertahankan urutan relatifnya.

Kekurangan:

• Tidak efisien untuk array besar.
• Kompleksitas waktu terburuknya adalah O(n^2).

Aplikasi Bubble Sort

Bubble sort dapat digunakan untuk mengurutkan data dalam berbagai aplikasi, seperti:

• Mengurutkan daftar nama.
• Mengurutkan nilai dalam database.
• Mengurutkan elemen dalam sebuah array.

Kesimpulan

Bubble sort adalah algoritma pengurutan yang sederhana dan mudah diimplementasikan. Namun, algoritma ini tidak efisien untuk array besar karena kompleksitas waktunya yang O(n^2). Untuk array besar, algoritma pengurutan yang lebih efisien, seperti quick sort atau merge sort, lebih disukai.

Lokasi:

Berbagi :