›
›

Cơ sở dữ liệu - Chương 2: Tìm kiếm và sắp xếp

ppt 79 trang vanle 4060
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cơ sở dữ liệu - Chương 2: Tìm kiếm và sắp xếp", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptco_so_du_lieu_chuong_2_tim_kiem_va_sap_xep.ppt

Nội dung text: Cơ sở dữ liệu - Chương 2: Tìm kiếm và sắp xếp

  1. Chương 2 TÌM KIẾM & SẮP XẾP 2.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 1 2.3. Bài tập © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  2. 2.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 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  3. 2.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 3 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  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? 4 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  5. 2.1.2. Giải Thuật Tìm Kiếm Tuyến Tính v Ý Tưởng: Tiến hành so sánh x với phần tử thứ nhất, thứ hai củ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. 5 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  6. v Minh Họa Tìm thấy Chưa VD:Tìm x = 14 tại vị trí thứ hết 14 5 mảng 12 3 5 1 14 9 0 10 2 7 1 2 3 4 5 6 7 8 9 10 HếtChưa mảng VD:Tìm x = 30 khônghết tìm 30 thấymảng 12 3 5 1 14 9 0 10 2 7 1 2 3 4 5 6 7 8 9 10 6 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  7. v 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. 7 • Nếu i > N // Hết mảng.Không tìm thấy.Dừng © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương Ngược lại: Lặp lại bước 2.
  8. v CàiĐánh Đặt giá giải thuậ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. } Độ phức tập tính toán cấp n: T(n)=O(n) 8 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  9. 2.1.3 Giải Thuật Tìm Kiếm Nhị Phân v Ý 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 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). 9 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  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ự. 10 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  11. vMinh Họa Tìm giá trị X = 85 (Tìm thấy) Mid = 5 M[mid]= 46 F M L 17 12 23 34 46 5959 69 77 85 90 X X > M[mid] 11 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  12. vMinh Họa Tìm giá trị X = 85 (Tìm thấy) Mid = 8 M[mid] = 77 F M L 7 12 23 34 46 5959 69 77 85 90 X X > M[mid] 12 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  13. vMinh Họa Tìm giá trị X = 85 (Tìm thấy) Mid = 9 M[mid] = 85 M F L 7 12 23 34 46 59 69 77 85 90 Đã tìm X thấy tại vị trí 9 X = M[mid] 13 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  14. vMinh Họa 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 Tìm kiếm phần tử có giá trị X = 5 (tìm thấy): Lần First>L X= X First Last Mid M[Mid] lặp ast M[Mid] M[Mid] M[Mid] B.đầu 1 10 False 5 8 False True False 1 1 4 False 2 3 False False True 2 3 4 False 3 4 False False True 3 4 4 False 4 5 True 14 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  15. v Minh Họa 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 Tìm kiếm phần tử có giá trị X = 7 (không tìm thấy) Lần First> X= X First Last Mid M[Mid] lặp Last M[Mid] M[Mid] M[Mid] B.đầu 1 10 False 5 8 False True False 1 1 4 False 2 3 False False True 2 3 4 False 3 4 False False True 3 4 4 False 4 5 False False True 4 5 4 True 15 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  16. v 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]) B7.1: First = Mid + 1 16 B7.2: Lặp lại B3 © DươngBkt: Thành Kết Phết-www.thayphet.net thúc Khoa KTCN Trường ĐH KTKT B.Dương
  17. v CàiĐánh Đặt giá giải thuậ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; } Độ phức tập tính toán cấp n: T(n)=O(Log2n) 17 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  18. 2.2 Các giải thuật sắp xếp 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 18 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  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. 19 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  20. Khái niệm về nghịch thế: a1 a2 a3 . . . . . . . . . . an-1 an Giả sử mảng có thứ tự tăng dần, nếu i aj 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ử) 20 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  21. 2.2.2. Giải Thuật Đổi Chổ Trực Tiếp-Interchange Sort v Ý 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. 21 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  22. v Minh Họa 12 2 8 5 1 6 4 12 2 8 5 1 6 4 i=1 j=2i=2 j=3i=3 j=4i=4 j=5i=5 j=6i=6 j=7i=7 22 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  23. Ban đầu 12 2 8 5 1 6 4 Lần 1 1 12 8 5 2 6 4 Lần 2 1 2 12 8 5 6 4 Lần 3 1 2 4 12 8 6 5 Lần 4 1 2 4 5 12 8 6 Lần 5 1 2 4 5 6 12 8 Lần 6 1 2 4 5 6 8 12 23 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  24. v 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. 24 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  25. v 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; } } 25 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  26. v Đá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 26 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  27. 2.2.3 Giải Thuật Chọn Trực Tiếp –Selection Sort v Ý 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. 27 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  28. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 16 11 45 28 73 61 7 23 Min 16 11 45 28 73 61 7 23 I=1 28 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  29. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 16 11 45 28 73 61 7 23 Min 7 11 45 28 73 61 16 23 I=2 29 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  30. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 16 11 45 28 73 61 7 23 Min 7 11 45 28 73 61 16 23 I=3 30 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  31. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 16 11 45 28 73 61 7 23 Min 7 11 16 28 73 61 45 23 I=4 31 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  32. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 16 11 45 28 73 61 7 23 Min 7 11 16 23 73 61 45 28 I=5 32 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  33. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 16 11 45 28 73 61 7 23 Min 7 11 16 23 28 61 45 73 I=6 33 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  34. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 16 11 45 28 73 61 7 23 Min 7 11 16 23 28 45 61 73 I=7 34 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  35. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 16 11 45 28 73 61 7 23 Kết thúc vì mảng chỉ còn 1 phần tử 7 11 16 23 28 45 61 73 35 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  36. Ban đầu 16 11 45 28 73 61 7 23 Lần 1 7 11 45 28 73 61 16 23 Lần 2 7 11 45 28 73 61 16 23 Lần 3 7 11 16 28 73 61 45 23 Lần 4 7 11 16 23 73 61 45 28 Lần 5 7 11 16 23 28 61 45 73 Lần 6 7 11 16 23 28 45 61 73 Lần 7 7 11 16 23 28 45 61 73 36 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  37. v 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[n] 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. 37 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  38. vCà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 ; } 38 } © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  39. v Đá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: 39 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  40. 2.2.4. Giải Thuật Chèn Trực Tiếp –Insert Sort v Ý 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 40 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  41. v Minh Họa 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 13 7 9 4 11 3 17 15 1 2 3 4 5 6 7 8 i=2 41 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  42. v Minh Họa 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 7 13 9 4 11 3 17 15 1 2 3 4 5 6 7 8 i=3 42 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  43. v Minh Họa 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 7 9 13 4 11 3 17 15 1 2 3 4 5 6 7 8 i=4 43 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  44. v Minh Họa 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 4 7 9 13 11 3 17 15 1 2 3 4 5 6 7 8 i=5 44 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  45. v Minh Họa 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 4 7 9 11 13 3 17 15 1 2 3 4 5 6 7 8 i=6 45 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  46. v Minh Họa 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 3 4 7 9 11 13 17 15 1 2 3 4 5 6 7 8 i=7 46 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  47. v Minh Họa 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 Kết thúc 3 4 7 9 11 13 17 15 1 2 3 4 5 6 7 8 i=8 47 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  48. Ban đầu 13 7 9 4 11 3 17 15 Lần 1 7 13 9 4 11 3 17 15 Lần 2 7 9 13 4 11 3 17 15 Lần 3 4 7 9 13 11 3 17 15 Lần 4 4 7 9 11 13 3 17 15 Lần 5 3 4 7 9 11 13 17 15 Lần 6 3 4 7 9 11 13 17 15 Lần 7 3 4 7 9 11 13 15 17 48 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  49. v 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 49 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  50. vCài Đặt void InsertSort(int a[],int n) { int pos, x; for(int i=1 ; i =0 )&&(a[pos]>=x) { a[pos+1]=a[pos]; pos ; } a[pos+1]=x; //chèn x vào dãy } 50 } © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  51. v Đá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: 51 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  52. 2.2.5. Giải Thuật Nổi Bọt –Bubble Sort v Ý 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. 52 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  53. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần Ban đầu 11 1 i 11 1 5 2 5 2 7 3 7 3 3 4 3 4 9 5 9 5 2 6 2 6 15 7 15 7 1 8 1 8 j 53 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  54. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần i 1 1 11 2 5 3 7 4 3 5 9 6 2 7 15 8 j 54 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  55. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 1 i 2 2 11 3 5 4 7 5 3 6 9 7 15 8 j 55 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  56. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 1 2 2 i 3 3 11 4 5 5 7 6 9 7 15 8 j 56 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  57. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 1 2 2 3 3 i 5 4 11 5 7 6 9 7 15 8 j 57 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  58. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 1 2 2 3 3 5 4 i 7 5 11 6 9 7 15 8 j 58 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  59. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 1 1 2 2 3 3 5 4 7 5 i 9 6 Kết 11 7 thúc 15 8 j 59 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  60. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 2 11 2 2 2 2 2 2 2 2 2 2 2 2 2 7 3 5 3 11 3 3 3 3 3 3 3 3 3 3 3 3 4 7 4 5 4 11 4 5 4 5 4 5 4 5 4 9 5 3 5 7 5 5 5 11 5 7 5 7 5 7 5 2 6 9 6 3 6 7 6 7 6 11 6 9 6 9 6 15 7 2 7 9 7 9 7 9 7 9 7 11 7 11 7 1 8 15 8 15 8 15 8 15 8 15 8 15 8 15 8 Ban đầu Bước 1 Bước 2 Bước 3 Bước 4 Bước 5 Bước 6 Bước 7 60 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  61. v 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] N-1: Hết dãy, dừng Ngược lại: Lặp lại Bước 2 61 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  62. vCài Đặt void bubblesort(t M[],int N) { for ( int i=0 ; i i ; j ) if(M[j]<M[j-1]) { int tam=M[j]; M[j]=M[j-1]; M[j-1]=tam; } } 62 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  63. v Đá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 63 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  64. 2.2.6.Giải Thuật Sắp Xếp Nhanh – Quick Sort v Ý 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). 64 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  65. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần i=1; j=8 L X=3 R 10 5 7 3 9 2 15 1 i j L=1 R=8 Đoạn 1 Đoạn 2 Đoạn cần L=1 L=4 sắp xếp 65 R=3 R=8 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  66. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần i=4; j=8 L X=5 R 1 2 3 7 9 5 15 10 L=4 R=8 i j L=1 R=3 Đoạn 1 Đoạn 2 Đoạn cần L=4 L=5 R=5 R=8 66 sắp xếp © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  67. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần i=5; j=8 L X=7 R L=5 1 2 3 5 9 7 15 10 R=8 L=4 R=5 i j L=1 R=3 Đoạn 2 L=6 Đoạn cần R=8 67 sắp xếp © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  68. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần i=6; j=8 L X=15 R L=6 1 2 3 5 7 9 15 10 R=8 L=4 R=5 i j L=1 R=3 Đoạn 1 L=6 Đoạn cần R=7 68 sắp xếp © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  69. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần i=6; j=7 X=15 L R L=6 1 2 3 5 7 9 10 15 R=7 L=4 R=5 i j L=1 R=3 Đoạn cần 69 sắp xếp © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  70. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần i=4; j=5 X=5 L R 1 2 3 5 7 9 10 15 L=4 R=5 i j L=1 R=3 Đoạn cần 70 sắp xếp © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  71. v Minh Họa Cho dãy có 8 phần tử Sắp xếp theo vi trí tăng dần i=1; j=3 L X=2 R 1 2 3 5 7 9 10 15 i j L=1 R=3 Đoạn cần 71 sắp xếp © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  72. v 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 Không còn đoạn nào cần sắp xếp Đoạn cần 72 sắp xếp © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  73. Đoạn [1- 8] 10 5 7 3 9 2 15 1 Đoạn [4- 8] 7 9 5 15 10 Đoạn [5- 8] 9 7 15 10 Đoạn [6- 8] 9 10 15 Đoạn [6- 7] 9 10 Đoạn [4- 5] 5 7 Đoạn [1- 3] 1 2 3 73 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  74. v 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] N-1: Hết dãy, dừng Ngược lại: Lặp lại Bước 2 74 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  75. vCà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) 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); 75 } © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  76. v Đá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 76 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  77. ü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) 77 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  78. 2.3 Bài Tập 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 78 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương
  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: 79 © Dương Thành Phết-www.thayphet.net Khoa KTCN Trường ĐH KTKT B.Dương