 |
| Thực hiện vun đống |
Rất may mắn có một người bạn giúp ta làm một việc như sau: người bạn đó sẽ sắp xếp số đồ vật của chúng ta thành một đống mà phần tử ở trên bao giờ cũng nhẹ hơn phần tử ở dưới. Như vậy, ta lấy được đồ vật nhỏ nhất và bỏ ra ngoài. Người bạn lại tiếp tục sắp lại đống đồ vật trên và ta lại chọn phần tử ở trên cao nhất - là phần tử nhẹ nhất trong đống nhưng nhẹ thứ hai trong danh sách các đồ vật. Cứ thế đến cuối cùng thì các phần tử được ta nhặt ra từ đống sẽ được sắp xếp.
Ngay lập tức ta thấy có một câu hỏi đặt ra là việc xếp lại cái đống đồ vật để cho ta chọn đồ vật nhẹ nhất có phức tạp và khó khăn hay không? Rất may nó lại khá đơn giản, post này sẽ giải thích kỹ hơn cho bạn.
- Thực hiện vun đống, mà cụ thể ở đây ta sẽ sử dụng cây nhị phân thỏa mãn điều kiện là nút gốc luôn có giá trị nhỏ hơn hoặc bằng hai nút con (không quan tâm đến trật tự giữa hai nút con trái và phải đâu nhé).
- Lấy phần tử gốc (phần tử cao nhất - nhỏ nhất) lưu vào một dãy mới và lại thực hiện bước 1 cho dãy còn lại. Tuy nhiên, để tiết kiệm bộ nhớ ta sẽ đổi chỗ phần tử gốc (đầu danh sách) cho phần tử cuối cùng và lúc này ta chỉ quan tâm danh sách mới gồm các phần tử từ đầu danh sách trở đi đến cuối dãy nhưng trừ phần tử cuối cùng.
Ta phải xây dựng một cây nhị phân, việc này cũng khá đơn giản khi ta lợi dụng tích chất của số học. Danh sách có các phần tử là: 0, 1, 2, 3, 4, ... n - 1 (danh sách n phần tử) thì ta sẽ quy định 1 và 2 là con của phần tử 0, 3 và 4 là con của phần tử 1, .... Một cách tổng quát: phần tử thứ i sẽ có hai con là 2*i+1 và 2*i+2 (lưu ý: quy định này áp dụng cho danh sách, mảng được đánh chỉ số từ 0 nhé như ngôn ngữ C, Python, Java).
Để dễ hình dung hơn ta sẽ xem xét một ví dụ:
a=[3, 6, 9, 2, 6, 8, 9, 1, 7, 21, 7, 12]
Ta sẽ thực hiện thao tác vun đống với danh sách trên, việc vun đống sẽ được thực hiện từ phải sang trái. Ta đánh số các phần tử như sau:
[3, 6, 9, 2, 6, 8, 9, 1, 7, 21, 7, 12]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Các thao tác lần lượt như sau:
- Ta xét phần tử cuối cùng (phần tử 11), ta thấy phần tử cha là phần tử số 5 (=8) đúng thứ tự nên không làm gì cả.
- Xét phần tử tiếp theo là phần tử thứ 10, ta thấy phần tử cha là phần tử 4 đúng thứ tự nên không làm gì cả.
- Tiếp tục phần tử thứ 9 lại thấy phần tử cha của phần tử 9 là phần tử 4 đúng thứ tự nên không làm gì và chuyển bước tiếp.
- Xét phần tử tiếp theo là phần tử 8 có giá trị (7) và phần tử cha của nó là phần tử 3 có giá trị 2 nên không đổi chỗ.
- Bước tiếp xét phần tử 7 có giá trị là 1 so với phần tử cha của nó (phần tử 3 có giá trị 2) sai thứ tự nên ta đổi chỗ. Lúc này danh sách như sau:
[3, 6, 9, 1, 6, 8, 9, 2, 7, 21, 7, 12]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] - Phần tử thứ 6 (giá trị 9) bằng giá trị của phần tử cha (phần tử 2).
- Phần tử thứ 5 có giá trị 8 nhỏ hơn giá trị của phần tử cha (phần tử 2 có giá trị 9) nên ta đổi chỗ.
[3, 6, 8, 1, 6, 9, 9, 2, 7, 21, 7, 12]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] - Bây giờ xét phần tử 4 có cha là phần tử 1 đúng thứ tự nên không làm gì cả.
- Tiếp tục xét phần tử 3 có giá trị là 1 nhỏ hơn giá trị của phần tử cha (phần tử 1 có giá trị 6) nên ta đổi chỗ hai phần tử này và được dãy mới như sau:
[3, 1, 8, 6, 6, 9, 9, 2, 7, 21, 7, 12]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] - Xét phần tử 2 có giá trị 8 lớn hơn giá trị của phần tử cha, ta chuyển sang bước tiếp theo.
- Xét phần tử 1 có giá trị 1 nhỏ hơn giá trị của phần tử cha (phần tử 0 có giá trị 3) đổi chỗ hai phần tử cho nhau, danh sách lúc này là:
[1, 3, 8, 6, 6, 9, 9, 2, 7, 21, 7, 12]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] - Lúc này phần tử nhỏ nhất đã được lên đầu dãy rồi. Kết thúc thao tác vun đống, danh sách bây giờ là một đống thỏa mãn phần tử cha luôn nhỏ hơn hoặc bằng hai phần tử con.
Sau khi thực hiện xong thao tác vung đống, ta sẽ thực hiện thao tác sắp xếp. Lúc phần tử nhỏ nhất trên đầu rồi. Ta sẽ nhặt phần tử này và bỏ sang một dãy mới. Nhưng để tiết kiệm không gian ta đổi chỗ phần tử đầu dãy với phần tử cuối cùng và tiếp tục vun đống với các phần tử từ đầu đến phần phần tử gần cuối cùng. Như vậy, ta sẽ thực hiện luận phiên: vung đống, đổi chỗ cho phần tử cuối cùng, vun đống dãy con, đổi chỗ cho phần tử cuối cùng của dãy con,...
Trong hình động dưới đây ta sẽ thực hiện luân phiên bước vun đống và nhặt phần tử cuối cùng sang danh sách mới. Lưu ý một chút là sau mỗi khi vung đống, ta đảo phần tử cuối dãy hiện tại cho phần tử đầu tiên và thực hiện vun lại, chính vì thế chỉ có một nhánh của cây thay đổi mà thôi. Vì vậy, mỗi bước vun đống ta sẽ mất log(n) thao tác thay đổi. Nên tổng cộng thời gian thực hiện thuật toán sẽ là log(1) + log(2) + ... + log(n).
Sau đây là các đoạn code ví dụ cài đặt thuật toán sắp xếp vung đống:
Python code:
C code (phiên bản con trỏ):
Trong các đoạn code trên, ta chú ý vào hai hàm là heap và heapsort. Hàm heap với hai tham số là danh sách cần vung đống (myList) và chỉ số cuối cùng (lastIndex). Chỉ số cuối cùng được sử dụng vì mỗi lần sau khi vung đống ta sẽ đảo phần tử nhỏ nhất (trên đỉnh đống) với phần tử dưới cùng nhất. Sau bước này, ta không xét phần tử vừa được đảo xuống cuối nên chỉ số cuối cùng giảm đi 1. Như vậy, ban đầu chỉ số lastIndex sẽ bằng kích thước danh sách - 1 (vì danh sách đánh chỉ số từ 0), cho đến khi lastIndex = 0 thì không phải vung đống nữa (vì chỉ có một phần tử thì vun làm gì).
Hàm heapsort thực hiện công việc vun đống rồi đảo phần tử trên đỉnh đống cho phần tử cuối cùng. Công việc này được thực hiện luân phiên, cuối cùng thì danh sách được sắp xếp theo chiều giảm dẫn.
Trong hàm main ta sẽ sử dụng cách in hoặc viết một đoạn code để đảo ngược dãy. Code đầy đủ bạn có thể xem ở các đường link sau: python, c language.
Nhận xét của tác giả:
Sắp xếp vung đống là một thuật toán cổ điện và rất đơn giản. Trong thuật toán này cần phải hình dung cách hoạt động của đống nhị phân (một dạng của cây nhị phân). Thuật toán này không có nhiều kỹ thuật phức tạp và nên là bài tập cho những người mới học.
Trong hình động dưới đây ta sẽ thực hiện luân phiên bước vun đống và nhặt phần tử cuối cùng sang danh sách mới. Lưu ý một chút là sau mỗi khi vung đống, ta đảo phần tử cuối dãy hiện tại cho phần tử đầu tiên và thực hiện vun lại, chính vì thế chỉ có một nhánh của cây thay đổi mà thôi. Vì vậy, mỗi bước vun đống ta sẽ mất log(n) thao tác thay đổi. Nên tổng cộng thời gian thực hiện thuật toán sẽ là log(1) + log(2) + ... + log(n).
 |
| Vung đống và chọn phần tử đầu tiên |
Python code:
C code (phiên bản con trỏ):
Trong các đoạn code trên, ta chú ý vào hai hàm là heap và heapsort. Hàm heap với hai tham số là danh sách cần vung đống (myList) và chỉ số cuối cùng (lastIndex). Chỉ số cuối cùng được sử dụng vì mỗi lần sau khi vung đống ta sẽ đảo phần tử nhỏ nhất (trên đỉnh đống) với phần tử dưới cùng nhất. Sau bước này, ta không xét phần tử vừa được đảo xuống cuối nên chỉ số cuối cùng giảm đi 1. Như vậy, ban đầu chỉ số lastIndex sẽ bằng kích thước danh sách - 1 (vì danh sách đánh chỉ số từ 0), cho đến khi lastIndex = 0 thì không phải vung đống nữa (vì chỉ có một phần tử thì vun làm gì).
Hàm heapsort thực hiện công việc vun đống rồi đảo phần tử trên đỉnh đống cho phần tử cuối cùng. Công việc này được thực hiện luân phiên, cuối cùng thì danh sách được sắp xếp theo chiều giảm dẫn.
Trong hàm main ta sẽ sử dụng cách in hoặc viết một đoạn code để đảo ngược dãy. Code đầy đủ bạn có thể xem ở các đường link sau: python, c language.
Nhận xét của tác giả:
Sắp xếp vung đống là một thuật toán cổ điện và rất đơn giản. Trong thuật toán này cần phải hình dung cách hoạt động của đống nhị phân (một dạng của cây nhị phân). Thuật toán này không có nhiều kỹ thuật phức tạp và nên là bài tập cho những người mới học.
Không có nhận xét nào:
Đăng nhận xét