Chạy tay bubble sort một lượt trên năm số là hiểu vì sao nó chậm

So hai số cạnh nhau, sai thì đổi

Đi từ trái sang phải, so hai phần tử cạnh nhau, sai thứ tự thì đổi chỗ. Một lần đi hết mảng gọi là một lượt. Lặp cho tới khi một lượt không đổi chỗ lần nào.

Một lượt đi hết mảng

1. So 5 và 1Sai thứ tự, đổi chỗ. Còn 1 5 4 2 8
2. So 5 và 4Đổi tiếp. Còn 1 4 5 2 8
3. So 5 và 2Đổi tiếp. Còn 1 4 2 5 8
4. So 5 và 8Đúng rồi, giữ nguyên. Số 8 đã về đúng chỗ

Cờ dừng sớm

Vì sao nó chậm

Số phép so sánh tăng theo bình phương số phần tử: gấp đôi dữ liệu thì chậm gấp bốn. 100 phần tử tốn khoảng 5.000 lần so sánh, 10.000 phần tử tốn khoảng 50 triệu.

Tại chỗ và ổn định

Nó làm ngay trên mảng gốc, chỉ tốn thêm một biến tạm. Hai phần tử bằng nhau giữ nguyên thứ tự cũ, tính chất đó gọi là ổn định và cần khi bạn sắp theo nhiều khoá liên tiếp.

Bubble sort: được gì, mất gì

Lưu lại để chạy tay sau

Loạt bài thuật toán sắp xếp cho dev Việt Nam.