Thuật Toán Sắp Xếp Nổi Bọt (Bubble Sort) - Góc Học IT

Trang chủ » Nổi Bọt Là Gì » Thuật Toán Sắp Xếp Nổi Bọt (Bubble Sort) - Góc Học IT

Có thể bạn quan tâm

1. Ý tưởng thuật toán sắp xếp nổi bọt

Giả sử cần sắp xếp tăng dần một danh sách có n phần tử a0, a1, a2,…,an-1.

Xuất phát từ cuối danh sách, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về đúng vị trí theo thứ tự tăng dần. Cuối cùng, phần tử đầu tiên trong danh sách sẽ là phần tử nhỏ nhất.

Sau đó, sẽ không xét đến phần tử đầu tiên đó nữa ở bước tiếp theo. Do vậy, ở lần xử lý thứ i, phần tử đầu được xét sẽ có vị trí là i.

Lặp lại các bước xử lý trên cho đến khi không còn cặp phần tử nào để xét.

2. Các bước thực hiện thuật toán

Bước 1: i = 0;//lần xử lý đầu tiên

Bước 2: j = n-1;//duyệt từ cuối dãy ngược về vị trí i

Trong khi (j > i) xét trường hợp: Nếu a[j]<a[j-1] thì đổi chổ a[j] và a[j-1].

j = j-1;

Bước 3: i = i+1; //lần xử lý kế tiếp

Nếu i = n-1 -> hết dãy -> Dừng.

Ngược lại -> Lặp lại Bước 2.

Minh họa thuật toán sắp xếp nổi bọt

Hoạt động của thuật toán sắp xếp nổi bọt (Bubble Sort)
Minh họa thuật toán Bubble Sort (Nguồn: codelearn.io)

3. Cài đặt thuật toán sắp xếp nổi bọt với C++

#include <iostream> using namespace std; void Bubble_Sort(int a[],int n){ int i, j; for (i=0; i<n-1; i++){ for (j=n-1; j>i; j--){ if(a[j]<a[j-1]){//nếu sai vị trí thì đổi chỗ swap(a[j], a[j-1]); } } } } void main() { int a[5] = {8, 4, 1, 6, 5}; Bubble_Sort(a, 5); cout<<"Mang sau khi sap xep:"<<endl; for(int i=0;i<5;i++){ cout<<a[i]<<" "; } system("pause"); }
Kết quả
Mang sau khi sap xep: 1 4 5 6 8

Đánh giá giải thuật

Số phép so sánh trong trường hợp tốt nhất hoặc xấu nhất đều là n(n-1)/2. Độ phức tạp thuật toán là O(n2).

  • Nhập xuất (input/output) cơ bản trong Python
  • Giới thiệu môn học Cấu trúc dữ liệu và giải thuật
  • Lập trình giao tiếp cảm biến LM35 với board mạch Arduino
  • Cài đặt Python và môi trường lập trình với Visual Studio Code
  • Hàm khởi tạo (constructor) __init__() của class trong Python
5/5 - (2 bình chọn)Bài trước và bài sau trong môn học<< Thuật toán sắp xếp chọn trực tiếp (Selection Sort)Thuật toán sắp xếp chèn trực tiếp (Insertion Sort) >>

Từ khóa » Nổi Bọt Là Gì