TAILIEUCHUNG - 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ử .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• giải thuật
• phương pháp sắp xếp
• tổ chức dữ liệu
• t đề án tin họ
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Bài giảng Cấu trúc dữ liệu
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• giáo trình cấu trúc dữ liệu
• bài tập cấu trúc dữ liệu
• đề cương cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Tài liệu Cấu trúc dữ liệu
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp