Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 2: Giải thuật sắp xếp

Trần Minh TháiEmail: minhthai@huflit.edu.vnWebsite: www.minhthai.edu.vn 1Chương 2.2. Giải thuật sắp xếpMục tiêuNắm vững, minh họa và tính toán được các phép gán (hoán vị) các giải thuật sắp xếp cơ bản trên mảng một chiềuCài đặt được các giải thuật bằng ngôn ngữ C2Các khái niệmĐể truy xuất thông tin nhanh chóng và chính xác  thông tin phải được sắp xếp theo một trật tự hợp lý nào đóMột số CTDL đã định nghĩa trước trật tự của các phần tử, khi đó mỗi phần tử khi thêm vào phải đảm bảo trật tự nàySắp xếp là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin) để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu giữ tại mỗi phần tử3Khái niệmTương tự như các giải thuật tìm kiếm, khối lượng công việc phải thực hiện có liên quan chặt chẽ với số lần so sánh các khóaNgoài ra, các giải thuật sắp xếp còn phải di chuyển các phần tử Chiếm nhiều thời gian khi các phần tử có kích thước lớn4Các khái niệmKhái niệm nghịch thế Giả sử xét mảng có thứ tự tăng dần, nếu có iaj thì ta gọi đó là nghịch thế. Mục tiêu của sắp xếp là khử các nghịch thế (bằng cách hoán vị)5a0a1a2a3an-3an-2An-1Các giải thuật sắp xếp cơ bảnĐổi chỗ trực tiếp – Interchange SortChọn trực tiếp – Selection SortChèn trực tiếp – Insertion SortNổi bọt – Bubble SortQuick SortMột số giải thuật khác đọc thêm trong tài liệu6Đổi chỗ trực tiếp – interchange sortÝ tưởng Xuất phát từ đầu dãy, tìm tất cả nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ (hoán vị)Lặp lại xử lý trên với các phần tử tiếp theo trong dãy. 701234567Đổi chỗ trực tiếp – interchange sort81057392151Giả sử cần sắp xếp dãy số sau tăng dần01234567Đổi chỗ trực tiếp – interchange sort9Bước 1: Xét phần tử đầu tiên (tại vị trí 0)i7392151j10501234567Đổi chỗ trực tiếp – interchange sort10Bước 1: Xét phần tử đầu tiên (tại vị trí 0)10i392151j5701234567Đổi chỗ trực tiếp – interchange sort11Bước 1: Xét phần tử đầu tiên (tại vị trí 0)10i792151j5301234567Đổi chỗ trực tiếp – interchange sort12Bước 1: Xét phần tử đầu tiên (tại vị trí 0)10i572151j3901234567Đổi chỗ trực tiếp – interchange sort13Bước 1: Xét phần tử đầu tiên (tại vị trí 0)10i579151j3201234567Đổi chỗ trực tiếp – interchange sort14Bước 1: Xét phần tử đầu tiên (tại vị trí 0)10i57391j21501234567Đổi chỗ trực tiếp – interchange sort15Bước 1: Xét phần tử đầu tiên (tại vị trí 0)10i5739j215101234567Đổi chỗ trực tiếp – interchange sort16Bước 1: Xét phần tử đầu tiên (tại vị trí 0)10i57392151j1Kết thúc bước 101234567Đổi chỗ trực tiếp – interchange sort17Bước 2: Xét phần tử thứ hai (tại vị trí 1)i5392151j110701234567Đổi chỗ trực tiếp – interchange sort18Bước 2: Xét phần tử thứ hai (tại vị trí 1)10i392151j15701234567Đổi chỗ trực tiếp – interchange sort19Bước 2: Xét phần tử thứ hai (tại vị trí 1)10i732151j15901234567Đổi chỗ trực tiếp – interchange sort20Bước 2: Xét phần tử thứ hai (tại vị trí 1)10i792151j15301234567Đổi chỗ trực tiếp – interchange sort21Bước 2: Xét phần tử thứ hai (tại vị trí 1)10i57921j131501234567Đổi chỗ trực tiếp – interchange sort22Bước 2: Xét phần tử thứ hai (tại vị trí 1)10i579151j13201234567Đổi chỗ trực tiếp – interchange sort23Bước 2: Xét phần tử thứ hai (tại vị trí 1)10i57392151j1Kết thúc bước 2201234567Đổi chỗ trực tiếp – interchange sort24Bước 3: Xét phần tử thứ ba (tại vị trí 2)i5392151j1210701234567Đổi chỗ trực tiếp – interchange sort2510i532151j12Bước 3: Xét phần tử thứ ba (tại vị trí 2)7901234567Đổi chỗ trực tiếp – interchange sort2610i392151j12Bước 3: Xét phần tử thứ ba (tại vị trí 2)5701234567Đổi chỗ trực tiếp – interchange sort2710i73921j12Bước 3: Xét phần tử thứ ba (tại vị trí 2)51501234567Đổi chỗ trực tiếp – interchange sort2810i792151j12Bước 3: Xét phần tử thứ ba (tại vị trí 2)5301234567Đổi chỗ trực tiếp – interchange sort2910i57392151j12Bước 3: Xét phần tử thứ ba (tại vị trí 2)Kết thúc bước 3301234567Đổi chỗ trực tiếp – interchange sort30i5732151j12Bước 4: Xét phần tử thứ tư (tại vị trí 3)310901234567Đổi chỗ trực tiếp – interchange sort3110i532151j12Bước 4: Xét phần tử thứ tư (tại vị trí 3)37901234567Đổi chỗ trực tiếp – interchange sort3210i53921j12Bước 4: Xét phần tử thứ tư (tại vị trí 3)371501234567Đổi chỗ trực tiếp – interchange sort3310i392151j12Bước 4: Xét phần tử thứ tư (tại vị trí 3)35701234567Đổi chỗ trực tiếp – interchange sort3410i57392151j12Bước 4: Xét phần tử thứ tư (tại vị trí 3)3Kết thúc bước 4501234567Đổi chỗ trực tiếp – interchange sort35i5732151j12Bước 5: Xét phần tử thứ năm (tại vị trí 4)3510901234567Đổi chỗ trực tiếp – interchange sort3610i5321j1235Bước 5: Xét phần tử thứ năm (tại vị trí 4)157901234567Đổi chỗ trực tiếp – interchange sort3710i532151j1235Bước 5: Xét phần tử thứ năm (tại vị trí 4)7901234567Đổi chỗ trực tiếp – interchange sort3810i57392151j1235Kết thúc bước 5Bước 5: Xét phần tử thứ năm (tại vị trí 4)701234567Đổi chỗ trực tiếp – interchange sort39i573921j1235Bước 6: Xét phần tử thứ sáu (tại vị trí 5)7101501234567Đổi chỗ trực tiếp – interchange sort40i5732151j1235Bước 6: Xét phần tử thứ sáu (tại vị trí 5)710901234567Đổi chỗ trực tiếp – interchange sort4110i57392151j1235Bước 6: Xét phần tử thứ sáu (tại vị trí 5)7Kết thúc bước 6901234567Đổi chỗ trực tiếp – interchange sort42i573921j1235Bước 7: Xét phần tử thứ bảy (tại vị trí 6)79101501234567Đổi chỗ trực tiếp – interchange sort4310i57392151j1235Bước 7: Xét phần tử thứ bảy (tại vị trí 6)79Kết thúc bước 71001234567Đổi chỗ trực tiếp – interchange sort4410573921511235Hoàn tất sắp xếp7910Giải thuậtBước 1 : i = 0;// bắt đầu từ đầu dãy Bước 2 : j = i+1;//tìm các phần tử a[j] i Bước 3 : Trong khi j i) thực hiện: Nếu a[j]xVD: 3; 5; 8; 10; 31; 4; 81; 7; 15; 17; 1. Giả sữ x = 10 thì sẽ có 2 phần như sau:Phần nhỏ hơn x: 3; 5; 8; 4; 7; 1Phần lớn hơn x: 31; 81; 15; 17110Quick sort01234567111Đoạn cần sắp xếpL=0R=7ijxi=0, j=7L=0R=2L=3R=7Đoạn 1Đoạn 2LR739215110501234567112ijxĐoạn cần sắp xếpi=3, j=7L=0R=2L=3R=7L=3R=4L=4R=7LRĐoạn 1Đoạn 2379515101201234567113Đoạn cần sắp xếpiji=4, j=7xL=0R=3L=3R=4L=4R=7LRĐoạn 2L=5R=7359715101201234567114Đoạn cần sắp xếpiji=5, j=7xL=0R=3L=3R=4LRĐoạn 1L=5R=7L=5R=6357915101201234567115Đoạn cần sắp xếpiji=5, j=6xL=0R=3L=3R=4LRL=5R=6357910151201234567116Đoạn cần sắp xếpiji=3, j=4xL=0R=3L=3R=4LR357910151201234567117Đoạn cần sắp xếpiji=0, j=3xL=0R=3LR3579101512Đoạn 2L=2R=301234567118Đoạn cần sắp xếpiji=2, j=3xL=2R=3LR3579101512012345671193579101512Đoạn cần sắp xếpKhông còn đoạn nào cần sắp xếp!Kết thúcGiải thuậtCho dãy aL, aL+1, aRBước 1: Phân hoạch dãy aL aR thành các dãy con:Dãy con 1: aL aj xBước 2:Nếu (Lx) j-- Bước 1.2c: Nếu (i≤j): Hoán vị a[i] và a[j]; i++, j-- Bước 1.3: Nếu i<j: Lặp lại bước 1.2 Ngược lại: Dừng phân hoạch121Viết hàm sắp xếp theo phương pháp Quick Sort122Bài tậpMinh họa từng bước thực hiện của giải thuật Quick Sort khi sắp dãy số sau tăng dần:1231579106206912300123456789Đánh giá giải thuậtChi phí trung bình O(n*log2n)Chi phí cho trường hợp xấu nhất O(n2)Chi phí tùy thuộc vào cách chọn phần tử “trục”:Nếu chọn được phần tử có giá trị trung bình, ta sẽ chia thành 2 dãy bằng nhau;Nếu chọn nhằm phần tử nhỏ nhất (hay lớn nhất)  O(n2)124