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@itc.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ữ C/C++2Các khái niệmSắ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ử.Khá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ị)3a1a2a3a4aN-2aN-1aNCá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ệu4Đổ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. 512345678Đổi chổ trực tiếp – interchange sort61057392151Giả sử cần sắp xếp dãy số sau tăng dần12345678Đổi chổ trực tiếp – interchange sort7Bước 1: Xét phần tử đầu tiên (tại vị trí 1)i7392151j10512345678Đổi chổ trực tiếp – interchange sort8Bước 1: Xét phần tử đầu tiên (tại vị trí 1)10i392151j5712345678Đổi chổ trực tiếp – interchange sort9Bước 1: Xét phần tử đầu tiên (tại vị trí 1)10i792151j5312345678Đổi chổ trực tiếp – interchange sort10Bước 1: Xét phần tử đầu tiên (tại vị trí 1)10i572151j3912345678Đổi chổ trực tiếp – interchange sort11Bước 1: Xét phần tử đầu tiên (tại vị trí 1)10i579151j3212345678Đổi chổ trực tiếp – interchange sort12Bước 1: Xét phần tử đầu tiên (tại vị trí 1)10i57391j21512345678Đổi chổ trực tiếp – interchange sort13Bước 1: Xét phần tử đầu tiên (tại vị trí 1)10i5739j215112345678Đổi chổ trực tiếp – interchange sort14Bướ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 sort15Bước 2: Xét phần tử thứ hai (tại vị trí 2)i5392151j110712345678Đổi chổ trực tiếp – interchange sort16Bước 2: Xét phần tử thứ hai (tại vị trí 2)10i392151j15712345678Đổi chổ trực tiếp – interchange sort17Bước 2: Xét phần tử thứ hai (tại vị trí 2)10i732151j15912345678Đổi chổ trực tiếp – interchange sort18Bước 2: Xét phần tử thứ hai (tại vị trí 2)10i792151j15312345678Đổi chổ trực tiếp – interchange sort19Bước 2: Xét phần tử thứ hai (tại vị trí 2)10i57921j131512345678Đổi chổ trực tiếp – interchange sort20Bước 2: Xét phần tử thứ hai (tại vị trí 2)10i579151j13212345678Đổi chổ trực tiếp – interchange sort21Bướ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 sort22Bước 3: Xét phần tử thứ ba (tại vị trí 3)i5392151j1210712345678Đổi chổ trực tiếp – interchange sort2310i532151j12Bước 3: Xét phần tử thứ ba (tại vị trí 3)7912345678Đổi chổ trực tiếp – interchange sort2410i392151j12Bước 3: Xét phần tử thứ ba (tại vị trí 3)5712345678Đổi chổ trực tiếp – interchange sort2510i73921j12Bước 3: Xét phần tử thứ ba (tại vị trí 3)51512345678Đổi chổ trực tiếp – interchange sort2610i792151j12Bước 3: Xét phần tử thứ ba (tại vị trí 3)5312345678Đổi chổ trực tiếp – interchange sort2710i57392151j12Bướ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 sort28i5732151j12Bước 4: Xét phần tử thứ tư (tại vị trí 4)310912345678Đổi chổ trực tiếp – interchange sort2910i532151j12Bước 4: Xét phần tử thứ tư (tại vị trí 4)37912345678Đổi chổ trực tiếp – interchange sort3010i53921j12Bước 4: Xét phần tử thứ tư (tại vị trí 4)371512345678Đổi chổ trực tiếp – interchange sort3110i392151j12Bước 4: Xét phần tử thứ tư (tại vị trí 4)35712345678Đổi chổ trực tiếp – interchange sort3210i57392151j12Bướ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 sort33i5732151j12Bước 5: Xét phần tử thứ năm (tại vị trí 5)3510912345678Đổi chổ trực tiếp – interchange sort3410i5321j1235Bước 5: Xét phần tử thứ năm (tại vị trí 5)157912345678Đổi chổ trực tiếp – interchange sort3510i532151j1235Bước 5: Xét phần tử thứ năm (tại vị trí 5)7912345678Đổi chổ trực tiếp – interchange sort3610i57392151j1235Kế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 sort37i573921j1235Bước 6: Xét phần tử thứ sáu (tại vị trí 6)7101512345678Đổi chổ trực tiếp – interchange sort38i5732151j1235Bước 6: Xét phần tử thứ sáu (tại vị trí 6)710912345678Đổi chổ trực tiếp – interchange sort3910i57392151j1235Bướ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 sort40i573921j1235Bước 7: Xét phần tử thứ bảy (tại vị trí 7)79101512345678Đổi chổ trực tiếp – interchange sort4110i57392151j1235Bướ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 sort4210573921511235Hoà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 i) thực hiện: Nếu a[j]N-1: Hết dãy. Dừng Ngược lại: Lặp lại Bước 2. 83Cài đặtvoid BubleSort(int a[], int N ){ int i, j;for (i = 0 ; ii ; 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}}99Bài tậpMinh họa từng bước thực hiện của giải thuật Insertion Sort khi sắp dãy số sau tăng dần:Cho biết tổng số gán và số phép so sánh100157910620123456Đánh giá giải thuật Các phép so sánh xảy ra trong mỗi vòng lặp while tìm vị trí thích hợp pos, và mỗi lần xác định vị trí đang xét không thích hợp, sẽ dời chỗ phần tử a[pos] tương ứng. Giải thuật thực hiện tất cả N-1 vòng lặp while, do 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 đầu, nên chỉ có thể ước lượng trong từng trường hợp như sau: 101Kế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ớn102Cá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 Sort103Quick 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)104xVD: 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; 17105Quick sort12345678106Đoạn cần sắp xếpL=1R=8ijxi=1, j=8L=1R=3L=4R=8Đoạn 1Đoạn 2LR739215110512345678107ijxĐoạn cần sắp xếpi=4, j=8L=1R=3L=4R=8L=4R=5L=5R=8LRĐoạn 1Đoạn 2379515101212345678108Đoạn cần sắp xếpiji=5, j=8xL=1R=4L=4R=5L=5R=8LRĐoạn 2L=6R=8359715101212345678109Đoạn cần sắp xếpiji=6, j=8xL=1R=4L=4R=5LRĐoạn 1L=6R=8L=6R=7357915101212345678110Đoạn cần sắp xếpiji=6, j=7xL=1R=4L=4R=5LRL=6R=7357910151212345678111Đoạn cần sắp xếpiji=4, j=5xL=1R=4L=4R=5LR357910151212345678112Đoạn cần sắp xếpiji=1, j=4xL=1R=4LR3579101512Đoạn 2L=3R=412345678113Đoạn cần sắp xếpiji=3, j=4xL=3R=4LR3579101512123456781143579101512Đ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); }117Bà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:11815791062069123012345678910Đá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)119