Cùng một bài, đọc bằng chữ. Nhanh hơn và tìm lại được bằng Ctrl+F.
Một lượt trên mảng 5 số
- So sánhNhìn hai số cạnh nhau: 5 và 3
- Đổi chỗ5 lớn hơn 3 nên đổi, thành 3 5 8 1 9
- Đi tiếpSang cặp kế: 5 và 8, đã đúng thứ tự
- Hết lượtĐến cuối mảng là xong một lượt
Một lượt gọi là một pass
Đi từ đầu đến cuối mảng một lần gọi là một pass. Bubble sort chạy pass mới cho đến khi có một pass không phải đổi chỗ lần nào. Lúc đó mảng đã đúng thứ tự.
Trường hợp tốt nhất
Mảng đã đúng thứ tự sẵn thì một pass là xong
Cờ dừng sớm
Vì sao chậm khi mảng lớn
Mỗi pass so gần hết mảng, và số pass cũng tăng theo số phần tử. Nhân hai thứ đó lại thành n². Dữ liệu tăng gấp đôi thì số phép so sánh tăng khoảng gấp bốn.
Bubble sort được gì, mất gì
Ưu điểm
Code ngắn, đọc một lần là hiểu
Ổn định, hai số bằng nhau giữ nguyên thứ tự
Có cờ dừng sớm cho mảng đã đúng sẵn
Nhược điểm
n² phép so sánh, mảng lớn là thấy chậm
Không ai dùng trong production
Đổi chỗ nhiều hơn selection sort
Bài sau: selection sort
Cùng là n², nhưng đổi chỗ ít hơn hẳn. Lưu lại để so hai bài.
