Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - Th.S Thiều Quang Trung

CHƯƠNG 3<br /> CÁC THUẬT TOÁN SẮP XẾP<br /> GV Th.S. Thiều Quang Trung<br /> Bộ môn Khoa học cơ bản<br /> Trường Cao đẳng Kinh tế Đối ngoại<br /> <br /> Nội dung<br /> <br /> 1<br /> 2<br /> 3<br /> 4<br /> 5<br /> 6<br /> <br /> • Chọn trực tiếp - Selection Sort<br /> • Chèn trực tiếp - Insertion Sort<br /> <br /> • Đổi chỗ trực tiếp - Interchange Sort<br /> • Nổi bọt - Bubble Sort<br /> • Sắp xếp dựa trên phân hoạch - Quick Sort<br /> • Trộn trực tiếp - Merge Sort<br /> GV. Thiều Quang Trung<br /> <br /> 2<br /> <br /> Các khái niệm<br /> • Sắp xếp là gì ?<br /> – Sắp xếp là quá trình xử lý một danh sách các phần<br /> tử (hoặc các mẫu tin) để đặt chúng theo một thứ<br /> tự thỏa mãn một tiêu chuẩn nào đó.<br /> <br /> • Khái niệm nghịch thế:<br /> – Xét một mảng các số a0, a1, … ,aN<br /> – Giả sử xét mảng có thứ tự tăng dần, nếu có i < j và<br /> ai > aj, thì ta gọi đó là nghịch thế.<br /> <br /> GV. Thiều Quang Trung<br /> <br /> 3<br /> <br /> Các khái niệm<br /> • Để sắp xếp một mảng => tìm cách giảm số các<br /> nghịch thế trong mảng này bằng cách hoán vị<br /> các cặp phần tử.<br /> • Cho trước một dãy số a1, a2, … aN được lưu trữ<br /> trong cấu trúc dữ liệu mảng.<br /> Ví dụ: int a[N];<br /> => Chọn lựa một số phương pháp để sắp xếp.<br /> <br /> GV. Thiều Quang Trung<br /> <br /> 4<br /> <br /> Chọn trực tiếp - Selection Sort<br /> • Ý tưởng: thực hiện N-1 lần việc đưa phần tử nhỏ<br /> nhất trong dãy hiện hành về vị trí đứng ở đầu dãy<br /> • Nhận xét: nếu mảng có thứ tự thì phần tử ai luôn<br /> là min (ai,ai+1,..,an-1) => Ý tưởng của thuật toán<br /> chọn trực tiếp:<br /> – Chọn phần tử nhỏ nhất trong N phần tử ban đầu, đưa<br /> phần tử này về vị trí đứng đầu dãy hiện hành;<br /> – Sau đó không quan tâm phần tử này nữa, xem dãy hiện<br /> hành chỉ còn N-1 phần tử của dãy ban đầu, bắt đầu từ<br /> vị trí thứ 2;<br /> – Lặp lại quá trình trên cho dãy hiện hành … cho đến khi<br /> dãy hiện hành chỉ còn một phần tử.<br /> GV. Thiều Quang Trung<br /> <br /> 5<br /> <br />