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 đa n – 1 lần tráo đổi phần tử, còn trường hợp sắp xếp nổi bọt thì tối đa n*(n-1) lần tráo đổi (Trường hợp danh sách sắp theo thứ tự ngược lại). Nhưng ưu điểm trông thấy rõ của phương pháp Nổi bọt là sau mỗi bước thì danh sách dần “ổn định” hơn. Nên có thể không cần chạy hết vòng lặp danh sách đã được theo thứ tự.
2. Ví dụ
Bên dưới là ví dụ sắp xếp mảng số nguyên theo phương pháp nổi bọt được thực hiện từng bước. Bước 0 là trạng thái ban đầu của danh sách. Ta thấy sau mỗi bước thì các phần tử đầu tiên lần lượt được đưa vào thứ tự, các phần tử còn lại cũng dần ổn định hơn. Đến bước 6 thì đã hoàn thành công việc sắp xếp.
3. Mô phỏng Thuật toán với mã nguồn Csharp
Ví dụ bên dưới xây dựng phương thức BubbleSort trong 1 class với thuộc tính là mảng cần sắp xếp. Constructure đưa vào cho biết số lượng phần tử của mảng, giá trị của các phần tử được khởi tạo ngẫu nhiên. Phương thức show() dùng để xuất các phần tử trong mảng ra màn hình.
Lời bình mới nhất