Đồ Án Viết chương trình mô phỏng thuật toán sắp xếp vun đống

LỜI NÓI ĐẦU
Ngày nay, trong khoa học máy tính và trong toán học, các thuật toán sắp xếp (Sorting algorithms) giúp cho quá trình thực hiện sắp xếp các phần tử của một tập dữ liệu như danh sách (Link list), mảng (Array), cây (Tree), được diễn với số phần tử rất lớn trong khoảng thời gian ngắn theo 1 thứ tự tăng hoặc giảm dần.
Thông thường đối tượng của 1 tập dữ liệu là dạng số (number), ký tự, chữ số (character),
Một số ứng dụng về sắp xếp như: sắp xếp danh sách sinh viên theo thứ tự ABC, sắp xếp bảng lương của các nhân viên theo thứ tự giảm dần theo mức lương,
Ngoài ra, người lập trình còn sử dụng các thuật toán sắp xếp để làm trung gian cho các thuật toán tìm kiếm được diễn ra nhanh hơn.
Trên thực tế, các loại thuật toán sắp xếp sẽ có độ phức tạp về giải thuật riêng nên việc sử dụng tài nguyên bộ nhớ cũng khác nhau, dẫn đến thời gian xử lý tập dữ liệu cũng sẽ chênh lệch.
Những thuật toán sắp xếp này có thể được chia thành hai nhóm dựa theo độ phức tạp của chúng. Độ phức tạp của thuật toán (Algorithmic complexity) là một khai niệm khá rắc rối đòi hỏi sự tưởng tượng mà sẽ tốn nhiều thời gian để giải thích của người nghiên cứu, nhưng ở đây có thể hiểu thông qua mối tương quan trực tiếp giữa độ phức tạp của thuật toán và hiệu quả của nó. Độ phức tạp của thuật toán thường được kí hiệu bởi một hàm O, trong đó O biểu diễn độ phức tạp của thuật toán đi kèm với một giá trị n biểu diễn kích thước của số lần chạy tối đa mà thuật toán đó dựa vào để xử lý trên tập dữ liệu. Ví dụ, O(n) có nghĩa là thuật toán có độ phức tạp tuyến tính. Cụ thể hơn, nó sẽ mất thời gian gấp 10 lần cho việc xử lý trên tập dữ liệu có 100 phần tử so với tập chỉ có 10 phần tử (10 * 10 = 100). Nếu độ phức tạp là O(n2) (quadratic complexity), thì nó sẽ phải tiêu tốn thời gian gấp 100 lần để xử lý trên tập 100 phần tử so với tập dữ liệu chỉ gồm 10 phần tử.

Hiện nay các thuật toán sắp xếp được được phân thành 2 loại như sau:
- Nhóm thứ nhất có độ phức tạp là O(n2) bao gồm: sắp xếp nổi bọt (bubble sort), chèn trực tiếp (insertion sort), chọn trực tiếp (selection sort),
- Nhóm thứ hai có độ phức tạp là O(nlogn) gồm: sắp xếp vun đống (heap sort), sắp xếp trộn (merge sort), và sắp xếp nhanh (quick sort),
Bên cạnh độ phức tạp của thuật toán, tốc độ của các thuật toán sắp xếp có thể được so sánh dựa vào thực nghiệm có được từ việc thử trên các tập dữ liệu. Vì tốc độ sắp xếp có thể thay đổi rất nhiều tùy theo đặc điểm của dữ liệu, nên để các kết quả thống kê chính xác dựa trên kinh nghiệm đòi hỏi việc chạy các thuật toán nhiều lần trên các dữ liệu khác nhau và tính trung bình. Thông thường tập dữ liệu kiểm tra được tạo ngẫu nhiên.


MỤC LỤC

LỜI NÓI ĐẦU 4
THUẬT TOÁN SẮP XẾP VUN ĐỐNG (HEAP SORT) 5
I. Giới thiệu thuật toán sắp xếp vun đống (Heap sort) 5
II. Ý tưởng của thuật toán Heap sort 5
III. Các định nghĩa 7
1. Định nghĩa Heap 7
2. Các tính chất của Heap 7
IV. Giải thuật Heap sort 7
1. Các bước giải thuật 7
2. Ví dụ sắp xếp dãy thuật 8
V. Cài đặt thuật toán Heap sort 10
1. Thủ tục hiệu chỉnh dãy a1 , a2, a3, a4, , aright thành heap 10
2. Hiệu chỉnh heap, sắp xếp dãy 11
VI. KẾT LUẬN 11
VII. CHƯƠNG TRÌNH DEMO HEAP SORT 12