 |
| Minh họa |
Bài toán: cho một danh sách (python), mảng (c) các số nguyên hãy thực hiện thuật toán sắp xếp (SX) nổi bọt để sắp lại danh sách (mảng) trên theo chiều tăng dần.
Thực ra, nếu ta thực hiện thuật toán để từng phần tử nhẹ nổi lên trên thì khi ta xét hết tất cả các phần tử thì sẽ được một danh sách tăng dần. Ngược lại, nếu ta thực hiện thuật toán để từng phần tử nặng hơn chìm xuống dưới đến khi xét hết tất cả các phần tử thì ta vẫn được một danh sách tăng dần. Do vậy, thuật toán SX nổi bọt (bubble sort) cũng còn được gọi là thuật toán sinking (chìm) sort.
Ví dụ
Cho một danh sách các phần tử như sau:
a=[5, 2, 9, 1, 8, 3]
Ta sẽ thực hiện chạy thuật toán SX nổi bọt với ví dụ trên theo hai cách:
Cách 1
Nếu ta muốn SX theo kiểu nổi bọt thì ta sẽ xét các phần tử từ cuối danh sách lên đầu danh sách. Cứ hai phần tử gần nhau a[i] và a[i+1] mà a[i]>a[i+1] thì ta đổi chỗ chúng cho nhau, ngược lại thì không làm gì cả.
Ta xét lần lặp đầu tiên, duyệt các phần tử từ cuối lên đầu danh sách. Các bước như sau:
- Ta thấy, 8 và 3 không đúng trật tự tăng dần -> đổi chỗ 8 và 3 -> a lúc này sẽ là: a=[5, 2, 9, 1, 3, 8].
- Lúc này, ta thấy 1 và 3 đúng trật tự rồi, ta không làm gì cả và chuyển sang phần tử tiếp theo.
- Ta thấy, 9 và 1 không đúng trật tự -> đổi chỗ 9 và 1, lúc này danh sách a sẽ như sau: a=[5, 2, 1, 9, 3, 8] .
- Duyệt phần tử tiếp theo, 2 và 1 không đúng trật tự, ta đổi chỗ 2 và 1 và danh sách a lúc này là: a=[5, 1, 2, 9, 3, 8].
- Ta lại thấy, 5 và 1 không đúng trật tự, ta đổi chỗ 5 và 1 và a sẽ như sau: a=[1, 5, 2, 9, 3, 8].
- Vậy là sau một vòng lặp thì phần tử có giá trị nhỏ nhất đã "nổi" lên trên rồi, vòn lặp tiếp theo số nhỏ thứ hai sẽ nổi lên, tương tự như vậy sau một số lần lặp thì ta sẽ SX lại a theo thứ tự tăng dần.
Cách 2
Ngược lại với bubble sort, nếu ta muốn thực hiện thuật toán sinking sort thì ta sẽ duyệt các phần tử từ đầu danh sách đến cuối danh sách. Sau vòng lặp đầu tiên, phần tử "nặng" nhất sẽ chìm xuống dưới. Các bước trong vòng lặp đầu tiên sẽ như sau:
- Đầu tiên, 5 và 2 không đúng trật tự, ta đổi chỗi 5 với 2 và trạng thái của danh sách a lúc này sẽ là: a=[2, 5, 9, 1, 8, 3].
- Bước tiếp, 5 và 9 đúng trật tự, ta không phải làm gì cả.
- Lúc này, 9 và 1 không đúng trật tự, ta đổi chỗ 9 và 1 cho nhau ta được a sẽ như sau: a=[2, 5, 1, 9, 8, 3].
- Lai thấy, 9 và 8 không đúng trật tự, đổi chỗ 9 và 8 và trạng thái mới của a lúc này sẽ là: a=[2, 5, 1, 8, 9, 3].
- Cuối cùng, đổi chỗ 9 và 3 vì chúng không đúng trật tự, ta được danh sách a mới như sau: a=[2, 5, 1, 8, 3, 9].
- Lúc này, phần tử có giá trị lớn nhất là 9 đã bị dồn xuống cuối cùng danh sách. Ta thức hiện lần lặp tiếp theo thì phần tử nặng thứ hai (8) sẽ bị dồn xuống và cứ thế ta sẽ SX lại được danh sách a.
Phân tích
Với ví dụ trên thì ta thấy thuật toán này rất đơn giản đúng không? Bây giờ ta sẽ đi phân tích để xem ta cần thực hiện bao nhiêu lần lặp để thuật toán cho "kết quả" (đúng và nhanh) tốt nhất.
Ta thấy rằng, để làm cho phần tử "nhẹ" nhất ("nặng" nhất) nổi lên (chìm xuống) ta cần so sánh tất cả các phần tử đứng gần nhau theo một chiều nào đó. Do vậy, để cho tất cả các phần tử nổi lên hoặc chìm xuống đúng vị trí của mình ta lại cần một vòng lặp cho tất cả các phần tử. Như vậy, ta cần hai vòng lặp lồng nhau. Ta xét các trường hợp sau:
Ngây thơ
Với trường hợp này, hai vòng lặp đều có số lần lặp là n (n = độ dài của danh sách). Như vậy, độ phức tạp của thuật toán sẽ là O(n2).Python code:
C code (phiên bản mảng):
Bạn có thể xem mã C phiên bản con trỏ tại đây.
Gảm số lần lặp của vòng trong
Ta quan sát thấy rằng, sau lần đổi chỗ tất cả các phần tử đầu tiên thì phần tử nhẹ nhất (nặng nhất) đã vào vị trí của nó nên ta không cần quan tâm đến nó nữa. Như vậy, vòng so sánh thứ hai ta chỉ quan tâm đến n - 1 phần tử mà thôi (trừ phần tử đã vào vị trí), tương tự, sau mỗi vòng lặp ngoài thì vòng lặp bên trong lại giảm đi được một lần lặp. Như vậy, độ phức tạp của thuật toán lúc này là O(n*n-1/2).C code (phiên bản mảng):
Bạn có thể xem mã C phiên bản con trỏ tại đây.
So sánh với cách trên, ta thấy trong vòng lặp thứ hai, chỉ số chỉ chạy từ i = n-1 đến i = j mà thôi. Mỗi vòng lặp ngoài thì j tăng lên 1 có nghĩa là vòng lặp trong cũng giảm đi một lần so sánh.
Dùng cờ đánh dấu
Trong trường hợp, nếu danh sách đã cho đã được SX hoặc chỉ có một số ít các phần tử sai vị trí, nếu vẫn áp dụng cách thứ 2 thì ta vẫn phải thực hiện n vòng lặp ngoài trong danh sách đã được sắp xếp rồi. Để tránh tình trạng này, ta thêm vào một biết gọi là "cờ" để đánh dấu. Đầu vòng lặp ta sẽ đặt "cờ" là False (hoặc 0), nếu có bất kỳ sự đổi chỗ nào thì ta đặt lại "cờ" bằng True (hoặc 1). Như vậy, nếu sau một vòng lặp nào đó mà "cờ" vẫn bằng False (hoặc 0) thì ta có thể dừng thuật toán tại đây (vì rõ ràng lúc này danh sách đã được sắp xếp rồi, có lặp cũng vô ích).
Python code: C code (phiên bản mảng):Bạn có thể xem mã C phiên bản con trỏ tại đây.
So sánh với cách thứ hai, nếu không có sự sai vị trí nào thì chắc chắn danh sáng/mảng đã được sắp xếp. Ta có thể dựng thuật toán tại đó.
Lưu ý, mã nguồn C được biên dịch bởi trình biên dịch Linux GCC, có thể bạn cần chỉ sửa lại mã một chút cho phù hợp với trình biên dịch của bạn. Đồng thời, trong một project chỉ có duy nhất một tệp .c có hàm main thôi nhé, vì vậy hãy chạy từng tệp một, đừng tham lam cho tất cả vào.
Khá chi tiết và dễ hiểu đó a :))
Trả lờiXóa