tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - Ngô Quang Thạch

Nội dung chương 4 trình bày đến người học những vấn đề liên quan đến "Các phương pháp sắp xếp cơ bản", cụ thể như: Định nghĩa bài toán sắp xếp, phương pháp chọn (Selection sort), phương pháp chèn (Insertion sort), phương pháp đổi chỗ (Interchange sort), phương pháp nổi bọt (Bubble sort),. | CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NGÔ QUANG THẠCH Email: thachnq@ ĐT: 01273984123 Chương 4: Các phương pháp sắp xếp cơ bản Định nghĩa bài toán sắp xếp Phương pháp chọn (Selection sort) Phương pháp chèn (Insertion sort) Phương pháp đổi chỗ (Interchange sort) Phương pháp nổi bọt (Bubble sort) Phương pháp sắp xếp nhanh (Quick sort) Định nghĩa bài toán sắp xếp Phát biểu bài toán: - Cho tập n đối tượng (phần tử). - Hãy sắp xếp n đối tượng trên theo thứ tự tăng (giảm) Tổ chức dữ liệu - int n Số phần tử cần sắp xếp - int A[n] Lưu trữ tập hợp n phần tử Định nghĩa bài toán sắp xếp Sắp xếp là một quá trình xử lý bố trí lại một danh sách các đối tượng theo thứ tự nào đó. Ví dụ: Cần sắp xếp danh sách thí sinh theo tên với thứ tự Alphabet, hoặc sắp xếp danh sách sinh viên theo điểm trung bình với thứ tự từ cao đến thấp. Các đối tượng cần được sắp xếp thường có nhiều thuộc tính chúng ta cần chọn một thuộc tính làm khóa và sắp xếp theo khóa này. Phương pháp chọn (Selection sort) 1. Ý tưởng Chọn phần tử nhỏ nhất trong n phần tử đầu, đưa phần tử này về vị trí đầu của dãy. Tiếp tục quá trình với n-1 phần tử còn lại và bắt đầu từ vị trí thứ 2, lặp lại quá trình trên cho dãy gồm n-1 phần tử còn lại. Thuật toán thực hiện n-1 lần để lần lượt đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí dẫn .