Đang chuẩn bị liên kết để tải về tài liệu:
BÀI GIẢNG GIẢI THUẬT VÀ LẬP TRÌNH - QUY HOẠCH ĐỘNG - LÊ MINH HOÀNG - 4

Có thể nhận xét thêm là QuickSort đệ quy cần thêm không gian nhớ cho Stack, còn HeapSort ngoài một nút nhớ phụ để thực hiện việc đổi chỗ, nó không cần dùng thêm gì khác. HeapSort tốt hơn QuickSort về phương diện lý thuyết bởi không có trường hợp tồi tệ nào HeapSort có thể mắc phải. Cũng nhờ có HeapSort mà giờ đây khi giải mọi bài toán có chứa mô-đun sắp xếp, ta có thể nói rằng độ phức tạp của thủ tục sắp xếp đó không quá O(nlog2n) | Cấu trúc dữ liệu và Giải thuật 95 thời gian thực hiện trung bình phức tạp hơn ta chỉ ghi nhận một kết quả đã chứng minh được là độ phức tạp trung bình của HeapSort cũng là O nlog2n . Có thể nhận xét thêm là QuickSort đệ quy cần thêm không gian nhớ cho Stack còn HeapSort ngoài một nút nhớ phụ để thực hiện việc đổi chỗ nó không cần dùng thêm gì khác. HeapSort tốt hơn QuickSort về phương diện lý thuyết bởi không có trường hợp tồi tệ nào HeapSort có thể mắc phải. Cũng nhờ có HeapSort mà giờ đây khi giải mọi bài toán có chứa mô-đun sắp xếp ta có thể nói rằng độ phức tạp của thủ tục sắp xếp đó không quá O nlog2n . 8.8. SẮP XẾP BẰNG PHÉP ĐẾM PHÂN PHỐI DISTRIBUTION COUNTING Có một thuật toán sắp xếp đơn giản cho trường hợp đặc biệt Dãy khoá ki k2 . kn là các số nguyên nằm trong khoảng từ 0 tới M TKey 0.M . Ta dựng dãy c0 c1 . cM các biến đếm ở đây cV là số lần xuất hiện giá trị V trong dãy khoá for V 0 to M do cV 0 Khởi tạo dãy biến đếm for i 1 to n do ck ck 1 Ví dụ với dãy khoá 1 2 2 3 0 0 1 1 3 3 n 10 M 3 sau bước đếm ta có co 2 d 3 c2 2 c3 3. Dựa vào dãy biến đếm ta hoàn toàn có thể biết được sau khi sắp xếp thì giá trị V phải nằm từ vị trí nào tới vị trí nào. Như ví dụ trên thì giá trị 0 phải nằm từ vị trí 1 tới vị trí 2 giá trị 1 phải đứng liên tiếp từ vị trí 3 tới vị trí 5 giá trị 2 đứng ở vị trí 6 và 7 còn giá trị 3 nằm ở ba vị trí cuối 8 9 10 0 0 1 1 1 2 2 3 3 3 Tức là sau khi sắp xếp Giá trị 0 đứng trong đoạn từ vị trí 1 tới vị trí c0. Giá trị 1 đứng trong đoạn từ vị trí c0 1 tới vị trí c0 c1. Giá trị 2 đứng trong đoạn từ vị trí c0 c1 1 tới vị trí c0 c1 c2. Giá trị v trong đoạn đứng từ vị trí c0 c1 . cv-1 1 tới vị trí c0 c1 c2 . cv. Để ý vị trí cuối của mỗi đoạn nếu ta tính lại dãy c như sau for V 1 to M do cV cV-1 cV Thì cV là vị trí cuối của đoạn chứa giá trị V trong dãy khoá đã sắp xếp. Muốn dựng lại dãy khoá sắp xếp ta thêm một dãy khoá phụ x1 x2 . xn. Sau đó duyệt lại dãy khoá k mỗi khi gặp khoá mang giá trị V ta đưa giá trị đó vào khoá xcv và giảm cv đi 1. .