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),...
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 4 - Ngô Quang ThạchCẤU TRÚC DỮ LIỆU VÀGIẢI THUẬTNGÔ QUANG THẠCHEmail: thachnq@gmail.comĐT: 01273984123Chươ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ếpPhươ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ếpPhá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ếpSắp xếp là một quá trình xử lý bố trí lại một danh sáchcá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ộctính chúng ta cần chọn một thuộc tính làm khóa và sắpxếp theo khóa này.Phương pháp chọn (Selection sort)1. Ý tưởngChọ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 đầu