Bubble sort (sắp xếp bằng cách đổi chỗ)
I. Mô tả phương pháp:
Phương pháp này sẽ duyệt danh sách nhiều lần, trong mỗi lần duyệt sẽ lần lượt so sánh cặp nút thứ i và thứ i+1 và đổi chỗ hai nút này nếu chúng không đúng thứ tự.
Ví dụ cho một dãy số đơn giản và sắp xếp cho nó tăng dần.
25 55 45 90 10
Và đây sẽ minh họa quá trình so sánh và đổi chỗ trong lần duyệt đầu tiên.
So sánh nút thứ i với nút thứ i+1 nếu nút thứ i > nút i+1 thì đổi chỗ 2 nút với nhau. Nếu không tiếp tục so sánh tiếp.
- So sánh 25 với 55:kiểm tra 25 < 55 -> Sai không đổi chỗ.
- So sánh tiếp 55 với phần tử tiếp theo là 45: 55 > 45 -> Đúng đổi chỗ 45 với 55
- So sánh tiếp 55 với 90: 55 < 90 -> sau không đổi chỗ.
- So sánh tiếp 90 với 10: 90 > 10 -> đúng đổi chỗ 90 cho 10.
Danh sách sau khi biến đổi lần thứ nhất.
25 45 55 10 90.
Ta nhận thấy phần tử 90 lớn nhất được đưa về cuối danh sách, cứ tuần tự kiểm tra n lần như vậy ta sẽ được một danh sách tăng dần.
OK chắc các bạn hiểu ý tưởng rồi chứ (dễ như ăn kẹo)

.
Tiếp giờ ta sẽ
Mô Tả Giải Thuật Bubble Sort
Dữ liệu nhập: Danh sách n nút chưa sắp xếp.
Dữ liệu xuất: Danh sách n nút đã sắp xếp.
Biến tạm: doicho
Hành động:
Gán doicho = true;
for(int i = 1;i < n && doicho = true;i++)
{
Gán doicho = flase;
for(j = 0;i < n-1; j++)
if(nodes[j] > nodes[j+1]))
{
Gán doicho = true;
Đỗi chỗ cho hai nút tại vị trí j và j+1
}
}
Kết thúc
Cài đặt giải thuật Bubble sort
void BubbleSort(int nodes[],int n) // n la so phan tu trong mang nodes[]
{
int temp,i,j;
bool doicho = true;
for(i = 1; i < n && doicho == true; i++)
{
doicho = false;
for(j = 0;j < n-i; j++)
if(nodes[j] < nodes[j+1])
{
doicho = true;
temp = nodes[j];
nodes[j] = nodes[j+1];
nodes[j+1] = temp;
}
}
}
Nhận xét: Giải thuật bubble sort dễ hiểu nhưng không tối ưu vì thời gian thực hiện giải thuật chậm.
cheer! (bắt trước anh ccom phát

)
(còn tiếp)