Sắp xếp nổi bọt

Bài học 13 trên 26 trong khóa học Mảng trong C++ của Coddy.

Một cách sắp xếp mảng khác có tên là sắp xếp nổi bọt. Ý tưởng là so sánh từng cặp số liền kề và hoán đổi nếu số bên phải nhỏ hơn số bên trái, cho đến khi đến cuối mảng.

1. Khai báo biến có tên counter và khởi tạo biến này bằng 1. counter lưu số phần tử đã được sắp xếp.

2. Tạo một vòng lặp while với điều kiện lặp cho đến khi counter nhỏ hơn n.

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

3. Tạo một vòng lặp for bên trong vòng lặp while và cho vòng lặp chạy từ 0 đến n-counter lần. Vì counter phần tử đã được sắp xếp nên ta không cần kiểm tra lại chúng.

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

4. Sau đó, so sánh phần tử thứ i với phần tử kế tiếp, tức phần tử thứ (i+1), và nếu arr[i]>arr[i+1] thì hoán đổi chúng.

Ta có thể thấy trong lần lặp đầu tiên của vòng lặp while bên ngoài, phần tử lớn nhất được đẩy về vị trí cuối cùng. Vì vậy, ta bỏ qua phần đó ở lần lặp tiếp theo và tăng counter thêm 1.

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++;
}

Phân tích độ phức tạp thời gian

Vòng lặp while chạy n lần và trong mỗi lần lặp while, vòng lặp for chạy gần n lần. Vì vậy, độ phức tạp thời gian là O(n²).

Để xem thuật toán thực sự hoạt động như thế nào qua từng bước.

Trực quan hóa sắp xếp nổi bọt

Thử thách

Sắp xếp mảng đã cho bằng thuật toán sắp xếp nổi bọt (bubble sort) và in ra mọi phần tử có chỉ số lẻ. Ngăn cách các phần tử bằng một dấu cách.

Tự làm thử

#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;

}