›
›

Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 8: Sắp xếp (Sorting) - Nguyễn Thị Xuân Hương

pdf 31 trang huongle 2451
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 8: Sắp xếp (Sorting) - Nguyễn Thị Xuân Hương", để 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:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_8_sap_xep_so.pdf

Nội dung text: Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 8: Sắp xếp (Sorting) - Nguyễn Thị Xuân Hương

  1. Chương 8: SẮP XẾP (Sorting) 8.1. Bài toán sắp xếp Input: Cho một tập n đối tuợng, mỗi đối tượng có m thuộc tính Output: n đối tượng được sắp xếp theo chiều tăng dần (hoặc giảm dần) theo giá trị của khóa cần xếp VD: Sắp xếp danh sách sau theo thứ tự tăng dần của điểm thi STT SBD Họ và tên Điểm thi 1 ĐA100 Nguyễn Văn A 7 2 ĐA105 Trần Thị B 8 3 ĐA108 Hoàng Văn H 6 4 ĐA103 Đỗ Thị C 9 5 ĐA200 Nguyễn Văn Đ 10 •Để đơn giản ta qui về bài toán: •Input: Cho dãy n giá trị khóa (là các số nguyên) •Output: Dãy được xếp theo giá trị tăng dần hoặc giảm dần 1
  2. Chương 8: SẮP XẾP (Sorting) 8.2. Một số giải thuật sắp xếp đơn giản: 8.2.1. Sắp xếp bằng chọn trực tiếp (Selection Sort)) Tư tưởng: Để thực hiện sắp xếp, ta coi như có hai dãy: - Dãy đã xếp chưa có phần tử nào - Dãy chưa xếp có n phần tử (dãy ban đầu) -> Chọn phần tử nhỏ nhất ở dãy chưa xếp đưa vào dãy đã xếp => sau mỗi lượt chọn dãy đã xếp tăng lên 1 phần tử, dãy chưa xếp giảm 1 phần tử. -Nếu chỉ sử dụng một dãy ban đầu để xếp: ta đổi giá trị của phần tử nhỏ nhất với phần tử đầu tiên ở dãy chưa xếp. -Thực hiện chọn n-1 lần và đổi giá trị thì xếp xong 2
  3. Chương 8: SẮP XẾP (Sorting) 8.2. Một số giải thuật sắp xếp đơn giản: 8.2.1. Sắp xếp bằng chọn trực tiếp (Selection Sort)) Tư tưởng: Để thực hiện sắp xếp, ta coi như có hai dãy: - Dãy đã xếp chưa có phần tử nào - Dãy chưa xếp có n phần tử (dãy ban đầu) -> Chọn phần tử nhỏ nhất ở dãy chưa xếp đưa vào dãy đã xếp => sau mỗi lượt chọn dãy đã xếp tăng lên 1 phần tử, dãy chưa xếp giảm 1 phần tử. -Nếu chỉ sử dụng một dãy ban đầu để xếp: ta đổi giá trị của phần tử nhỏ nhất với phần tử đầu tiên ở dãy chưa xếp. -Thực hiện chọn n-1 lần và đổi giá trị thì xếp xong 3
  4. Chương 8: SẮP XẾP (Sorting) 8.2.1. Sắp xếp bằng chọn trực tiếp (Selection Sort)) * VD: Dãy: 5 7 1 6 9 2 8 4 Lượt 1: Chọn số 1 ở vị trí 2 - nhỏ nhất trong dãy chưa xếp -> đổi giá trị của phần tử đầu tiên (5) của dãy chưa xếp với số được chọn ở vị trí 2 là 1 1 7 5 6 9 2 8 4 => Dãy đã xếp chứa 1 phần tử là 1 (vị trí a0); dãy chưa xếp còn 7 phần tử (từ a1 đến an-1 ) Lượt 2: Chọn số 2 ở vị trí 5 - nhỏ nhất trong dãy chưa xếp -> đổi số ở vị trí 1 là 7 cho số ở vị trí 5 là 2 1 2 5 6 9 7 8 4 Thực hiện n-1 lần. Dãy đã xếp: 1 2 4 5 6 7 8 9 4
  5. Chương 8: SẮP XẾP (Sorting) 8.2.1. Sắp xếp bằng chọn trực tiếp (Selection Sort)) * VD: Dãy: 5 7 1 6 9 2 8 4 Lượt 1: Chọn số 1 ở vị trí 2 - nhỏ nhất trong dãy chưa xếp -> đổi giá trị của phần tử đầu tiên (5) của dãy chưa xếp với số được chọn ở vị trí 2 là 1 1 7 5 6 9 2 8 4 => Dãy đã xếp chứa 1 phần tử là 1 (vị trí a0); dãy chưa xếp còn 7 phần tử (từ a1 đến an-1 ) Lượt 2: Chọn số 2 ở vị trí 5 - nhỏ nhất trong dãy chưa xếp -> đổi số ở vị trí 1 là 7 cho số ở vị trí 5 là 2 1 2 5 6 9 7 8 4 Thực hiện n-1 lần. Dãy đã xếp: 1 2 4 5 6 7 8 9 5
  6. Chương 8: SẮP XẾP (Sorting) 8.2.1. Sắp xếp bằng chọn trực tiếp (Selection Sort)) Thảo luận: -Viết thủ tục và đánh giá độ phức tạp giải thuật, cho dãy số và minh họa các bước thực hiện theo giải thuật. - Khi dùng hai dãy riêng biệt: dãy đã xếp và dãy chưa xếp thì giải thuật thực hiện trên đó có gì khác nhau? 6
  7. Chương 8: SẮP XẾP (Sorting) 8.2.2. Sắp xếp bằng chèn trực tiếp (Inserttion Sort) Tư tưởng giải thuật: Chia dãy ban đầu thành hai dãy con: - Dãy đã xếp có 1 phần tử (là phần tử đầu tiên) - Dãy chưa xếp còn n-1 phần tử Lấy lần lượt từng phần tử ở dãy chưa xếp chèn vào vị trí thích hợp trên dãy đã xếp sao cho vẫn đảm bảo thứ tự. Mỗi lần như vậy, dãy đã xếp tăng lên 1 phần tử, dãy chưa xếp giảm đi 1 phần tử. 7
  8. Chương 8: SẮP XẾP (Sorting) 8.2.2. Sắp xếp bằng chèn trực tiếp (Inserttion Sort) VD: Dãy: 5 7 1 6 9 2 8 4 Chia dãy thành hai dãy con 5| 7 1 6 9 2 8 4 Lượt 1: chèn 7 vào dãy đã xếp 5 7| 1 6 9 2 8 4 Lượt 2: chèn 1 vào dãy đã xếp 1 5 7| 6 9 2 8 4 Thực hiện n-1 lần Dãy đã xếp : 1 2 4 5 6 7 8 9 8
  9. Chương 8: SẮP XẾP (Sorting) 8.2.2. Sắp xếp bằng chèn trực tiếp (Inserttion Sort) Lượt 2: chèn 1 vào dãy đã xếp 5 7| 1 6 9 2 8 4 Key = a[2]; j = 1; Vì key lùi a[j+1] = a[j] => a[2] = a[1] 5 - 7 6 9 2 8 4 J ; -> j =0 Vì key a[j+1] = a[j]=> a[1] =a[0] - 5 7 6 9 2 8 4 J ; => j =-1 A[j+1] =key => a[0] =1 1 5 7 6 9 2 8 4 9
  10. Chương 8: SẮP XẾP (Sorting) 8.2.2. Sắp xếp bằng chèn trực tiếp (Inserttion Sort) Thảo luận: - Trình bày từng bước thực hiện giải thuật theo ý tưởng trên - Viết thủ tục và đánh giá độ phức tạp giải thuật, cho ví dụ và minh họa các bước thực hiện theo giải thuật. 10
  11. Chương 8: SẮP XẾP (Sorting) 8.2.1. Sắp xếp nổi bọt (Bubble Sort) Tư tưởng giải thuật: quét từ cuối dãy về đầu dãy, nếu trên đường đi mà gặp hai phần tử liên tiếp có giá trị ngược với thứ tự sắp xếp thì đổi giá trị của chúng. (phương pháp đổi chỗ liên tiếp) 11
  12. Chương 8: SẮP XẾP (Sorting) 8.2.1. Sắp xếp nổi bọt (Bubble Sort) VD: Dãy: 5 7 1 6 9 2 8 4 Lượt 1: 1 5 7 2 6 9 4 8 Lượt 2: 1 2 5 7 4 6 9 8 Lượt 3: 1 2 4 5 7 6 8 9 . Thực hiện n-1 lần Dãy đã xếp: 1 2 4 5 6 7 8 9 12
  13. Chương 8: SẮP XẾP (Sorting) 8.2.1. Sắp xếp nổi bọt (Bubble Sort) Thảo luận: -Viết thủ tục và đánh giá độ phức tạp giải thuật, cho dãy số và minh họa các bước thực hiện theo giải thuật. - Các phương pháp sắp xếp trên có ưu, nhược điểm gì? Khi nào sử dụng các phương pháp đó? 13
  14. Chương 8: SẮP XẾP (Sorting) 8.3. Một số giải thuật sắp xếp công nghiệp: 8.3. 1.Sắp xếp nhanh (Quick Sort) Tư tưởng giải thuật: Chọn một phần tử chốt là t, chia dãy ban đầu thành 3 dãy con Dãy S1 = { x | x t } Nhận xét: Dãy S2 đã được xếp, tiếp tục thực hiện sắp xếp Quick Sort với dãy S1, và S3 - Chọn chốt: + Phần tử trái cùng x[l] (l: left tính từ chỉ số 0) + Phần tử phải cùng x[r] (r: right tính từ chỉ số n-1) + Phần tử giữa: x[l+r]/2 14
  15. Chương 8: SẮP XẾP (Sorting) 8.3. 1.Sắp xếp nhanh (Quick Sort) -i = l; j = r -Chia dãy: Lặp quá trình sau: + Tiến từ trái sang phải trong khi các phần tử x[i] còn nhỏ hơn chốt (dừng khi x[i] >= chốt) + Tiến từ phải sang trái trong khi các phần tử x[j] còn lớn hơn chốt (dừng khi x[j] j -> đã chia dãy xong. Dãy S1: l-> j, dãy S2: j+1 -> i-1 ; Dãy S3: i -> r 15
  16. Chương 8: SẮP XẾP (Sorting) VD: Dãy số: 5l 9 1 7 6 2 8 4r Luợt 1: Chọn chốt là t= x[0+8]/2 = 6 ; i = l ; j = r ; Ta chia dãy như sau: Quét : 5 9i 1 7 6 2 8 4j Đổi giá trị x[i] và x[j] 5 4 1i 7 6 2 8j 9 Quét : 5 4 1 7i 6 2j 8 9 Đổi giá trị x[i] và x[j] 5 4 1 2 6i,j 7 8 9 Quét: 5 4 1 2 6j 7i 8 9 i>j-> dừng [5 4 1 2 6j] [7i 8 9] l =0 < j =4 ; i = 5 < r = 7 Tiếp tục QuickSort(x[], l,j), QuickSort(x[],i,r) 16
  17. Chương 8: SẮP XẾP (Sorting) 8.3. 1.Sắp xếp nhanh (Quick Sort) Thảo luận: - Phương pháp sắp xếp trên dựa trên chiến lược thiết kế giải thuật nào? Vì sao? - Lựa chọn cách biểu diễn dữ liệu như thế nào cho bài toán? - Viết thủ tục và đánh giá độ phức tạp giải thuật, cho dãy số và minh họa các bước thực hiện theo giải thuật. 17
  18. Chương 8: SẮP XẾP (Sorting) 8.3. 2.Sắp xếp bằng vung đống – HeapSort Định nghĩa: Heap là cây nhị phân hoàn chỉnh, trong đó giá trị khóa ở nút gốc luôn lớn hơn khóa ở hai nút con. Cây con trái và cây con phải cũng là heap. Tư tưởng sắp xếp bằng Heap:  Vun heap: vun dãy ban đầu chứa các khóa tạo thành Heap Sắp xếp: Chặt gốc (Heap) để lấy ra phần tử lớn nhất trên cây (mỗi lần chặt khóa lớn nhất được lấy ra và heap giảm đi 1 phần tử - chọn nút cuối cùng thay thế cho nút gốc -> vi phạm tính chất Heap nên phải vun lại Heap). Chặt n-1 lần 18
  19. Chương 8: SẮP XẾP (Sorting) 8.3. 2.Sắp xếp bằng vung đống – HeapSort Giải thuật vun Heap: - Mỗi nút lá là một Heap, vun các nút cha với hai con đã là heap - > Vun các nút trong i từ n/2 đến 1 là các nút cha với hai con đã là Heap 19
  20. Chương 8: SẮP XẾP (Sorting) vun Heap: tại nút i Thực hiện: 1.Nút cha cần vun là key = x[i]; 2.Con trái j = 2*i //là x[j]), con phải 2*i+1 ( là x[j+1]) 3.Trong khi j vẫn thuộc cây ( j x[j] -> key thỏa mãn t/c heap Đặt X[j/2] = key, K.thúc +Nếu key thì tuyển nút con x[j] lên trên (x[j/2] = x[j]). +Tiếp tục đi xuống xét các con của j để tìm vị trí thích hợp cho khóa key (Tăng j = 2*j 4. Đặt X[j/2] = key; 20
  21. Chương 8: SẮP XẾP (Sorting) VD: cho dãy khóa sau: 1 3 7 6 9 2 8 4 5 Vun heap : vun các nút cha từ n/2 đến 1 Từ 4 -> 1 Vun gốc i= 4 Vun gốc i = 3 21
  22. Chương 8: SẮP XẾP (Sorting) Vun heap : Vun gốc i= 2 Vun gốc i= 1 22
  23. Chương 8: SẮP XẾP (Sorting) vun Heap: tại nút I =1 19 Key = 1 j = 2 -> con lớn j = 2 69 8 Vì Key tuyển x[1]= x[2]=9 j = 2*j = 4 -> con lớn j=4 56 3 2 7 Vì key tuyển x[2]=x[4] =6 4 51  j = 2*j = 8 -> con lớn j =9 Vì key tuyển x[4] = x[9]=5 j = 2*j = 18 (không thuộc cây) -> đặt x[j/2] = key, kết thúc. 23
  24. Chương 8: SẮP XẾP (Sorting) Sắp xếp : Chặt gốc key = 9 Vun heap tại gốc i =1 24
  25. Chương 8: SẮP XẾP (Sorting) Sắp xếp : Chặt gốc key = 8 Vun heap tại gốc i =1 Tiếp tục chặt n-1 lần ta được dãy : 1 2 3 4 5 6 7 8 9 25
  26. Chương 8: SẮP XẾP (Sorting) 8.3. 2.Sắp xếp bằng vung đống – HeapSort Heap được coi là Hàng đợi có ưu tiên – vì khóa ở gốc luôn lớn nhất. Các phép toán với CTDL Heap: Khởi tạo, chèn 1 phần tử, lấy một phần tử ra khỏi Heap. Thảo luận: Biểu diễn và cài đặt CTDL Heap như thế nào trên máy tính? Khi nào cần sử dụng cấu trúc Heap? 26
  27. Chương 8: SẮP XẾP (Sorting) 8.3. 3.Sắp xếp bằng trộn (Merge Sort) Tư tưởng giải thuât : Nếu có hai dãy đã xếp -> trộn thành 1 dãy được xếp Dãy có 1 phần tử là dãy đã được xếp VD : Dãy A (đã xếp) gồm : 1 5 8 9 10 Dãy B (đã xếp) gồm : 2 4 6 7 Trộn hai dãy A,B được dãy C : 1 2 4 5 6 7 8 9 10 27
  28. Chương 8: SẮP XẾP (Sorting) 8.3. 3.Sắp xếp bằng trộn (Merge Sort) Giải thuât sắp xếp bằng trộn: Chia dãy : - Nếu dãy cần xếp còn lớn hơn 1 phần tử , ta chia đôi dãy ban đầu thành hai dãy con tại vị trí k= (l+r)/2 - Tiếp tục sử dụng phép chia đôi với dãy con trái từ l đến k, và dãy con phải từ k+1 đến r - Quá trình chia dừng khi nhận được các dãy con có độ dài =1 (đã được xếp) Trộn : Trộn từng cặp dãy con (trái và phải) nhận được sau quá trình chia để nhận được dãy con được xếp lớn hơn. Và tiếp tục trộn như vậy cho đến khi nhận được dãy cần xếp ban đầu. 28
  29. Chương 8: SẮP XẾP (Sorting) 8.3. 3.Sắp xếp bằng trộn (Merge Sort) VD : dãy : 5 9 1 7 6 2 8 4 10 Lượt 1 : k =(0+8)/2=4: [5 9 1 7 6] [2 8 4 10] Chia dãy trái : [5 9 1][7 6] Chia dãy trái : [5 9][1] Chia dãy trái : [5] [9] Trộn cặp dãy nhận được : [5 9][1] Trộn : [1 5 9] Chia dãy phải : [7][6] Trộn hai dãy con : [6 7] Trộn hai dãy con : [1 5 6 7 9] 29
  30. Chương 8: SẮP XẾP (Sorting) 8.3. 3.Sắp xếp bằng trộn (Merge Sort) VD : dãy : 5 9 1 7 6 2 8 4 10 Chia dãy phải : [2 8][4 10] Chia dãy trái : [2][8] Trộn hai dãy đã xếp: [2 8] Chia dãy phải : [4][10] Trộn : [4 10] Trộn : [2 4 8 10] Trộn hai dãy đã xếp :[1 2 4 5 6 7 8 9 10] 30
  31. Chương 8: SẮP XẾP (Sorting) 8.3. 3.Sắp xếp bằng trộn (Merge Sort) Thảo luận : - Biểu diễn dữ liệu cho bài toán, Viết thủ tục và tính độ phức tạp cho giải thuật, cho dãy số và minh họa các bước thực hiện theo giải thuật. - Giải thuật trên được thiết kế theo chiến lược gì ? -Nếu không cần chia dãy thì có áp dụng được ý tưởng sắp xếp bằng trộn không? 31