- CÁC THUẬT TOÁN SẮP XẾP MỤC TIÊU Hoàn tất bài thực hành này, sinh viên có thể. - Hiểu được các thuật toán sắp xếp: Selection Sort, Heap Sort, Quick Sort, Merge Sort. - Áp dụng các thuật toán sắp xếp để giải quyết các bài toán sắp xếp đơn giản. - Áp dụng các thuật toán sắp xếp để giải quyết các bài toán sắp xếp trên danh sách các cấu trúc theo từng khóa. - So sánh, đánh giá thời gian chạy của thuật toán với số lượng phần tử lớn. - Thời gian thực hành: từ 120 phút đến 400 phút TÓM TẮT Sắp xếp là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin) để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu giữ tại mỗi phần tử. - Có nhiều giải thuật sắp xếp: Selection sort, Insertion sort, Interchange sort, Bubble sort, Shaker sort, Binary Insertion sort, Shell sort, Heap sort, Quick sort, Merge sort, Radix sort… Selection sort • Chọn phần tử nhỏ nhất trong N phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu dãy hiện hành. - Xem dãy hiện hành chỉ còn N-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2. - đến khi dãy hiện hành chỉ còn 1 phần tử. - Heap sort Heap là một dãy các phần tử aleft, aleft+1. - (ai , a2i), (ai ,a2i+1): các cặp phần tử liên đới. - Heap được định nghĩa như trên được dùng trong trường hợp sắp xếp tăng dần, khi sắp xếp giảm dần phải đổi chiều các quan hệ. - Ví dụ 1: Dãy số được bố trí theo quan hệ so sánh và tạo thành cấu trúc như sau: Phần tử ở mức i chính là phần tử lớn trong cặp phần tử tương ứng ở mức i+1 Ví dụ 2: Loại bỏ 8 ra khỏi cây. - 1 Trang Tài liệu hướng dẫn thực hành môn Cấu trúc dữ liệu và giải thuật Tiến hành nhiều lần việc loại bỏ phầần tử gốc của cây cho đến khi tất cả các phần tử ử của cây đều là. - khi đó xếp các phần tử theo thứ tự ự loại bỏ trên cây sẽ có dãy đã sắp xếp. - Ngược lại, nếu các đoạnn 1 và 3 có nhiều nhi hơn 1 phần tử thì dãy con ban đầu đ chỉ có thứ tự khi các đoạn 1, 3 được sắp. - Để sắp xếp các đoạn n 1 và 3, ta lần l lượt tiến hành việc phân hoạch từng ng dãy con theo cùng phương pháp phân hoạch ch dãy ban đầu vừa trình bày … Với x là một phần tử tùy ý trong dãy và thường được chọn là vị trí chính giữa dãyy ban đầu. - Lần lượt sử dụng các thuật toán Selection Sort, Heap Sort, Quick Sort, Merge Sort để sắp xếp dãy A. - 2 - Đảo phần tử đó ra đầu mảng Trang Chương trình mẫu (CacThuatToanSapXep) Tài liệu hướng dẫn thực c hành môn Cấu trúc dữ liệu và giải thuật #include void Swap(int &a, int &b. - //chỉ số phần tử nhỏ nhất trong dãy hiện hành for (int i=0