Đề tài Nguyên lý sáng tạo ứng dụng trong một số thuật toán sắp xếp nội

ĐẠI HỌC QUỐC GIA TP.HCM TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN  BÀI THU HOẠCH MÔN HỌC PHƢƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC LỚP CAO HỌC KHOA HỌC MÁY TÍNH KHÓA 22 Giảng viên: GS.TSKH. Hoàng Văn Kiếm ĐỀ TÀI NGUYÊN LÝ SÁNG TẠO ỨNG DỤNG TRONG MỘT SỐ THUẬT TOÁN SẮP XẾP NỘI Học viên: Trần Huy Quang Mã số: 12 11 058 TP.HCM, 12-2012 MỤC LỤC THUẬT TOÁN SẮP XẾP ................................................................................................ 4 I. Sắp xếp theo phương pháp chọn ................................................................................ 5 1. Phương pháp chọn trực tiếp – Selection Sort ...................................................... 5 2. Phương pháp vun đống – Heap Sort.................................................................... 6 3. Đánh giá............................................................................................................... 9 II. Sắp xếp theo phương pháp chèn .............................................................................. 10 1. Phương pháp chèn trực tiếp – Insertion Sort ..................................................... 10 2. Phương pháp độ dài bước giảm dần - Shell Sort ............................................... 11 3. Đánh giá............................................................................................................. 13 III. Phương pháp sắp xếp phân hoạch - Quick Sort ....................................................... 14 1. Ý tưởng .............................................................................................................. 14 2. Thuật toán .......................................................................................................... 14 3. Minh họa ............................................................................................................ 14 4. Độ phức tạp của thuật toán ................................................................................ 15 5. Đánh giá............................................................................................................. 16 PHỤ LỤC: CÁC NGUYÊN LÝ SÁNG TẠO ............................................................... 17 1. Nguyên lý phân nhỏ .......................................................................................... 17 2. Nguyên lý “tách khỏi” ....................................................................................... 17 3. Nguyên lý phẩm chất cục bộ ............................................................................. 17 4. Nguyên lý phản đối xứng .................................................................................. 17 5. Nguyên lý kết hợp ............................................................................................. 17 6. Nguyên lý vạn năng ........................................................................................... 17 7. Nguyên lý “chứa trong”..................................................................................... 17 8. Nguyên lý phản trọng lượng .............................................................................. 17 9. Nguyên lý gây ứng suất sơ bộ ........................................................................... 18 10. Nguyên lý thực hiện sơ bộ ................................................................................. 18 11. Nguyên lý dự phòng .......................................................................................... 18 12. Nguyên lý đẳng thế ............................................................................................ 18 13. Nguyên lý đảo ngược ........................................................................................ 18 14. Nguyên lý cầu (tròn) hóa ................................................................................... 18 15. Nguyên lý linh động .......................................................................................... 18 16. Nguyên lý giải “thiếu” hoặc “thừa” .................................................................. 19 17. Nguyên lý chuyển sang chiều khác ................................................................... 19 18. Nguyên lý sử dụng các dao động cơ học ........................................................... 19 19. Nguyên lý tác động theo chu kỳ ........................................................................ 19 20. Nguyên lý liên tục tác động có ích .................................................................... 19 21. Nguyên lý “vượt nhanh” ................................................................................... 20 22. Nguyên lý biến hại thành lợi ............................................................................. 20 23. Nguyên lý quan hệ phản hồi .............................................................................. 20 24. Nguyên lý sử dụng trung gian ........................................................................... 20 25. Nguyên lý tự phục vụ ........................................................................................ 20 26. Nguyên lý sao chép (Copy) ............................................................................... 20 27. Nguyên lý “rẻ” thay cho “đắt” .......................................................................... 20 28. Thay thế sơ đồ cơ học ........................................................................................ 20 29. Sử dụng các kết cấu khí và lỏng ........................................................................ 21 30. Sử dụng vỏ dẻo và màng mỏng ......................................................................... 21 31. Sử dụng các vật liệu nhiều lỗ ............................................................................ 21 32. Nguyên lý thay đổi màu sắc .............................................................................. 21 33. Nguyên lý đồng nhất ......................................................................................... 21 34. Nguyên lý loại bỏ hoặc tái sinh từng phần ........................................................ 21 35. Thay đổi các thông số lý hóa của đối tượng ...................................................... 22 36. Sử dụng chuyển pha .......................................................................................... 22 37. Sử dụng sự nở nhiệt ........................................................................................... 22 38. Sử dụng các chất oxy hóa .................................................................................. 22 39. Sử dụng môi trường trơ ..................................................................................... 22 40. Sử dụng các vật liệu hợp thành (composite) ..................................................... 22 TÀI LIỆU THAM KHẢO .............................................................................................. 23 4 THUẬT TOÁN SẮP XẾP Sắp xếp là quá trình bố trí lại các phần tử của một tập đối tượng theo một thứ tự được ấn định, chẳng hạn tăng dần hay giảm dần đối với một dãy số. Với một cấu trúc đã được sắp xếp thì rất thuận tiện khi thực hiện các tác vụ như tìm kiếm, duyệt cấu trúc… Có hai loại thuật toán sắp xếp: Sắp xếp nội và Sắp xếp ngoại. Sắp xếp nội - Toàn bộ dữ liệu được đưa vào bộ nhớ trong. - Kích thước dữ liệu cần sắp xếp không lớn lắm. - Thời gian sắp xếp được thực hiện rất nhanh. Sắp xếp ngoại - Chỉ một phần nhỏ dữ liệu cần sắp xếp được đưa vào bộ nhớ trong, phần lớn dữ liệu còn lại được lưu ở bộ nhớ ngoài (đĩa cứng, băng từ…). - Kích thước dữ liệu sắp xếp rất lớn. - Thời gian sắp xếp chậm. Trong khuôn khổ đề tài, xét các thuật toán sắp xếp nội với thứ tự tăng dần trên mảng một chiều có N số nguyên. a1, a2, …, aN-1, aN (N>0) Sắp xếp dãy số trên là thực hiện bố trí lại các phần tử sao cho hình thành một dãy mới tăng dần. Để thay đổi vị trí các phần tử trong dãy, cần dựa vào kết quả của một loạt phép so sánh và hoán vị. Do đó hai thao tác chính của các thuật toán sắp xếp là phép so sánh và phép gán. Số lượng các phép toán này chính là chi phí thực hiện, hay còn gọi là độ phức tạp của thuật toán. Khi xây dựng thuật toán sắp xếp, cần tìm cách giảm thiểu những phép so sánh và hoán vị không cần thiết để tăng hiệu quả của thuật toán. Do dãy số được lưu trọn vẹn trong bộ nhớ chính của máy tính, nên các thuật toán sắp xếp nội thường không sử dụng các vùng nhớ thêm trong quá trình sắp xếp, mà hướng đến sắp xếp trực tiếp trên dãy số ban đầu. Một số thuật toán sắp xếp nội đề cập trong đề tài gồm Selection Sort, Heap Sort, Insertion Sort, Shell Sort, và Quick Sort. Trong đó những thuật toán như Selection Sort, Insertion Sort là những thuật toán đơn giản nhưng có chi phí cao. Trong khi các thuật toán Shell Sort, Heap Sort, và Quick Sort là những thuật toán phức tạp và có hiệu quả cao hơn. 5 I. Sắp xếp theo phƣơng pháp chọn 1. Phƣơng pháp chọn trực tiếp – Selection Sort a) Ý 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 ở đầu dãy hiện hành. Lúc này ta có dãy con đầu a1 đã có thứ tự, nên không cần quan tâm đến phần tử này nữa. Xét dãy con sau chỉ còn N-1 phần tử cần sắp xếp, lặp lại thao tác trên để đưa phần tử nhỏ nhất về đầu dãy hiện hành. Ta được dãy con đầu a1, a2 đã có thứ tự, chỉ cần sắp xếp dãy con sau có N-2 phần tử còn lại. Lặp lại như trên cho đến khi dãy con cần sắp xếp chỉ còn một phần tử, ta được dãy kết quả có thứ tự. b) Thuật toán Bước 1: i := 1 Bước 2: Tìm phần tử amin nhỏ nhất trong dãy hiện hành ai, ai+1, …, aN Bước 3: Hoán vị amin và ai Bước 4: Nếu i < N-1: tăng i thêm 1 và lặp lại Bước 2 Ngược lại: Dừng c) Minh họa Cho dãy 8 phần tử: 25 55 45 40 10 90 85 35 Dãy ban đầu 25 55 45 40 10 90 85 35 i=1 10 55 45 40 25 90 85 35 i=2 10 25 45 40 55 90 85 35 i=3 10 25 35 40 55 90 85 45 i=4 10 25 35 40 55 90 85 45 i=5 10 25 35 40 45 90 85 55 i=6 10 25 35 40 45 55 85 90 i=7 10 25 35 40 45 55 85 90 Dãy kết quả 10 25 35 40 45 55 85 90 6 d) Độ phức tạp của thuật toán - Số phép so sánh: tại mỗi lượt thứ i, cần thực hiện N-i phép so sánh để tìm phần tử nhỏ nhất trong dãy con chưa có thứ tự. Số phép so sánh không phụ thuộc vào tình trạng của dãy ban đầu, do đó tổng số phép so sánh là n(n-1)/2. - Số phép gán: tại mỗi lượt, cần thực hiện ba phép gán để hoán vị amin với ai, do đó cần 3n(n-1)/2 phép gán. Tuy nhiên điều này phụ thuộc vào tình trạng ban đầu của dãy số, nếu dãy ban đầu đã có thứ thự thì không cần thực hiện phép gán nào. - Độ phức tạp của thuật toán là T(N) = O(N2). 2. Phƣơng pháp vun đống – Heap Sort a) Ý tưởng Sử dụng một cấu trúc dữ liệu gọi là Heap cho phép tích lũy các thông tin về sự so sánh giữa các phần tử trong quá trình sắp xếp. Cấu trúc Heap Là một cây nhị phân gần đầy đủ, cài đặt bằng mảng một chiều al al+1…ar, với các nút trên heap có nội dung nhỏ hơn hay bằng nội dung của nút cha. - a0 là nút gốc (là phần tử lớn nhất) - ai  a2i - ai  a2i+1 Nút cha lớn hơn hay bằng hai nút con. (ai, a2i), (ai, a2i+1) là hai cặp phần tử liên đới. Trong đó l ≤ i ≤ r. Cấu trúc heap được cài đặt bằng một mảng một chiều: 30 26 22 21 12 19 15 16 14 8 30 26 22 21 12 19 15 16 14 8 0 1 2 3 4 5 6 7 8 9 7 Tính chất của Heap 1. Heap có nút gốc lớn nhất, đánh theo chỉ số 0, 1, 2,… cho các nút kế tiếp. Đướng đi từ gốc đến nút lá có nội dung - giá trị nút giảm dần. 2. Nếu al al+1…ar là một heap, khi cắt bỏ một số phần tử ở hai đầu của heap, thì dãy còn lại vẫn là một heap. 3. Heap con: SubHeap(p,m), có nút gốc là p và các nút con nhỏ hơn hay bằng m. (nếu p > m thì subheap rỗng) 4. Mọi dãy al al+1…ar với 2l > r là một heap. b) Thuật toán Giai đoạn 1: Hiệu chỉnh dãy số ban đầu thành heap al al+1…ar Với l=0 và r=N-1 Giai đoạn 2: Sắp xếp dãy số dựa trên heap Bước 1: Hoán vị phần tử lớn nhất - nút gốc của heap với phần tử cuối dãy Bước 2: Loại bỏ phần tử lớn nhất ra khỏi heap: r=r-1 Hiệu chỉnh phần còn lại của dãy là al al+1…ar-1 thành heap Bước 3: Nếu r>l: lặp lại Bước 2 Ngược lại: Dừng Dựa theo tính chất 4 của heap, thực hiện Giai đoạn 1 bằng cách bắt đầu từ heap mặc nhiên là dãy am+1, am+2,…, aN-1 (với m=N/2). Lần lượt thêm vào đầu heap các phần tử am, am-1, …, a0 đồng thời hiệu chỉnh dãy thành heap. c) Minh họa Cho dãy 8 phần tử: 12 2 8 5 1 6 4 15 Giai đoạn 1: Hiệu chỉnh dãy ban đầu thành heap Dãy ban đầu 12 2 8 5 1 6 4 15 l=4 12 2 8 5 1 6 4 15 12 2 8 15 1 6 4 5 l=3 12 2 8 15 1 6 4 5 12 2 8 15 1 6 4 5 l=2 12 2 8 15 1 6 4 5 8 12 2 8 15 1 6 4 5 l=1 12 2 8 15 1 6 4 5 12 15 8 2 1 6 4 5 12 15 8 5 1 6 4 2 15 12 8 5 1 6 4 2 Dãy kết quả 15 12 8 5 1 6 4 2 Giai đoạn 2: Sắp xếp dãy số dựa trên heap Heap ban đầu 15 12 8 5 1 6 4 2 r=7 2 12 8 5 1 6 4 15 Hiệu chỉnh lại heap 12 5 8 2 1 6 4 15 r=6 4 5 8 2 1 6 12 15 Hiệu chỉnh lại heap 8 5 6 2 1 4 12 15 r=5 4 5 6 2 1 8 12 15 Hiệu chỉnh lại heap 6 5 4 2 1 8 12 15 r=4 1 5 4 2 6 8 12 15 Hiệu chỉnh lại heap 5 2 4 1 6 8 12 15 r=3 1 2 4 5 6 8 12 15 Hiệu chỉnh lại heap 4 2 1 5 6 8 12 15 r=2 1 2 4 5 6 8 12 15 Hiệu chỉnh lại heap 2 1 4 5 6 8 12 15 r=1 1 2 4 5 6 8 12 15 r=l: Dừng 1 2 4 5 6 8 12 15 d) Độ phức tạp của thuật toán - Độ phức tạp của thuật toán là T(N) = O(Nlog2N) 9 3. Đánh giá Trong phương pháp Selection Sort, khi tìm phần tử nhỏ nhất ở bước thứ i thì không tận dụng được những thông tin đã có được do các phép so sánh ở bước i-1. Vấn đề này có thể giải quyết với một cấu trúc dữ liệu có khả năng tích lũy các thông tin về sự so sánh các phần tử trong quá trình sắp xếp. J.Wiliams đã đề xuất một cấu trúc như vậy, gọi là Heap trong thuật toán Heap Sort. Từ Selection Sort đến Heap Sort thể hiện những nguyên lý sáng tạo ứng dụng như sau. - Nguyên lý phân nhỏ Dãy số biểu diễn bằng mảng một chiều được chuyển sang cấu trúc heap là một cây phân cấp, như vậy một dãy đồng nhất đã được phân chia thành các thành phần độc lập, chính là các nhánh của cây. Do đó trong quá trình sắp xếp, số lượng phép so sánh và phép gán được giảm thiểu do thuật toán chỉ làm việc trên một số nhánh liên quan tại mỗi bước của thuật toán. - Nguyên lý phẩm chất cục bộ Cấu trúc mảng một chiều tuyến tính được chuyển thành cấu trúc cây phân cấp, cụ thể là cây nhị phân. Trong đó, một phần tử ở mức i là phần tử lớn trong cặp phần tử ở mức i+1, do đó phần tử ở mức 0 tức là nút gốc của cây luôn là phần tử lớn nhất trong dãy. Khi loại phần tử gốc ra khỏi cây, cần phải cập nhật lại cây để đảm bảo tính chất của heap, tuy nhiên việc cập nhật chỉ xảy ra một cách cục bộ đối với những nhánh liên quan đến phần tử vừa loại bỏ, còn các nhánh khác vẫn giữ nguyên. Như vậy bước tiếp theo của thuật toán có thể sử dụng lại kết quả của sự so sánh ở bước hiện tại. - Nguyên lý linh động Dãy số được biểu diễn một cách tự nhiên bằng cấu trúc mảng một chiều, nhưng với heap, dãy số có thể biểu diễn dưới dạng cây phân cấp. Với đặc trưng của cấu trúc cây gồm nhiều nhánh, dãy số được chia thành nhiều thành phần độc lập dưới dạng các nhánh và có khả năng dịch chuyển đối với nhau, mỗi khi cập nhật heap trong quá trình sắp xếp. - Nguyên lý chuyển sang chiều khác Ở mỗi bước sắp xếp, Selection Sort hoạt động trên toàn bộ chiều dài của dãy con còn lại nên số lượng phép so sánh luôn nhiều nhất. Hạn chế đó là do cấu trúc của mảng một chiều. Trong khi Heap Sort sử dụng cấu trúc heap là cấu trúc cây - nhiều chiều, tại mỗi bước, việc so sánh chỉ xảy ra trong nhánh liên quan nên có thể giảm thiểu số phép so sánh. 10 - Thay thế sơ đồ cơ học Phương pháp Heap Sort sử dụng cấu trúc cây phân cấp thay cho mảng một chiều với các phần tử cố định. Như vậy các phần tử đồng nhất trong dãy số đã được chuyển sang cấu trúc không đồng nhất, mỗi phần tử được phân cấp qua giá trị của nó. - Nguyên lý loại bỏ hoặc tái sinh từng phần Cấu trúc heap có nút gốc luôn là phần tử lớn nhất trong dãy hiện hành, nếu loại bỏ phần tử này khỏi cây, có nghĩa là đưa nó về vị trí đúng thì sau đó không cần quan tâm đến nó nữa. Sau khi loại bỏ nút gốc, heap cần phải phục hồi với những phần tử còn lại, tuy nhiên chi phí cho thao tác này không lớn, do việc cập nhật chỉ xảy ra cục bộ trên những nhánh liên quan trong cây. II. Sắp xếp theo phƣơng pháp chèn 1. Phƣơng pháp chèn trực tiếp – Insertion Sort a) Ý tưởng Từ dãy ban đầu, ta luôn có dãy con a1 đã có thứ tự. Chèn phần tử a2 vào dãy con đã có thứ tự trên, ta được dãy con có thứ tự mới a1, a2. Lặp lại cho đến khi chèn xong phần tử aN vào dãy con đã có thứ tự, ta được dãy kết quả có thứ tự. Như vậy, với dãy con đã có thứ tự là a1, a2, …, ai-1, cần tìm cách chèn phần tử ai vào vị trí thích hợp: - Xét 1 ≤ k ≤ i, vị trí thích hợp của ai là vị trí ở giữa ak-1 và ak nếu ak-1 ≤ ai < ak. - Dời các phần tử ak, ak+1, …, ai-1 về phía sau một vị trí và chèn ai vào vị trí k, ta được dãy a1, a2, …, ai-1 có thứ tự. b) Thuật toán Bước 1: i := 2 Bước 2: x := ai Tìm vị trí k thích hợp trong dãy con a1, a2, …, ai-1 để chèn ai vào Bước 3: Dời chỗ các phần tử ak, ak+1, …, ai-1 về phía sau một vị trí Bước 4: ak := x Bước 5: i := i+1 Nếu i  N: Lặp lại Bước 2 Ngược lại: Dừng 11 c) Minh họa Cho dãy 8 phần tử: 12 2 8 5 1 6 4 15 Dãy ban đầu 12 2 8 5 1 6 4 15 i=1 12 2 8 5 1 6 4 15 i=2 2 12 8 5 1 6 4 15 i=3 2 8 12 5 1 6 4 15 i=4 2 5 8 12 1 6 4 15 i=5 1 2 5 8 12 6 4 15 i=6 1 2 5 6 8 12 4 15 i=7 1 2 4 5 6 8 12 15 i=8 1 2 4 5 6 8 12 15 Dãy kết quả 1 2 4 5 6 8 12 15 d) Độ phức tạp của thuật toán - Trong mỗi lần lặp, cần thực hiện một phép so sánh và hai phép gán. Tổng số phép so sánh và phép gán phụ thuộc vào tình trạng ban đầu của dãy. - Độ phức tạp của thuật toán là T(N) = O(N2). 2. Phƣơng pháp độ dài bƣớc giảm dần - Shell Sort a) Ý tưởng Từ dãy ban đầu a1, a2, …, aN, chia dãy ban đầu thành h dãy con gồm các phần tử cách nhau h vị trí. Như vậy dãy ban đầu là xen kẽ của h dãy con như sau: Dãy con thứ nhất: a1, ah+1, a2h+1, … Dãy con thứ nhất: a2, ah+2, a2h+2, … … Dãy con thứ nhất: ah, a2h, a3h, … Thực hiện sắp xếp các phần tử trong cùng dãy con ta có các phần tử được đưa về vị trí đúng tương đối – có thứ tự trong dãy con đang xét. Sau đó giảm khoảng cách h để tạo thành các dãy con mới, như vậy tạo cơ hội so sánh một phần tử với nhiều phần tử 12 khác trước đó không nằm cùng dãy con. Sắp xếp những dãy con mới này. Lặp lại cho đến khi h=1, ta được dãy kết quả có thứ tự. Cách lựa chọn khoảng cách h và số bước sắp xếp là k thỏa: hi > hi+1, hk=1, với i=1..k Khoảng cách giữa các phần tử trong một dãy con ở bước sau phải nhỏ hơn bước trước. Sau k bước, khoảng cách bằng 1 (lúc này mỗi dãy con chỉ có một phần tử). Theo Knuth đề nghị: hi = (hi-1 - 1)/3, hk=1, k=log3n – 1 Hoặc: hi = (hi-1 - 1)/2, hk=1, k=log2n - 1 b) Thuật toán Bước 1: Chọn k khoảng cách h1, h2, …, hk i := 1 Bước 2: Chia dãy ban đầu thành các dãy con cách nhau hi phần tử Sắp xếp từng dãy con theo phương pháp Chèn trực tiếp Bước 3: i := i+1 Nếu i ≤ k: Lặp lại Bước 2 Ngược lại: Dừng c) Minh họa Cho dãy 8 phần tử: 12 2 8 5 1 6 4 15 Chọn k=3 và các khoảng cách h1=5, h2=3, h3=1 - h=5 12 2 8 5 1 6 4 15 Sắp xếp các dãy con theo phương pháp Chèn trực tiếp 6 2 8 5 1 12 4 15 - h=3 6 2 4 5 1 12 8 15 13 Sắp xếp các dãy con theo phương pháp Chèn trực tiếp 5 1 4 6 2 12 8 15 - h=1 5 1 4 6 2 12 8 15 Sắp xếp các dãy con theo phương pháp Chèn trực tiếp 1 2 4 5 6 8 12 15 - Dừng do h=1 d) Độ phức tạp của thuật toán - Hiệu quả thuật toán phụ thuộc vào các dãy con với các độ dài được chọn. - Khi chọn theo công thức Knuth: hi = (hi-1-1)/2, hk=1, k=log2n-1, thuật toán có độ phức tạp là T(N) = O(N1.2). 3. Đánh giá Hai thuật toán Insertion Sort và Shell Sort cùng dựa trên ý tưởng chèn một phần tử v