tailieunhanh - Algorithms Programming - Thuật Toán Số phần 5

Cấu trúc dữ liệu và Giải thuật QuickSort gặp nhược điểm trong trường hợp suy biến nhưng xác suất xảy ra trường hợp này rất nhỏ. HeapSort thì mã lệnh hơi phức tạp và khó nhớ, nhưng nếu cần chọn ra m phần tử lớn nhất trong dãy khoá thì dùng HeapSort sẽ không phải sắp xếp lại toàn bộ dãy. | Cấu trúc dữ liệu và Giải thuật 115 Quicksort gặp nhược điểm trong trường hợp suy biến nhưng xác suất xảy ra trường hợp này rất nhỏ. HeapSort thì mã lệnh hơi phức tạp và khó nhớ nhưng nếu cần chọn ra m phần tử lớn nhất trong dãy khoá thì dùng HeapSort sẽ không phải sắp xếp lại toàn bộ dãy. MergeSort phải đòi hỏi thêm một không gian nhớ phụ nên áp dụng nó trong trường hợp sắp xếp trên file. Còn ShellSort thì hơi khó trong việc đánh giá về thời gian thực thi nó là sửa đổi của thuật toán sắp xếp chèn nhưng lại có tốc độ tốt mã lệnh đơn giản và lượng bộ nhớ cần huy động rất ít. Tuy nhiên những nhược điểm của bốn phương pháp này quá nhỏ so với ưu điểm chung của chúng là nhanh. Hơn nữa chúng được đánh giá cao không chỉ vì tính tổng quát và tốc độ nhanh mà còn là kết quả của những cách tiếp cận khoa học đối với bài toán sắp xếp. Những thuật toán trên không chỉ đơn thuần là cho ta hiểu thêm về một cách sắp xếp mới mà kỹ thuật cài đặt chúng với mã lệnh tối ưu cũng dạy cho chúng ta nhiều điều Kỹ thuật sử dụng số ngẫu nhiên kỹ thuật chia để trị kỹ thuật dùng các biến với vai trò luân phiên nên nắm vững nội dung của những thuật toán đó mà cách thuộc tốt nhất chính là cài đặt chúng vài lần với các ràng buộc dữ liệu khác nhau nếu có thể thử được trên hai ngôn ngữ lập trình thì rất tốt và cũng đừng quên kỹ thuật sắp xếp bằng chỉ số. Bài tập Bài 1 Viết thuật toán QuickSort không đệ quy Bài 2 Hãy viết những thuật toán sắp xếp nêu trên với danh sách những xâu ký tự gồm 3 chữ cái thường để sắp xếp chúng theo thứ tự từ điển. Bài 3 Hãy viết lại tất cả những thuật toán nêu trên với phương pháp sắp xếp bằng chỉ số trên một dãy số cần sắp không tăng giảm dần . Bài 5 Cho một danh sách thí sinh gồm n người mỗi người cho biết tên và điểm thi hãy chọn ra m người điểm cao nhất. Giải quyết bằng thuật toán có độ phức tạp tính toán trung bình O n Bài 6 Thuật toán sắp xếp bằng cơ số trực tiếp có ổn định không Tại sao Bài 7 Cài đặt thuật toán sắp xếp trộn hai đường tự nhiên Bài 8 Tìm hiểu .