Chương 4: Các thuật toán sắp xếp (new) Cô Võ Thị Hường

Môn học Cấu trúc dữ liệu và giải thuật GV: Võ Thị Hường LOGO THUẬT TOÁN SẮP XẾP  Khái niệm sắp xếp  Các thuật sắp xếp đơn giản  Các thuật toán sắp xếp nhanh KHÁI NIỆM SẮP XẾP  Đặt vấn đề  Cho dãy số 21 44 52 73 81 81 52 73 21 44 81 73 52 44 21  Cho danh sách tên học sinh Hùng An Thắng Bình An Hoàng Bình Hùng Hoàng Thắng KHÁI NIỆM SẮP XẾP  Khái niệm  Sắp xếp là việc biến đổi vị trí của một tập đối tượng theo một trật tự nhất định  Mục đích  Giúp việc tìm kiếm, chọn lọc thông tin được dễ dàng, nhanh chóng BÀI TOÁN SẮP XẾP BÀI TOÁN Đầu vào: Dãy n đối tượng, mỗi đối tượng có một khóa sắp xếp Đầu ra: Dãy n đối tượng được sắp xếp theo trật tự của khóa.  Giả thiết các khóa là số nguyên được lưu trong mảng một chiều, thứ tự sắp xếp là không giảm CÁC THUẬT TOÁN SẮP XẾP ĐƠN GiẢN  Thuật toán sắp xếp lựa chọn (Selection Sort)  Thuật toán sắp xếp chèn (Insertion Sort)  Thuật toán sắp xếp nổi bọt (Bubble Sort)  Thuật toán sắp xếp đổi chỗ (Interchange sort) www.themegallery.com Company Logo THUẬT TOÁN SẮP XẾP LỰA CHỌN  Ý tưởng thuật toán  Dựa vào thuật toán tìm MAX, MIN  Ở lần duyệt thứ i, với 1<=i K[Pos]; Company Logo THUẬT TOÁN SẮP XẾP LỰA CHỌN A[1] A[2] A[3] A[4] A[5] Ban đầu 3 -1 5 7 -4 Bước 1 -4 -1 5 7 3 -1 5 7 3 3 7 5 5 7 5 7 Khóa Bước Bước 2 Bước 3 Bước 4 Kết quả -4 -1 3 Cho bộ dữ liệu K = {9, 3, 10, 0, 99, 35, 25, 88, 18} Áp dụng giải thuật insertion sort với bộ dữ liệu K, chỉ rõ kết quả từng bước thực hiện của giải thuật. www.themegallery.com Company Logo Sắp xếp dãy gồm 10 mẩu tin có khóa là các số nguyên: 5, 6, 2, 2, 10, 12, 9, 10, 9 và 3 www.themegallery.com Company Logo A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] Ban đầu 5 6 2 2 10 12 9 10 9 3 Bước 1 6 5 2 10 12 9 10 9 3 2 5 6 10 12 9 10 9 3 3 6 10 12 9 10 9 5 5 10 12 9 10 9 6 6 12 9 10 9 10 9 12 10 9 10 9 10 12 10 10 12 10 10 12 10 12 2 Bước 2 Bước 3 Bước 4 Bước 5 Bước 6 Bước 7 Bước 8 Bước 9 Kết quả 2 2 3 5 6 9 9 10 www.themegallery.com Company Logo THUẬT TOÁN SẮP XẾP CHÈN  Ý tưởng thuật toán www.themegallery.com Company Logo THUẬT TOÁN SẮP XẾP CHÈN  Ý tưởng thuật toán :  Giả sử phần đầu của dãy là Bi-1 = {X1, ... , Xi-1} đã được sắp xếp tăng dần • Coi {X1} đã được sắp xếp không giảm  Kiểm tra phần tử Xi: Tìm vị trí thích hợp của Xi trong Bi-1 và chèn Xi vào vị trí để được dãy Bi = {X1 ,..., Xi-1, Xi} không giảm  Lặp lại với Xi+1 , ... cho đến khi i=n THUẬT TOÁN SẮP XẾP CHÈN  Ý tưởng thuật toán :  Ở lần duyệt thứ i, với 1<=i 0) Xj+1 = Xj; j = j – 1; Xj+1 = tg; THUẬT TOÁN SẮP XẾP CHÈN A[1] A[2] A[3] A[4] A[5] Ban đầu 3 -1 7 -4 5 Bước 1 -1 3 Bước 2 -1 3 7 Bước 3 -4 -1 3 7 Bước 4 -4 -1 3 5 7 Kết quả -4 -1 3 5 7 Khóa Bước Sắp xếp dãy gồm 10 mẩu tin đã cho ở trên có khóa là các số nguyên: 5, 6, 2, 2, 10, 12, 9, 10, 9 và 3. www.themegallery.com Company Logo Cho bộ dữ liệu K = {9, 3, 10, 0, 99, 35, 25, 88, 18} Áp dụng giải thuật insertion sort với bộ dữ liệu K, chỉ rõ kết quả từng bước thực hiện của giải thuật. www.themegallery.com Company Logo THUẬT TOÁN SẮP XẾP NỔI BỌT  Ý tưởng thuật toán :  Ở lần duyệt thứ i, với 1<=ii Bước 3 : Trong khi j ≤ N thực hiện Nếu a[j]a[j]; //xét cặp a[i], a[j] j = j+1; Bước 4 : i = i+1; Nếu i< n: Lặp lại Bước 2. Ngược lại: Dừng. www.themegallery.com Company Logo THUẬT TOÁN SẮP XẾP ĐỔI CHỖ Cài đặt thuật toán: ProcedureInterchangeSort; Var i, j: integer; Begin for i: = 1to n do for j: =i+1 to n do if (a[j]< a[i]) { nếu có sự sai vị trí thì đổi chỗ} Hoanvi(a[i],a[j]); End; www.themegallery.com Company Logo THUẬT TOÁN SẮP XẾP ĐỔI CHỖ Ví dụ minh họa Sắp xếp dãy gồm 10 mẩu tin có khóa là các số nguyên: 5, 6, 2, 2, 10, 12, 9, 10, 9 và 3 www.themegallery.com Company Logo www.themegallery.com Company Logo Cho bộ dữ liệu K = {9, 3, 10, 0, 99, 35, 25, 88, 18} Áp dụng giải thuật Quick sort với bộ dữ liệu K, chỉ rõ kết quả từng bước thực hiện của giải thuật. www.themegallery.com Company Logo Cho bộ dữ liệu K = {32, 43, 18, 80, 60, 59, 93, 70, 55} Áp dụng giải thuật quick sort với bộ dữ liệu K, chỉ rõ kết quả từng bước thực hiện của giải thuật. www.themegallery.com Company Logo