1. Bài toán sắp xếp Nổi bọt
Như đã biết ở bài viết trước về thuật toán Sắp xếp chọn ta thấy rằng sau mỗi vòng lặp ta lựa được một phần tử nhỏ nhất đưa về đầu danh sách, các phần tử còn lại hầu như không ảnh hưởng. Ta thấy rằng kết quả của vòng lặp trước không ảnh hưởng đến vòng lặp sau. Trong bài viết này chúng ta sẽ xét tới thuật toán sắp xếp Nổi bọt – Cải tiển hơn so với Thuật toán sắp xếp chọn.
Với thuật toán này, sẽ có 2 vòng lặp lồng nhau. Tại mỗi vòng lặp con sẽ chạy từ cuối danh sách trở về đầu danh sách. tại mỗi bước sẽ so sánh 2 phần tử kế cận nhau nếu phần tử nào nhỏ hơn sẽ được đảo về phía trước. Trong mỗi vòng lặp con, phần tử nhỏ nhất sẽ lần lượt được đưa về đầu dòng theo phương pháp tráo đổi – Đúng với tư tưởng “Nổi bọt” phần tử nhỏ sẽ dần được nổi lên trên cùng. Đặc điểm tối ưu hơn so với Sắp xếp chọn là tại mỗi vòng lặp con do có quá trình tráo đổi phần tử nhỏ về đầu dãy nên các phần tử lớn dần được đưa về cuối dãy và đồng thời những giá trị nhỏ cũng dần được đưa về đầu dãy. Đối với phương pháp sắp xếp chọn có tối …..
