Phân tích và thiết kế giải thuật - Chương 2: Tìm kiếm và sắp xếp

12.1. Các giải thuật tìm kiếm 2.1.1. Bài toán tìm kiếm 2.1.2. Giải thuật tìm kiếm tuyến tính 2.1.3. Giải thuật Tìm kiếm nhị phân 2.2. Các giải thuật sắp xếp 2.2.1. Bài toán sắp xếp 3.2.1 Giải thuật ñổi chổ trực tiếp –Interchange Sort 3.2.2 Giải thuật chọn trực tiếp-Selection Sort 3.2.3 Giải thuật chèn trực tiếp-Insert Sort 3.2.4 Giải thuật nổi bọt – Bubble Sort 3.2.5 Giải thuật nhanh – Quick Sort 2.3. Bài tập Chương 2 TÌM KiẾM & SẮP XẾP © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 22.1 Các Giải Thuật Tìm Kiếm © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 2.1.1. Bài toán tìm kiếm 2.1.2. Giải thuật tìm kiếm tuyến tính 2.1.3. Giải thuật Tìm kiếm nhị phân 32.1.1 Bài Toán Tìm Kiếm
Trong thực tế, khi thao tác, khai thác dữ liệu hầu như lúc nào cũng phải thực hiện thao tác tìm kiếm.
Kết quả của việc tìm kiếm có thể là không tìm thấy hoặc tìm thấy.
Nếu kết quả là tìm thấy thì nhiều khi còn phải xác ñịnh xem vị trí của phần tử tìm thấy là ở ñâu?
Việc tìm kiếm nhanh hay chậm tùy thuộc vào trạng thái và trật tự của dữ liệu trên ñó.
Có 2 thuật toán chính: Tìm kiếm tuyến tính & Tìm kiếm nhị phân © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 4
Giả sử chúng ta có một mảng M gồm N phần tử.
Vấn ñề ñặt ra là có hay không phần tử có giá trị bằng X trong mảng M?
Nếu có thì phần tử có giá trị bằng X là phần tử thứ mấy trong mảng M? © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 52.1.2. Giải Thuật Tìm Kiếm Tuyến Tính  Ý Tưởng: Tiến hành so sánh x với phần tử thứ nhất, thứ haicủa mảng A cho ñến khi gặp ñược phần tử có khóa cần tìm, hoặc ñã tìm hết mảng mà không thấy x. Ưu ñiểm: Thuật toán này có thể cho ta thực hiện tìm kiếm khi các phần tử trong mảng chưa ñược sắp xếp. Nhược ñiểm: Sẽ mất rất nhiều thời gian nếu như không có phần tử chúng ta cần tìm. © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 6VD:Tìm x = 14 12 3 5 1 14 9 0 10 2 7 14 Chưa hết mảng Tìm thấy tại vị trí thứ 5 ì t t i ị trí t 1 2 3 4 5 6 7 8 9 10 12 3 5 1 14 9 0 10 2 7 VD:Tìm x = 30 30 Chưa hết mảng Hết mảng không ìm thấy 1 2 3 4 5 6 7 8 9 10  Minh Họa © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 7 Giải thuật: Bước 1 : i = 1; // Bắt ñầu từ phần tử ñầu tiên của dãy Bước 2 : So sánh a[i] với x, có 2 khả năng. • a[i] = x ; // Tìm thấy.Dừng • a[i] != x ; // Thực hiện bước 3. Bước 3 : • i = i+1; // xét phần tử kế tiếp trong mảng. • Nếu i > N // Hết mảng.Không tìm thấy.Dừng Ngược lại: Lặp lại bước 2. © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 8 Cài ðặt Int Timtuyentinh (int a[] , int N , int x) { int i = 0; while((i < N) && (a[i] != x)) i++; if( i == N) return -1 ; // tìm hết mảng nhưng không có x else return i ; //a[i] là phần tử có khóa x. } © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM  ðánh giá giải thuật ðộ phức tập tính toán cấp n: T(n)=O(n) 92.1.3 Giải Thuật Tìm Kiếm Nhị Phân  Ý Tưởng: - Lần tìm kiếm ban ñầu là phần tử ñầu tiên của dãy (First = 1) ñến phần tử cuối cùng của dãy (Last = N). - So sánh giá trị X với giá trị phần tử ñứng ở giữa của dãy M là M[Mid]. - Nếu X = M[Mid]: Tìm thấy - Nếu X < M[Mid]: Rút ngắn phạm vi tìm kiếm về nửa ñầu của dãy M (Last = Mid–1) - Nếu X > M[Mid]: Rút ngắn phạm vi tìm kiếm về nửa sau của dãy M (First = Mid+1) - Lặp lại quá trình này cho ñến khi tìm thấy phần tử có giá trị X hoặc phạm vi tìm kiếm không còn nữa (First > Last). © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 10 Ưu ñiểm: Thuật toán tìm nhị phân sẽ rút ngắn ñáng kể thời gian tìm kiếm. Nhược ñiểm: Chỉ thực hiện ñược trên dãy ñã có thứ tự. © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 1 12 34 4623 59 69 77 11 Minh Họa 90857 L Tìm giá trị X = 85 (Tìm thấy) M X Mid = 5 M[mid]= 46 X > M[mid] © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM F 7 12 34 4623 59 69 77 12 Minh Họa 9085 Tìm giá trị X = 85 (Tìm thấy) M X Mid = 8 M[mid] = 77 X > M[mid] © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM F L 7 12 34 4623 59 69 77 13 Minh Họa 9085 Tìm giá trị X = 85 (Tìm thấy) ðã tìm thấy tại vị trí 9 M X Mid = 9 M[mid] = 85 X = M[mid] © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM LF Minh Họa Tìm kiếm phần tử có giá trị X = 5 (tìm thấy): True54False443 TrueFalseFalse43False432 TrueFalseFalse32False411 FalseTrueFalse85False101B.ñầu X> M[Mid] X< M[Mid] X= M[Mid] M[Mid]Mid First>L ast LastFirst Lần lặp © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Giả sử dãy M gồm 10 phần tử có khóa như sau (N = 10). 2 3 4 5 8 15 17 22 25 30 14  Minh Họa Tìm kiếm phần tử có giá trị X = 7 (không tìm thấy) True454 TrueFalseFalse 54False443 TrueFalseFalse43False432 TrueFalseFalse32False411 FalseTrueFalse85False101B.ñầu X> M[Mid] X< M[Mid] X= M[Mid] M[Mid]Mid First> Last LastFirst Lần lặp © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM Giả sử dãy M gồm 10 phần tử có khóa như sau (N=10). 1 3 4 5 8 15 17 22 25 30 15 16  Giải thuật: B1: First = 1 B2: Last = N B3: IF (First > Last) B3.1: Không tìm thấy B3.2: Thực hiện Bkt B4: Mid = (First + Last)/ 2 B5: IF (X = M[Mid]) B5.1: Tìm thấy tại vị trí Mid B5.2: Thực hiện Bkt B6: IF (X < M[Mid]) B6.1: Last = Mid – 1 B6.2: Lặp lại B3 B7: IF (X > M[Mid]) B7.1: First = Mid + 1 B7.2: Lặp lại B3 Bkt: Kết thúc © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 17  Cài ðặt int Timnhiphan(int M[ ], int N, int X){ int First = 1; int Last = N; while (First <= Last){ int Mid = (First + Last)/2; if (X == M[Mid]) return Mid; if (X < M[Mid]) Last = Mid – 1; else First = Mid + 1; } return -1; } © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM  ðánh giá giải thuật ðộ phức tập tính toán cấp n: T(n)=O(Log2n) 18 2.2 Các giải thuật sắp xếp © Dương Thành Phết-www.thayphet.net 2.2.1. Bài toán sắp xếp 2.2.2. Giải thuật ñổi chổ trực tiếp –Interchange Sort 2.2.3. Giải thuật chọn trực tiếp-Selection Sort 2.2.4. Giải thuật chèn trực tiếp-Insert Sort 2.2.5. Giải thuật nổi bọt – Bubble Sort 2.2.6. Giải thuật nhanh – Quick Sort Khoa CNTT Trường Cð CNTT TP.HCM 19 2.2.1. Bài Toán Sắp Xếp
ðể thuận tiện và giảm thiểu thời gian thao tác mà ñặc biệt là ñể tìm kiếm. Do vậy sắp xếp dữ liệu là một trong những thao tác cần thiết và thường gặp trong quá trình lưu trữ, quản lý dữ liệu.
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ự tăng hoặc giảm dựa trên nội dung lưu trữ trên mỗi phần tử.
Có rất nhiều thuật toán sắp xếp song chúng ta chỉ quan tâm ñến 5 giải thuật sắp xếp thường sử dụng. © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 20 © Dương Thành Phết-www.thayphet.net Khái niệm về nghịch thế: anan-1. . . . . . . . . . a3a2a1 Giả sử mảng có thứ tự tăng dần, nếu iaj thì 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ị các phần tử) Khoa CNTT Trường Cð CNTT TP.HCM 2.2.2. Giải Thuật ðổi Chổ Trực Tiếp-Interchange Sort 21 © Dương Thành Phết-www.thayphet.net  Ý 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ỗ 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. Khoa CNTT Trường Cð CNTT TP.HCM 22 © Dương Thành Phết-www.thayphet.net  Minh Họa 212 8 5 1 6 4 212 8 5 1 6 4 i=1 j=2 j=5i j=3 j=4i j=7i j=6i i i Khoa CNTT Trường Cð CNTT TP.HCM 23 © Dương Thành Phết-www.thayphet.net 212 8 5 1 6 4 121 8 5 2 6 4 21 12 8 5 6 4 21 4 12 8 6 5 21 4 5 12 8 6 21 4 5 6 12 8 21 4 5 6 8 12 Ban ñầu Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Lần 6 Khoa CNTT Trường Cð CNTT TP.HCM 24 © Dương Thành Phết-www.thayphet.net  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]: ðổi chổ a[i] và 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. Khoa CNTT Trường Cð CNTT TP.HCM 25 © Dương Thành Phết-www.thayphet.net  Cài ðặt void InterchangeSort(int a[], int N ) { int i, j,tam; for (i = 0 ; i<N-1 ; i++) for (j =i+1; j < N ; j++) if(a[j ]< a[i]) { tam=a[i]; a[i]=a[j]; a[j]=tam; } } Khoa CNTT Trường Cð CNTT TP.HCM 26 © Dương Thành Phết-www.thayphet.net  ðánh giá giải thuật:  Ðối với giải thuật ñổi chỗ trực tiếp, 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 qủa so sánh Khoa CNTT Trường Cð CNTT TP.HCM 2.2.3 Giải Thuật Chọn Trực Tiếp –Selection Sort 27 © Dương Thành Phết-www.thayphet.net  Ý Tưởng:  ðầu tiên dãy có N phần tử, ta chọn phần tử nhỏ nhất trong dãy ñổi chổ cho phần tử ñầu tiên.  Tiếp theo, tìm phần tử nhỏ nhất của dãy n-1 phần tử còn lại trong dãy ñổi chổ cho phần tử thứ 2 của dãy.  Quá trình trên thực hiên ñến khi nào trong mảng chỉ còn 1 phần tử thi dừng lại.  Kết quả ñược mảng ñã sắp xếp tăng. Khoa CNTT Trường Cð CNTT TP.HCM 28 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần I=1 Min 11 45 28 73 61 7 2316 11 45 28 73 61 7 2316 Khoa CNTT Trường Cð CNTT TP.HCM 29 © Dương Thành Phết-www.thayphet.net Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 11 45 28 73 61 16 237 I=2 Min 11 45 28 73 61 7 2316  Minh Họa Khoa CNTT Trường Cð CNTT TP.HCM 30 © Dương Thành Phết-www.thayphet.net Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 11 28 73 61 237 I=3 Min 45 16 11 45 28 73 61 7 2316  Minh Họa Khoa CNTT Trường Cð CNTT TP.HCM 31 © Dương Thành Phết-www.thayphet.net Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 11 73 617 16 45 I=4 Min 28 23 11 45 28 73 61 7 2316  Minh Họa Khoa CNTT Trường Cð CNTT TP.HCM 32 © Dương Thành Phết-www.thayphet.net Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 11 617 16 4523 Min I=5 73 28 11 45 28 73 61 7 2316  Minh Họa Khoa CNTT Trường Cð CNTT TP.HCM 33 © Dương Thành Phết-www.thayphet.net Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 117 16 23 28 73 I=6 Min 4561 11 45 28 73 61 7 2316  Minh Họa Khoa CNTT Trường Cð CNTT TP.HCM 34 © Dương Thành Phết-www.thayphet.net Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 117 16 23 28 736145 I=7 Min 11 45 28 73 61 7 2316  Minh Họa Khoa CNTT Trường Cð CNTT TP.HCM 35 © Dương Thành Phết-www.thayphet.net Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 117 16 23 28 736145 Kết thúc vì mảng chỉ còn 1 phần tử 11 45 28 73 61 7 2316  Minh Họa Khoa CNTT Trường Cð CNTT TP.HCM 36 © Dương Thành Phết-www.thayphet.net Ban ñầu Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Lần 6 11 45 28 73 61 7 2316 11 45 28 73 61 16 237 11 45 28 73 61 16 237 11 16 28 73 61 45 237 11 16 23 73 61 45 287 11 16 23 28 61 45 737 11 16 23 28 45 61 737 11 16 23 28 45 61 737Lần 7 Khoa CNTT Trường Cð CNTT TP.HCM 37 © Dương Thành Phết-www.thayphet.net  Giải thuật: Bước 1: I = 1 Bước 2: Tìm phần tử nhỏ nhất a[min] trong dãy hiện hành từ a[i] ñến a[min] Bước 3 : ðổi chổ cho a[min] 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 thì dừng. Khoa CNTT Trường Cð CNTT TP.HCM 38 © Dương Thành Phết-www.thayphet.net Cài ðặt void SelectionSort(int a[], int n) { int min, i, j, tam; for (i = 0; i < n - 1; i++) { a[min] = a[i]; for (j = i + 1; j < n; j++) if (a[j] < a[min]) a[min] =a[j]; tam=a[i]; a[i]=a[min]; a[min]=tam ; } } Khoa CNTT Trường Cð CNTT TP.HCM 39 © Dương Thành Phết-www.thayphet.net  ðá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 kết luận: Khoa CNTT Trường Cð CNTT TP.HCM 2.2.4. Giải Thuật Chèn Trực Tiếp –Insert Sort 40 © Dương Thành Phết-www.thayphet.net  Ý Tưởng:  Cho dãy ban ñầu a1, a2, , an, ta có thể xem như ñã có ñoạn gồm 1 phần tử a1 ñã ñược sắp xếp,  Sau ñó thêm a2 vào ñoạn a1 sẽ có ñoạn a1 a2 ñược sắp xếp.  Tiếp tục thêm a3 vào ñoạn a1 a2 ñể có ñoạn a1 a2 a3 ñược sắp xếp.  Tiếp tục cho ñến thêm khi xong an vào ñoạn a1 a2 an-1 sẽ có dãy a1 a2 ..an ñược sắp xếp Khoa CNTT Trường Cð CNTT TP.HCM 41 © Dương Thành Phết-www.thayphet.net Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 13 7 9 4 11 3 17 15 1 2 3 4 5 6 7 8 i=2 13 7 9 4 11 3 17 15  Minh Họa Khoa CNTT Trường Cð CNTT TP.HCM 42 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 7 4 11 3 17 15 1 2 3 4 5 6 7 8 13 9 i=3 13 7 9 4 11 3 17 15 Khoa CNTT Trường Cð CNTT TP.HCM 43 © Dương Thành Phết-www.thayphet.net Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 11 17 15 1 2 3 4 5 6 7 8 3 i=4 7 9 13 4 13 7 9 4 11 3 17 15  Minh Họa Khoa CNTT Trường Cð CNTT TP.HCM 44 © Dương Thành Phết-www.thayphet.net Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 17 15 1 2 3 4 5 6 7 8 34 7 9 13 11 i=5 13 7 9 4 11 3 17 15  Minh Họa Khoa CNTT Trường Cð CNTT TP.HCM 45 © Dương Thành Phết-www.thayphet.net Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 17 15 1 2 3 4 5 6 7 8 4 7 9 11 13 3 i=6 13 7 9 4 11 3 17 15  Minh Họa Khoa CNTT Trường Cð CNTT TP.HCM 46 © Dương Thành Phết-www.thayphet.net Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 15 1 2 3 4 5 6 7 8 3 4 7 9 11 13 i=7 17 13 7 9 4 11 3 17 15  Minh Họa Khoa CNTT Trường Cð CNTT TP.HCM 47 © Dương Thành Phết-www.thayphet.net Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 2 3 4 5 6 7 8 3 4 7 9 11 13 i=8 17 15 Kết thúc 13 7 9 4 11 3 17 15  Minh Họa Khoa CNTT Trường Cð CNTT TP.HCM 48 © Dương Thành Phết-www.thayphet.net 13 7 9 4 11 3 17 15Ban ñầu Lần 1 Lần 2 Lần 3 Lần 4 Lần 5 Lần 6 Lần 7 7 13 9 4 11 3 17 15 7 9 13 4 11 3 17 15 4 7 9 13 11 3 17 15 4 7 9 11 13 3 17 15 3 4 7 9 11 13 17 15 3 4 7 9 11 13 17 15 3 4 7 9 11 13 15 17 Khoa CNTT Trường Cð CNTT TP.HCM 49 © Dương Thành Phết-www.thayphet.net  Giải thuật: Bước 1: i=2; // a[1] ñã ñược sắp xế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ỗ phần tử a[pos] ñến a[i-1] sang phải một vị trí ñể dành chỗ cho a[i] Bước 4: a[pos]=x //ñoạn a[1] ñến 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 Khoa CNTT Trường Cð CNTT TP.HCM 50 © Dương Thành Phết-www.thayphet.net Cài ðặt void InsertSort(int a[],int n) { int pos, x; for(int i=1 ; i<n ; i++) { x=a[i]; pos=i-1; // tìm vị trí chèn x while((pos >=0 )&&(a[pos]>=x) { a[pos+1]=a[pos]; pos--; } a[pos+1]=x; //chèn x vào dãy } } Khoa CNTT Trường Cð CNTT TP.HCM 51 © Dương Thành Phết-www.thayphet.net  ðánh giá giải thuật:  Các phép so sánh xảy ra trong 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ó ước lượng trong từng trường hợp sau: Khoa CNTT Trường Cð CNTT TP.HCM 2.2.5. Giải Thuật Nổi Bọt –Bubble Sort 52 © Dương Thành Phết-www.thayphet.net  Ý 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ử ñó về vị trí ñứng ñầu dãy hiện hành  Sau ñó sẽ không xét ñến nó ở bước tiếp theo  Do vậy ở lần xử lý thứ i sẽ có vị trí dầu dãy là i phần tử ñược sắp xếp.  Lặp lại xử lý trên cho ñến khi không còn phần tử nào ñể xét. Khoa CNTT Trường Cð CNTT TP.HCM 153 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 11 5 7 3 9 2 15 2 1 3 4 5 6 7 8 i j1 11 5 7 3 9 2 15 2 1 3 4 5 6 7 8 Ban ñầu Khoa CNTT Trường Cð CNTT TP.HCM 15 54 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 11 5 7 3 9 2 2 1 3 4 5 6 7 8 i j Khoa CNTT Trường Cð CNTT TP.HCM 15 55 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 2 11 5 7 3 9 2 1 3 4 5 6 7 8 i j Khoa CNTT Trường Cð CNTT TP.HCM 15 56 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 2 3 11 5 7 9 2 1 3 4 5 6 7 8 i j Khoa CNTT Trường Cð CNTT TP.HCM 15 57 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 2 3 5 11 7 9 2 1 3 4 5 6 7 8 i j Khoa CNTT Trường Cð CNTT TP.HCM 15 58 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 2 3 5 7 11 9 2 1 3 4 5 6 7 8 i j Khoa CNTT Trường Cð CNTT TP.HCM 15 59 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 2 3 5 7 9 11 2 1 3 4 5 6 7 8 i j Kết thúc Khoa CNTT Trường Cð CNTT TP.HCM 60 © Dương Thành Phết-www.thayphet.net Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần  Minh Họa 1 11 5 7 3 9 2 15 2 1 3 4 5 6 7 8 15 1 11 5 7 3 9 2 2 1 3 4 5 6 7 8 15 1 2 11 5 7 3 9 2 1 3 4 5 6 7 8 15 1 2 3 11 5 7 9 2 1 3 4 5 6 7 8 15 1 2 3 5 11 7 9 2 1 3 4 5 6 7 8 15 1 2 3 5 7 11 9 2 1 3 4 5 6 7 8 15 1 2 3 5 7 9 11 2 1 3 4 5 6 7 8 15 1 2 3 5 7 9 11 2 1 3 4 5 6 7 8 Ban ñầu Bước 1 Bước 2 Bước 3 Bước 4 Bước 5 Bước 6 Bước 7 Khoa CNTT Trường Cð CNTT TP.HCM 61 © Dương Thành Phết-www.thayphet.net  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—; 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 Khoa CNTT Trường Cð CNTT TP.HCM 62 © Dương Thành Phết-www.thayphet.net Cài ðặt void bubblesort(t M[],int N) { for ( int i=0 ; i<N-1 ; i++) for(int j=N-1 ; j>i ; j--) if(M[j]<M[j-1]) { int tam=M[j]; M[j]=M[j-1]; M[j-1]=tam; } } Khoa CNTT Trường Cð CNTT TP.HCM 63 © Dương Thành Phết-www.thayphet.net  ðánh giá giải thuật:  Ðối với giải thuật nổi bọ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 qủa so sánh Khoa CNTT Trường Cð CNTT TP.HCM 64 © Dương Thành Phết-www.thayphet.net  Ý Tưởng:  Phân hoạch dãy M thành 2 dãy con thỏa mãn ñiều kiện: “1/2 Dãy bên trái chứa các phần tử nhỏ hơn các phần tử của 1/2 Dãy bên phải”  Nếu dãy con có nhiều hơn 1 phần tử thì thực hiện sắp xếp dãy con (ðệ qui). 2.2.6.Giải Thuật Sắp Xếp Nhanh – Quick Sort Khoa CNTT Trường Cð CNTT TP.HCM 65 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 10 5 7 3 9 2 15 1 ðoạn cần sắp xếp L=1 R=8 i=1; j=8 L RX=3 i j ðoạn 1 L=1 R=3 ðoạn 2 L=4 R=8 Khoa CNTT Trường Cð CNTT TP.HCM 66 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 2 3 7 9 5 15 10 ðoạn cần sắp xếp i=4; j=8 L RX=5 i j L=1 R=3 L=4 R=8 ðoạn 1 ðoạn 2 L=4 R=5 L=5 R=8 Khoa CNTT Trường Cð CNTT TP.HCM 67 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 2 3 5 9 7 15 10 ðoạn cần sắp xếp i=5; j=8 L RX=7 i j L=1 R=3 L=4 R=5 L=6 R=8 L=5 R=8 ðoạn 2 Khoa CNTT Trường Cð CNTT TP.HCM 68 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 2 3 5 7 9 15 10 ðoạn cần sắp xếp i=6; j=8 L RX=15 i j L=1 R=3 L=4 R=5 L=6 R=8 L=6 R=7 ðoạn 1 Khoa CNTT Trường Cð CNTT TP.HCM 69 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 2 3 5 7 9 10 15 ðoạn cần sắp xếp i=6; j=7 L R X=15 i j L=1 R=3 L=4 R=5 L=6 R=7 Khoa CNTT Trường Cð CNTT TP.HCM 70 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 2 3 5 7 9 10 15 ðoạn cần sắp xếp i=4; j=5 L R X=5 i j L=1 R=3 L=4 R=5 Khoa CNTT Trường Cð CNTT TP.HCM 71 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 2 3 5 7 9 10 15 ðoạn cần sắp xếp i=1; j=3 L RX=2 i j L=1 R=3 Khoa CNTT Trường Cð CNTT TP.HCM 72 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 2 3 5 7 9 10 15 ðoạn cần sắp xếp Không còn ñoạn nào cần sắp xếp Khoa CNTT Trường Cð CNTT TP.HCM 73 © Dương Thành Phết-www.thayphet.net  Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 2 3 5 7 9 10 15 ðoạn cần sắp xếp 10 5 7 3 7 9 10 15 Khoa CNTT Trường Cð CNTT TP.HCM 74 © Dương Thành Phết-www.thayphet.net  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—; 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 Khoa CNTT Trường Cð CNTT TP.HCM 75 © Dương Thành Phết-www.thayphet.net Cài ðặt void QuickSort(int M[], int First, int Last) { int i, j, tam, x; x = M[(First+Last)/2]; i = First; j = Last; do { while (M[i] <x) i++; while (M[j] > X) j--; if (i <= j) { tam=M[i]; M[i]=M[j]; M[j]=tam; i++; j--; } }while (i<= i); QuickSort(M, First, j); QuickSort (M, i, Last); } Khoa CNTT Trường Cð CNTT TP.HCM 76 © Dương Thành Phết-www.thayphet.net  ðánh giá giải thuật: + Trường hợp tốt nhất, khi mảng M có thứ tự tăng: Số phép gán: Gmin = N-1 Số phép so sánh: Smin = N×Log2(N)/2 Số phép hoán vị: Hmin = 0 + Trường hợp xấu nhất, khi phần tử X ñược chọn ở giữa dãy con là giá trị lớn nhất: Số phép gán: Gmax = N×(N-1)/2 Số phép so sánh: Smax = (N-1)×(N-1) Số phép hoán vị: Hmax = N×(N-1)/2 + Trung bình: Số phép gán: Gavg = (N-1)×(N+2)/4 Số phép so sánh: Savg = N×[Log2(N)+2N–2]/4 Số phép hoán vị: Havg = N×(N-1)/4 Khoa CNTT Trường Cð CNTT TP.HCM 77 © Dương Thành Phết-www.thayphet.net
Chi phí trung bình O(n*log2n)
Chi phí cho trường hợp xấu nhất O(n2)
Chi phí này phụ 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) Khoa CNTT Trường Cð CNTT TP.HCM 78 1. Trình bày tư tưởng và minh họa giải thuật tìm kiếm tuyến tính, tìm kiếm nhị phân 2. Cài ñặt thuật toán tìm tuyến tính bằng cách: - Sử dụng vòng lặp for - Sử dụng vòng lặp while 3. Trong trường hợp các phần tử của dãy ñã có thứ tự tăng (hoặc giảm) hãy cài ñặt lại thuật toán tìm nhị phân 2.3 Bài Tập © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM 79 1. Trình bày tư tưởng và minh họa 5 giải thuật sắp xếp 2. Cài ñặt 5 giải thuật sắp xếp theo các trường hợp và ñiền kết quả số lần thực hiện các phép toán vào bảng sau: © Dương Thành Phết-www.thayphet.net Khoa CNTT Trường Cð CNTT TP.HCM