tailieunhanh - Cấu trúc dữ liệu và giải thuật I - Bài 9

Sắp xếp danh sách Mục tiêu Giới thiệu các thuật toán sắp xếp phù hợp với danh sách liên kết | r A rw w Ấ 1 1 r 1 Bài 9 Sắp xếp danh sách Mục tiêu Giới thiệu các thuật toán sắp xếp phù hợp với danh sách liên kết Nội dung Các cách tiếp cận Môt số thuật toán hiệu qủa o Quicksort o Merge sort o Radix sort Bài tập Bài tập lý thuyất Bài tập thực hành I. Các cách tiếp cận Một danh sách có thứ tự danh sách được sắp là một danh sách mà các phần tử của nó được sắp xếp theo một thứ tự nào đó dựa trên một trường khoá. Ví dụ danh sách các phần tử số có thứ tự tăng là danh sách mà với mọi cặp phần tử X Y ta luôn có X Y nếu X xuất hiện trước Y trong danh sách danh sách có 1 hoặc không có phần tử nào được xem là một danh sách được sắp . Để sắp xếp một danh sách ta có thể thực hiện một trong 2 phương án sau Phương án 1 Hoán vị nội dung các phần tử trong danh sách thao tác trên vùng Info . Với phương án này có thể chọn một trong những thuật toán sắp xếp đã biết để cài đặt lại trên xâu như thực hiện trên mảng điểm khác biệt duy nhất là cách thức truy xuất đến các phần tử trên xâu thông qua liên kết thay vì chỉ số như trên mảng. Do dựa trên việc hoán vị nội dung của các phần tử phương pháp này đòi hỏi sử dụng thêm vùng nhớ trung gian nên chỉ thích hợp với các xâu có các phần tử có thành phần Info kích thước nhỏ. Hơn nữa số lần hoán vị có thể lên đến bậc n2 với xâu n phần tử. Khi kích thước của trường Info lớn việc hoán vị giá trị của hai phân tử sẽ chiếm chi phí đáng kể. Điều này sẽ làm cho thao tác xắp xếp chậm lại. Như vậy phương án này không tận dụng được các ưu điểm của xâu . Ví dụ Cài đặt thuật toán sắp xếp Chọn trực tiếp trên xâu void ListSelectionSort LIST l NODE min chỉ đến phần tử có giá trị nhỏ nhất trong xâu NODE p q p while p q p- pNext min p while q NULL if q- Info min- Info min q ghi nhận vị trí phần tử min hiện hành q q q- pNext Hoán vị nội dung 2 phần tử Hoanvi min- Info p- Info p p- pNext Phương án 2 Thay đổi các mối liên kết thao tác trên vùng Next Do các nhược điểm của các phương pháp sắp xếp theo phương án 1 khi dữ liệu lưu tại mỗi phần tử .