Bubble Sort

Pelajaran 13 dari 26 dalam kursus Array di C++ di Coddy.

Cara lain untuk mengurutkan array disebut bubble sort. Idenya adalah membandingkan setiap pasangan angka yang berdekatan dan menukarnya jika angka di sebelah kanan lebih kecil daripada angka di sebelah kiri, sampai kita mencapai akhir.

1. Deklarasikan variabel bernama counter dan inisialisasikan dengan 1. Counter menyimpan jumlah elemen yang sudah diurutkan.

2. Buat while loop dengan kondisi iterasi hingga counter kurang dari n.

int counter=1;
while(counter<n){
     
}

3. Buat for loop di dalam while loop dan lakukan iterasi dari 0 hingga n-counter kali. Karena sejumlah elemen sesuai nilai counter sudah diurutkan, kita tidak perlu memeriksanya lagi.

int counter=1;
while(counter<n){
     for(int i=0;i<n-counter;i++){
     
     }
}

4. lalu bandingkan elemen ke-i dengan elemen berikutnya, yaitu elemen ke-(i+1), dan jika arr[i]>arr[i+1], tukar keduanya.

Kita bisa melihat bahwa pada iterasi pertama while loop eksternal, elemen terbesar terdorong ke posisi terakhir. Karena itu, kita mengabaikan bagian tersebut pada iterasi berikutnya dan menambahkan 1 ke counter.

int counter=1;
while(counter<n){
  for(int i=0;i<n-counter;i++){
    if(arr[i]>arr[i+1]){
      int temp=arr[i];
      arr[i]=arr[i+1];
      arr[i+1]=temp;
    }
  }
  counter++;
}

Analisis kompleksitas waktu

Kita menjalankan while loop sebanyak n kali dan di setiap while loop, sebuah for loop berjalan hampir sebanyak n kali. Oleh karena itu, kompleksitas waktunya menjadi O(n²).

Untuk melihat cara kerja algoritma ini secara bertahap.

Visualisasi Bubble Sort

Tantangan

Urutkan array yang diberikan menggunakan algoritma bubble sort dan cetak setiap elemen yang indeksnya ganjil. Pisahkan elemen dengan satu spasi.

Coba sendiri

#include<iostream>
using namespace std;


int main(){
  
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
  cin>>arr[i];
}

//Code Here




return 0;

}