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

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