Bài giảng Cấu trúc dữ liệu và Giải thuật - Chương 2.2: Giải thuật sắp xếp - Trần Minh Thái

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 so sánh, phép gán/ hoán vị của 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ữ C#2Cá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ử3Cá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ị)4a1a2a3a4aN-2aN-1aNCác khá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ớn5Cá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 Ý tưởng chính của giải thuật là 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ỗ phần tử này với phần tử tương ứng trong cặp nghịch thế. Lặp lại xử lý trên với các phần tử tiếp theo trong dãy. 712345678Đổi chổ trực tiếp – interchange sort81057392151Giả sử cần sắp xếp dãy số sau tăng dần12345678Đổi chổ trực tiếp – interchange sort9Bước 1: Xét phần tử đầu tiên (tại vị trí 1)i7392151j10512345678Đổi chổ trực tiếp – interchange sort10Bước 1: Xét phần tử đầu tiên (tại vị trí 1)10i392151j5712345678Đổi chổ trực tiếp – interchange sort11Bước 1: Xét phần tử đầu tiên (tại vị trí 1)10i792151j5312345678Đổi chổ trực tiếp – interchange sort12Bước 1: Xét phần tử đầu tiên (tại vị trí 1)10i572151j3912345678Đổi chổ trực tiếp – interchange sort13Bước 1: Xét phần tử đầu tiên (tại vị trí 1)10i579151j3212345678Đổi chổ trực tiếp – interchange sort14Bước 1: Xét phần tử đầu tiên (tại vị trí 1)10i57391j21512345678Đổi chổ trực tiếp – interchange sort15Bước 1: Xét phần tử đầu tiên (tại vị trí 1)10i5739j215112345678Đổi chổ trực tiếp – interchange sort16Bước 1: Xét phần tử đầu tiên (tại vị trí 1)10i57392151j1Kết thúc bước 112345678Đổi chổ trực tiếp – interchange sort17Bước 2: Xét phần tử thứ hai (tại vị trí 2)i5392151j110712345678Đổi chổ trực tiếp – interchange sort18Bước 2: Xét phần tử thứ hai (tại vị trí 2)10i392151j15712345678Đổi chổ trực tiếp – interchange sort19Bước 2: Xét phần tử thứ hai (tại vị trí 2)10i732151j15912345678Đổi chổ trực tiếp – interchange sort20Bước 2: Xét phần tử thứ hai (tại vị trí 2)10i792151j15312345678Đổi chổ trực tiếp – interchange sort21Bước 2: Xét phần tử thứ hai (tại vị trí 2)10i57921j131512345678Đổi chổ trực tiếp – interchange sort22Bước 2: Xét phần tử thứ hai (tại vị trí 2)10i579151j13212345678Đổi chổ trực tiếp – interchange sort23Bước 2: Xét phần tử thứ hai (tại vị trí 2)10i57392151j1Kết thúc bước 2212345678Đổi chổ trực tiếp – interchange sort24Bước 3: Xét phần tử thứ ba (tại vị trí 3)i5392151j1210712345678Đổi chổ trực tiếp – interchange sort2510i532151j12Bước 3: Xét phần tử thứ ba (tại vị trí 3)7912345678Đổi chổ trực tiếp – interchange sort2610i392151j12Bước 3: Xét phần tử thứ ba (tại vị trí 3)5712345678Đổi chổ trực tiếp – interchange sort2710i73921j12Bước 3: Xét phần tử thứ ba (tại vị trí 3)51512345678Đổi chổ trực tiếp – interchange sort2810i792151j12Bước 3: Xét phần tử thứ ba (tại vị trí 3)5312345678Đổi chổ trực tiếp – interchange sort2910i57392151j12Bước 3: Xét phần tử thứ ba (tại vị trí 3)Kết thúc bước 3312345678Đổi chổ trực tiếp – interchange sort30i5732151j12Bước 4: Xét phần tử thứ tư (tại vị trí 4)310912345678Đổi chổ trực tiếp – interchange sort3110i532151j12Bước 4: Xét phần tử thứ tư (tại vị trí 4)37912345678Đổi chổ trực tiếp – interchange sort3210i53921j12Bước 4: Xét phần tử thứ tư (tại vị trí 4)371512345678Đổi chổ trực tiếp – interchange sort3310i392151j12Bước 4: Xét phần tử thứ tư (tại vị trí 4)35712345678Đổi chổ trực tiếp – interchange sort3410i57392151j12Bước 4: Xét phần tử thứ tư (tại vị trí 4)3Kết thúc bước 4512345678Đổi chổ trực tiếp – interchange sort35i5732151j12Bước 5: Xét phần tử thứ năm (tại vị trí 5)3510912345678Đổi chổ trực tiếp – interchange sort3610i5321j1235Bước 5: Xét phần tử thứ năm (tại vị trí 5)157912345678Đổi chổ trực tiếp – interchange sort3710i532151j1235Bước 5: Xét phần tử thứ năm (tại vị trí 5)7912345678Đổ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í 5)712345678Đổi chổ trực tiếp – interchange sort39i573921j1235Bước 6: Xét phần tử thứ sáu (tại vị trí 6)7101512345678Đổi chổ trực tiếp – interchange sort40i5732151j1235Bước 6: Xét phần tử thứ sáu (tại vị trí 6)710912345678Đổi chổ trực tiếp – interchange sort4110i57392151j1235Bước 6: Xét phần tử thứ sáu (tại vị trí 6)7Kết thúc bước 6912345678Đổi chổ trực tiếp – interchange sort42i573921j1235Bước 7: Xét phần tử thứ bảy (tại vị trí 7)79101512345678Đổi chổ trực tiếp – interchange sort4310i57392151j1235Bước 7: Xét phần tử thứ bảy (tại vị trí 7)79Kết thúc bước 71012345678Đổi chổ trực tiếp – interchange sort4410573921511235Hoàn tất sắp xếp7910Giải thuậtBước 1 : i = 1;// 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 N thì trả về giá trị vt, kết thúc; Bước 3: Nếu a[i] i) thực hiện: Nếu a[j]i ; j --) { if(a[j]= 0)&&(a[pos] > x)) { a[pos+1] = a[pos]; pos--; } a[pos+1] = x;// chèn x vào dãy}}107Bài tậpMinh họa từng bước thực hiện khi áp dụng giải thuật Insertion Sort để sắp xếp dãy số sau tăng dần Cho biết tổng số phép gán và số phép so sánh của các phần tử trong dãy108157910620123456543210Mỗi lần lặp:So sánh tìm vị trí thích hợp pos Dời chỗ phần tử sang phải 1 vị trí Giải thuật thực hiện tất cả N-1 vòng lặp!!! Số lượng phép so sánh và dời chỗ này phụ thuộc vào tình trạng của dãy số ban đầu109Đánh giá giải thuật 3210Trường hợpSố phép so sánhSố phép gánTốt nhất??????Xấu nhất??????110Trường hợpSố phép so sánhSố phép gánTốt nhấtXấu nhấtĐánh giá giải thuật Kết luận“Chèn trực tiếp” và “Chọn trực tiếp” đều có chi phí cho trường hợp xấu nhất là O(n2) do đó, không thích hợp cho việc sắp xếp các mảng lớnDễ cài đặt, dễ kiểm lỗi“Chèn trực tiếp” tốt hơn “Chọn trực tiếp”, nhất là khi mảng đã có thứ tự sẵn Cần có những giải thuật hiệu quả hơn cho việc sắp xếp các mảng lớn111Cá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 SortNổi bọt – Bubble SortChèn trực tiếp – Insertion SortQuick Sort112Quick sortChia dãy cần sắp thành 2 phầnCách “chia”: ½ dãy bên trái chứa các giá trị nhỏ hơn ½ dãy bên phảiThực hiện việc sắp xếp trên từng dãy con (đệ qui)(x là phần tử trong dãy)113xVD: 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; 17114Quick sort12345678115Đoạn cần sắp xếpL=1R=8ijxi=1, j=8L=1R=3L=4R=8Đoạn 1Đoạn 2LR739215110512345678116ijxĐoạn cần sắp xếpi=4, j=8L=1R=3L=4R=8L=4R=5L=5R=8LRĐoạn 1Đoạn 2379515101212345678117Đoạn cần sắp xếpiji=5, j=8xL=1R=4L=4R=5L=5R=8LRĐoạn 2L=6R=8359715101212345678118Đoạn cần sắp xếpiji=6, j=8xL=1R=4L=4R=5LRĐoạn 1L=6R=8L=6R=7357915101212345678119Đoạn cần sắp xếpiji=6, j=7xL=1R=4L=4R=5LRL=6R=7357910151212345678120Đoạn cần sắp xếpiji=4, j=5xL=1R=4L=4R=5LR357910151212345678121Đoạn cần sắp xếpiji=1, j=4xL=1R=4LR3579101512Đoạn 2L=3R=412345678122Đoạn cần sắp xếpiji=3, j=4xL=3R=4LR3579101512123456781233579101512Đ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 ix) j--; if(i<=j) { HoanVi(a[i], a[j]); i++; j--; } } while(i<j); if(left<j) QuickSort(a, left, j); if(i<right) QuickSort(a, i, right); }126Bà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:12715791062069123012345678910Đá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)128Bài tập thuyết trìnhNghiên cứu và trình bày minh hoạ các thuật toán:Shell Sort (1-15)Heap Sort (16-30)Merge Sort (31-45)Radix Sort (46-60)Shaker Sort (61-69)129