Cho danh sách dãy số a gồm n phần tử (a1, a2, ..., an). Sắp xếp dãy a theo thứ tự tăng dần.
|
Duyệt lần lượt các phần tử từ phần tử thứ 1 đến phần tử thứ (n - 1), i chạy từ 1 đến nhỏ hơn n. Với mỗi phần tử đang xét: Duyệt từ cuối danh sách đến sau phần tử đang xét, j chạy từ n đến lớn hơn i. Nếu phần tử đứng sau nhỏ hơn phần tử đứng trước (a[j] < a[j - 1]) thì hoán đổi hai phần tử. |
Lưu ý: Lần duyệt thứ i thì phần tử nhỏ thứ i được đưa về vị trí thứ i.
Cho dãy số: 10 8 9 7 5
a) Sắp xếp dãy số theo thứ tự tăng dần (không giảm) dùng thuật toán sắp xếp nổi bọt.
Giải: Đầu vào: 10 8 9 7 5
Lần 1:
Xét vị trí thứ nhất, so sánh từ cuối dãy về sau phần tử thứ nhất.
10 8 9 5 7
10 8 5 9 7
10 5 8 9 7
5 10 8 9 7
Lần 2:
Xét vị trí thứ hai, so sánh từ cuối dãy về sau phần tử thứ hai.
5 10 8 7 9
5 10 7 8 9
5 7 10 8 9
Lần 3:
Xét vị trí thứ ba, so sánh từ cuối dãy về sau phần tử thứ ba.
5 7 10 8 9
5 7 8 10 9
Lần 4:
Xét vị trí thứ tư, so sánh từ cuối dãy về sau phần tử thứ tư.
5 7 8 9 10
Kết luận:
Đầu ra (dãy đã được sắp xếp tăng dần): 5 7 8 9 10
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cout << "Nhap so luong phan tu, n = ";
cin >> n;
int a[n];
cout << "Nhap danh sach cac so:\n";
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
for(int i = 0; i < n - 1; i++)
{
cout << "\nLan " << i + 1 << ":\n";
for(int j = n - 1; j > i; j--)
{
cout << "So sanh a[" << j << "] = " << a[j]
<< " va a[" << j - 1 << "] = " << a[j - 1];
if(a[j] < a[j - 1])
{
swap(a[j], a[j - 1]);
cout << " -> Doi cho\n";
}
else
{
cout << " -> Khong doi\n";
}
for(int k = 0; k < n; k++)
{
cout << a[k] << " ";
}
cout << "\n";
}
}
return 0;
}
Code C++ đối chiếu kết quả sau mỗi lần so sánh:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int chon;
do
{
system("cls"); // Xoa man hinh
int n;
cout << "Nhap so luong phan tu, n = ";
cin >> n;
int a[n];
cout << "Nhap danh sach cac so:\n";
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
// Bubble Sort
for(int i = 0; i < n - 1; i++)
{
cout << "\nLan " << i + 1 << ":\n";
for(int j = n - 1; j > i; j--)
{
// Neu sai thu tu thi doi cho
if(a[j] < a[j - 1])
{
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
}
// In mang sau moi lan xet
for(int k = 0; k < n; k++)
{
cout << a[k] << " ";
}
cout << "\n";
}
}
// Menu lua chon
cout << "\n====================\n";
cout << "0 - Thoat\n";
cout << "1 - Chay tiep\n";
cout << "Hay chon: ";
cin >> chon;
}
while(chon == 1);
cout << "\nDa thoat chuong trinh!\n";
return 0;
}
Độ phức tạp thuật toán:
| Trường hợp | Độ phức tạp |
|---|---|
| Tốt nhất | O(n) |
| Trung bình | O(n2) |
| Xấu nhất | O(n2) |
Bubble Sort dễ hiểu, dễ cài đặt nhưng không hiệu quả với dữ liệu lớn.