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

Trang chủ » độ Phức Tạp Của Thuật Toán Sắp Xếp Nổi Bọt » 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).

  • Sử dụng Eclipse để lập trình C++
  • Cú pháp và cách sử dụng toán tử điều kiện trong C++
  • Giới thiệu môn học Cấu trúc dữ liệu và giải thuật
  • Arduino là gì? Cấu trúc của board mạch Arduino Uno
  • Tính đóng gói (encapsulation) và đa hình (polymorphism) 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 » độ Phức Tạp Của Thuật Toán Sắp Xếp Nổi Bọt