Cơ sở dữ liệu - Chương 2: Giải thuật sắp xếp (tiếp theo)

Võ Quang Hoàng Khang Email: vqhkhang@gmail.com 1 CHƯƠNG 2.(TT) GIẢI THUẬT SẮP XẾP Mục tiêu  Nắ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ều  Cài đặt được các giải thuật bằng ngôn ngữ C/C++ 2 Khái niệm  Sắp xếp là quá trình xử lý một danh sách các phần tử để đặt chúng theo một thứ tự thỏa mãn một tiêu chí 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ó i<j và ai>aj 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ị) 3 a1 a2 a3 a4 aN-2 aN-1 aN Các giải thuật sắp xếp cơ bản  Đổi chổ trực tiếp – Interchange Sort  Chọn trực tiếp – Selection Sort  Chèn trực tiếp – Insertion Sort  Nổi bọt – Bubble Sort  Quick Sort  Một số giải thuật khác - đọc thêm trong tài liệu 4 Đổ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. 5 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 6 10 5 7 3 9 2 15 1 Giả sử cần sắp xếp dãy số sau tăng dần 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 7 Bước 1: Xét phần tử đầu tiên (tại vị trí 1) i 7 3 9 2 15 1 j 10 5 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 8 Bước 1: Xét phần tử đầu tiên (tại vị trí 1) 10 i 3 9 2 15 1 j 5 7 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 9 Bước 1: Xét phần tử đầu tiên (tại vị trí 1) 10 i 7 9 2 15 1 j 5 3 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 10 Bước 1: Xét phần tử đầu tiên (tại vị trí 1) 10 i 57 2 15 1 j 3 9 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 11 Bước 1: Xét phần tử đầu tiên (tại vị trí 1) 10 i 57 9 15 1 j 3 2 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 12 Bước 1: Xét phần tử đầu tiên (tại vị trí 1) 10 i 57 3 9 1 j 2 15 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 13 Bước 1: Xét phần tử đầu tiên (tại vị trí 1) 10 i 57 3 9 j 2 15 1 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 14 Bước 1: Xét phần tử đầu tiên (tại vị trí 1) 10 i 57 3 9 2 15 1 j Kết thúc bước 1 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 15 Bước 2: Xét phần tử thứ hai (tại vị trí 2) i 5 3 9 2 15 1 j 10 7 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 16 Bước 2: Xét phần tử thứ hai (tại vị trí 2) 10 i 3 9 2 15 1 j 57 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 17 Bước 2: Xét phần tử thứ hai (tại vị trí 2) 10 i 7 3 2 15 1 j 5 9 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 18 Bước 2: Xét phần tử thứ hai (tại vị trí 2) 10 i 7 9 2 15 1 j 5 3 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 19 Bước 2: Xét phần tử thứ hai (tại vị trí 2) 10 i 57 9 21 j 3 15 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 20 Bước 2: Xét phần tử thứ hai (tại vị trí 2) 10 i 57 9 15 1 j 3 2 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 21 Bước 2: Xét phần tử thứ hai (tại vị trí 2) 10 i 57 3 9 2 15 1 j Kết thúc bước 2 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 22 Bước 3: Xét phần tử thứ ba (tại vị trí 3) i 5 3 9 2 15 1 j 10 7 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 23 10 i 5 32 15 1 j Bước 3: Xét phần tử thứ ba (tại vị trí 3) 7 9 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 24 10 i 3 9 2 15 1 j Bước 3: Xét phần tử thứ ba (tại vị trí 3) 57 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 25 10 i 7 3 9 21 j Bước 3: Xét phần tử thứ ba (tại vị trí 3) 5 15 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 26 10 i 79 2 15 1 j Bước 3: Xét phần tử thứ ba (tại vị trí 3) 5 3 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 27 10 i 573 9 2 15 1 j Bước 3: Xét phần tử thứ ba (tại vị trí 3) Kết thúc bước 3 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 28 i 5732 15 1 j Bước 4: Xét phần tử thứ tư (tại vị trí 4) 10 9 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 29 10 i 532 15 1 j Bước 4: Xét phần tử thứ tư (tại vị trí 4) 79 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 30 10 i 53 9 21 j Bước 4: Xét phần tử thứ tư (tại vị trí 4) 7 15 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 31 10 i 3 9 2 15 1 j Bước 4: Xét phần tử thứ tư (tại vị trí 4) 57 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 32 10 i 5 73 9 2 15 1 j Bước 4: Xét phần tử thứ tư (tại vị trí 4) Kết thúc bước 4 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 33 i 5 732 15 1 j Bước 5: Xét phần tử thứ năm (tại vị trí 5) 10 9 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 34 10 i 5321 j Bước 5: Xét phần tử thứ năm (tại vị trí 5) 15 79 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 35 10 i 532 15 1 j Bước 5: Xét phần tử thứ năm (tại vị trí 5) 79 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 36 10 i 5 73 9 2 15 1 j Kết thúc bước 5 Bước 5: Xét phần tử thứ năm (tại vị trí 5) 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 37 i 5 73 9 21 j Bước 6: Xét phần tử thứ sáu (tại vị trí 6) 10 15 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 38 i 5 732 15 1 j Bước 6: Xét phần tử thứ sáu (tại vị trí 6) 10 9 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 39 10 i 5 73 9 2 15 1 j Bước 6: Xét phần tử thứ sáu (tại vị trí 6) Kết thúc bước 6 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 40 i 5 73 9 21 j Bước 7: Xét phần tử thứ bảy (tại vị trí 7) 10 15 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 41 10 i 5 73 9 2 15 1 j Bước 7: Xét phần tử thứ bảy (tại vị trí 7) Kết thúc bước 7 1 2 3 4 5 6 7 8 Đổi chổ trực tiếp – interchange sort 42 10 5 73 9 2 15 1 Hoàn tất sắp xếp Giải thuật  Bướ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ực hiện Nếu a[j]<a[i]: Hoán vị 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. 43 Cài đặt void InterchangeSort(int a[], int N ) { int i, j; for (i = 0 ; i<N-1 ; i++) { for (j =i+1; j < N ; j++) if(a[j ]< a[i]) Hoanvi(a[i],a[j]); } } void Hoanvi(int &a, int &b) { int tam=a; a=b; b=tam; } 44  Ðánh giá giải thuật Số lượng các phép so sánh xảy ra không phụ thuộc vào tình trạng của dãy số ban đầu, nhưng số lượng phép hoán vị thực hiện tùy thuộc vào kết quả so sánh, có thể ước lượng trong từng trường hợp như sau: 45 Bài tập Minh họa từng bước thực hiện của giải thuật Interchange Sort khi sắp dãy số sau tăng dần: Cho biết tổng số phép hoán vị 46 15 7 9 10 6 20 Chọn trực tiếp – selection sort Ý tưởng: Chọn phần tử nhỏ nhất trong N phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu dãy hiện hành; lúc này dãy hiện hành chỉ còn N-1 phần tử cần sắp xếp, bắt đầu từ vị trí thứ 2; lặp lại quá trình trên cho dãy hiện hành... đến khi dãy hiện hành chỉ còn 1 phần tử 47 Chọn trực tiếp – selection sort 48 Làm sao để xác định được vị trí phần tử có giá trị nhỏ nhất trong một dãy gồm N phần tử? ? 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort Tìm vị trí phần tử nhỏ nhất? 49 10 5 7 3 9 2 15 1 Giả sử cần tìm vị trí phần tử nhỏ nhất trong dãy số sau ? 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort Tìm vị trí phần tử nhỏ nhất? 50 10 5 7 3 9 2 15 1 Bước 1: Giả sử vị trí phần tử nhỏ nhất là 1 (vtmin), phần tử này có giá trị 10 vtmin 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort Tìm vị trí phần tử nhỏ nhất? 51 5 7 3 9 2 15 1 Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmin 5 nhỏ hơn 10 nên cập nhật vị trí min 10 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort Tìm vị trí phần tử nhỏ nhất? 52 3 9 2 15 1 Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmin 7 lớn hơn 5 nên không cập nhật vị trí min 10 5 7 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort Tìm vị trí phần tử nhỏ nhất? 53 3 9 2 15 1 Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmin 3 nhỏ hơn 5 nên cập nhật vị trí min 10 5 7 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort Tìm vị trí phần tử nhỏ nhất? 54 3 9 2 15 1 Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmin 9 lớn hơn 3 nên không cập nhật vị trí min 10 5 7 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort Tìm vị trí phần tử nhỏ nhất? 55 9 2 15 Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmin 1 nhỏ hơn 3 nê cập nhật vị trí min 10 5 7 3 1 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort Tìm vị trí phần tử nhỏ nhất? 56 9 2 Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmin 15 lớn ơn 1 nên không cập nhật vị trí min 10 5 7 3 15 1 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort Tìm vị trí phần tử nhỏ nhất? 57 9 Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmin 10 5 7 3 15 2 lớn hơn 1 nên không cập nhật vị trí min 21 Chọn trực tiếp – selection sort Tìm vị trí phần tử nhỏ nhất? 58 Hãy cài đặt hàm tìm và trả về vị trí phần tử nhỏ nhất bằng ngôn ngữ C, đầu vào là mảng số nguyên a, kích thước n? ? Chọn trực tiếp – selection sort Tìm vị trí phần tử nhỏ nhất? 59 Giả sử cần tìm vị trí phần tử nhỏ nhất bắt đầu từ vị trí k cho trước (ví dụ đoạn từ 3 đến 8) thì giải quyết như thế nào? Hãy viết hàm cài đặt bằng ngôn ngữ C? ? 1 2 3 4 5 6 7 8 10 1 7 3 9 2 15 8 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort 60 10 5 7 3 9 2 15 1 Giả sử cần sắp xếp dãy số sau tăng dần 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort 61 5 7 3 9 2 15 Bước 1: Xét phần tử thứ nhất (vị trí 1) i • Tìm phần tử nhỏ nhất từ vị trí 1 đến 8 min • Hoán vị 2 phần tử tại vị trí đang xét với vị trí phần tử min 10 1 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort 62 7 3 9 15 Bước 2: Xét phần tử thứ hai (vị trí 2) i • Tìm phần tử nhỏ nhất từ vị trí 2 đến 8 min • Hoán vị 2 phần tử tại vị trí đang xét với vị trí phần tử min 10 1 5 2 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort 63 9 15 Bước 3: Xét phần tử thứ ba (vị trí 3) i • Tìm phần tử nhỏ nhất từ vị trí 3 đến 8 min • Hoán vị 2 phần tử tại vị trí đang xét với vị trí phần tử min 10 1 52 7 3 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort 64 9 15 Bước 4: Xét phần tử thứ tư (vị trí 4) i • Tìm phần tử nhỏ nhất từ vị trí 4 đến 8 min • Hoán vị 2 phần tử tại vị trí đang xét với vị trí phần tử min 10 1 2 3 57 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort 65 15 Bước 5: Xét phần tử thứ năm (vị trí 5) i • Tìm phần tử nhỏ nhất từ vị trí 5 đến 8 min • Hoán vị 2 phần tử tại vị trí đang xét với vị trí phần tử min 10 1 2 3 5 9 7 Bước 6: Xét phần tử thứ sáu (vị trí 6) • Tìm phần tử nhỏ nhất từ vị trí 6 đến 8 • Hoán vị 2 phần tử tại vị trí đang xét với vị trí phần tử min 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort 66 15 i min 10 1 2 3 5 7 9 Bước 7: Xét phần tử thứ bảy (vị trí 7) • Tìm phần tử nhỏ nhất từ vị trí 7 đến 8 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort 67 i min 1 2 3 5 7 9 • Hoán vị 2 phần tử tại vị trí đang xét với vị trí phần tử min 15 10 Kết thúc giải thuật - hoàn tất sắp xếp 1 2 3 4 5 6 7 8 Chọn trực tiếp – selection sort 68 1 2 3 5 7 9 15 10 Giải thuật Bước 1: i = 1; Bước 2: Tìm phần tử a[vtmin] nhỏ nhất trong dãy hiện hành từ a[i] đến a[N] Bước 3: Hoán vị a[vtmin] và a[i] Bước 4: i = i+1 Nếu i < N thì lặp lại Bước 2 Ngược lại: Dừng. 69 Cài đặt void SelectionSort(int a[],int N ) { int vtmin; for (int i=0; i<N-1 ; i++) { vtmin = i; for(int j = i+1; j <N ; j++) { if (a[j ] < a[vtmin]) vtmin=j; } Hoanvi(a[vtmin], a[i]); } } 70 Tìm vị trí min tính từ i đến N Ðánh giá giải thuật Ðối với giải thuật chọn trực tiếp, có thể thấy rằng ở lượt thứ i, bao giờ cũng cần (n-i) lần so sánh để xác định phần tử nhỏ nhất hiện hành. Số lượng phép so sánh này không phụ thuộc vào tình trạng của dãy số ban đầu, do vậy trong mọi trường hợp có thể kết luận : 71 Bài tập Minh họa từng bước thực hiện của giải thuật Selection Sort khi sắp dãy số sau tăng dần: Cho biết tổng số phép gán tìm min và tổng số phép hoán vị 72 15 7 9 10 6 20 KIỂM TRA Minh họa từng bước thực hiện khi sắp dãy số sau tăng dần: - Đổi chỗ trực tiếp. Cho biết tổng số phép hoán vị - Chọn trực tiếp. Cho biết tổng số phép gán tìm min và tổng số phép hoán vị 73 15 7 9 10 6 20 Chèn trực tiếp – insertion sort Ý tưởng Cho dãy ban đầu a1 , a2 ,... ,an, ta có thể xem như đã có đoạn gồm một phần tử a1 đã được sắp, sau đó thêm a2 vào đoạn a1 sẽ có đoạn a1 a2 được sắp; tiếp tục thêm a3 vào đoạn a1 a2 để có đoạn a1 a2 a3 được sắp; tiếp tục cho đến khi thêm xong aN vào đoạn a1 a2 ...aN-1 sẽ có dãy a1 a2 .... aN được sắp. 74 1 2 3 4 5 6 7 8 Chèn trực tiếp – insertion sort 75 10 5 7 3 9 2 15 1 Giả sử cần sắp xếp dãy số sau tăng dần 1 2 3 4 5 6 7 8 Chèn trực tiếp – insertion sort 76 10 5 7 3 9 2 15 1 Xem như phần tử thứ 1 đã có thứ tự Tìm vị trí thích hợp để chèn cho phần tử thứ 2 1 2 3 4 5 6 7 8 Chèn trực tiếp – insertion sort 77 7 3 9 2 15 1 Hai phần tử đầu tiên đã có thứ tự Tìm vị trí thích hợp để chèn cho phần tử thứ 3 10 5 1 2 3 4 5 6 7 8 Chèn trực tiếp – insertion sort 78 3 9 2 15 1 Ba phần tử đầu tiên đã có thứ tự Tìm vị trí thích hợp để chèn cho phần tử thứ 4 7 10 5 1 2 3 4 5 6 7 8 Chèn trực tiếp – insertion sort 79 9 2 15 1 Bốn phần tử đầu tiên đã có thứ tự Tìm vị trí thích hợp để chèn cho phần tử thứ 5 3 7 10 5 1 2 3 4 5 6 7 8 Chèn trực tiếp – insertion sort 80 2 15 1 Năm phần tử đầu tiên đã có thứ tự Tìm vị trí thích hợp để chèn cho phần tử thứ 6 9 3 7 10 5 1 2 3 4 5 6 7 8 Chèn trực tiếp – insertion sort 81 15 1 Sáu phần tử đầu tiên đã có thứ tự Tìm vị trí thích hợp để chèn cho phần tử thứ 7 2 9 3 7 10 5 1 2 3 4 5 6 7 8 Chèn trực tiếp – insertion sort 82 15 Bảy phần tử đầu tiên đã có thứ tự Tìm vị trí thích hợp để chèn cho phần tử thứ 8 2 9 3 7 10 5 1 1 2 3 4 5 6 7 8 Chèn trực tiếp – insertion sort 83 15 Kết thúc giải thuật 2 9 3 7 10 5 1 Chèn trực tiếp – insertion sort 84 Dựa vào đâu để xác định được vị trí chèn thích hợp của một giá trị trong dãy có giá trị tăng dần? ? Giải thuật Bước 1: i = 2; // giả sử có đoạn a[1] đã được sắp Bước 2: x = a[i]; Tìm vị trí pos thích hợp trong đoạn a[1] đến a[i-1] để chèn a[i] vào Bước 3: Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chỗ cho a[i] Bước 4: a[pos] = x; // có đoạn a[1]..a[i] đã được sắp Bước 5: i = i+1; Nếu i ≤ N : Lặp lại Bước 2. Ngược lại : Dừng. 85 void ChenTrucTiep(int a[], int N ) { int pos; int x; for(int i=1 ; i<N ; i++) //đoạn a[0] đã sắp { x = a[i]; pos = i-1; while((pos >= 0)&&(a[pos] > x)) { a[pos+1] = a[pos]; pos--; } a[pos+1] = x;// chèn x vào dãy } } 86  Đá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: 87 Bài tập Minh 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 88 15 7 9 10 6 20 Nổi bọt – bubble sort Ý tưởng: Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đúng đầu dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo. Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét. 89 12 3 4 5 6 7 8 90 7 3 9 2 15 1 10 5 i j 12 3 4 5 6 7 8 91 7 3 9 2 15 1 10 5 i j 12 3 4 5 6 7 8 92 7 3 9 2 15 1 10 5 i j 12 3 4 5 6 7 8 93 7 3 9 2 15 1 10 5 i j 12 3 4 5 6 7 8 94 7 3 9 2 15 1 10 5i j 12 3 4 5 6 7 8 95 7 3 9 2 15 1 10 5 i j 12 3 4 5 6 7 8 96 7 3 9 2 15 1 10 5 i j 12 3 4 5 6 7 8 97 7 3 9 2 15 1 10 5 i Kết thúc Giải thuật Bước 1: i = 1; Bước 2: j = N; Trong khi (j > i) thực hiện: Nếu a[j]<a[j-1]: Hoán vị a[j] và a[j-1] j = j-1; Bước 3: i = i+1; Nếu i >N-1: Hết dãy. Dừng Ngược lại: Lặp lại Bước 2. 98 Cài đặt void BubleSort(int a[], int N ) { int i, j; for (i = 0 ; i<N-1 ; i++) for (j =N-1; j >i ; j --) if(a[j]< a[j-1]) Hoanvi(a[j],a[j-1]); } 99 Đánh giá giải thuật Trong mọi trường hợp, số phép so sánh là: (n-1) + (n-2) + + 1 = n(n-1)/2 = O(n2) Số phép hoán vị:  Trường hợp xấu nhất: n(n-1)/2  Trường hợp tốt nhất: 0 100 “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ớn Dễ 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ớn 101 Quick sort  Chia dãy cần sắp thành 2 phần  Cách “chia”: ½ dãy bên trái chứa các giá trị nhỏ hơn ½ dãy bên phải  Thự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) 102 x 1 2 3 4 5 6 7 8 103Đoạn cần sắp xếp L=1 R=8 i j x i=1, j=8 L=1 R=3 L=4 R=8 Đoạn 1 Đoạn 2 L R 7 3 9 2 15 110 5 1 2 3 4 5 6 7 8 104 i j x Đoạn cần sắp xếp i=4, j=8 L=1 R=3 L=4 R=8 L=4 R=5 L=5 R=8 L R Đoạn 1 Đoạn 2 3 7 9 5 15 101 2 1 2 3 4 5 6 7 8 105Đoạn cần sắp xếp i j i=5, j=8 x L=1 R=4 L=4 R=5 L=5 R=8 L R Đoạn 2 L=6 R=8 3 5 9 7 15 101 2 1 2 3 4 5 6 7 8 106Đoạn cần sắp xếp i j i=6, j=8 x L=1 R=4 L=4 R=5 L R Đoạn 1 L=6 R=8 L=6 R=7 3 5 7 9 15 101 2 1 2 3 4 5 6 7 8 107Đoạn cần sắp xếp i j i=6, j=7 x L=1 R=4 L=4 R=5 L R L=6 R=7 3 5 7 9 10 151 2 1 2 3 4 5 6 7 8 108Đoạn cần sắp xếp i j i=4, j=5 x L=1 R=4 L=4 R=5 L R 3 5 7 9 10 151 2 1 2 3 4 5 6 7 8 109Đoạn cần sắp xếp i j i=1, j=4 x L=1 R=4 L R 3 5 7 9 10 151 2 Đoạn 2 L=3 R=4 1 2 3 4 5 6 7 8 110Đoạn cần sắp xếp i j i=3, j=4 x L=3 R=4 L R 3 5 7 9 10 151 2 1 2 3 4 5 6 7 8 111 3 5 7 9 10 151 2 Đoạn cần sắp xếp Không còn đoạn nào cần sắp xếp! Kết thúc Giải thuật Cho dãy aL, aL+1, aR Bước 1: Phân hoạch dãy aL aR thành các dãy con:  Dãy con 1: aL aj < x  Dãy con 2: aj+1 ai-1 =x  Dãy con 3: ai aR > x Bước 2:  Nếu (L<j) Phân hoạch dãy aL aj  Nếu (i<R) Phân hoạch dãy ai aR 112 Giải thuật phân hoạch dãy aL, aL+1, aR thành 2 dãy con Bước 1: Chọn tùy ý một phần tử a[k] trong dãy là giá trị mốc, L≤k≤R x=a[k], i=L, j=R Bước 2: Phát hiện và hiệu chỉnh cặp a[i] và a[j] nằm sai chỗ: Bước 2a: Trong khi (a[i]<x) i++ Bước 2b: Trong khi (a[j]>x) j-- Bước 2c: Nếu (i