Đề 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ào một dãy có thứ tự. Tuy nhiên độ phức tạp của thuật toán Shell Sort là O(N1.2) nhỏ hơn rất nhiều so với độ phức tạp O(N2) của Insertion Sort. Sự cải tiến này có thể nói là kết quả của việc ứng dụng những nguyên lý sáng tạo trong quá trình xây dựng thuật toán. - Nguyên lý phân nhỏ Trong phương pháp Shell Sort, dãy ban đầu được chia thành nhiều dãy con độc lập và tiến hành sắp xếp trên từng dãy con, giúp giảm thiểu số phép so sánh và phép gán. Rồi tiếp tục tăng mức độ phân nhỏ các dãy con, cho đến khi độ dài của mỗi dãy con chỉ là một thì được dãy kết quả có thứ tự. - Nguyên lý thực hiện sơ bộ Trong phương pháp Insertion Sort, phần tử cần chèn luôn được so sánh trong một dãy tổng thể có độ dài tối đa, dẫn đến mất thời gian so sánh và dịch chuyển. Phương pháp Shell Sort thực hiện sắp xếp các phần tử trong cùng dãy con để đưa chúng về vị trí đúng tương đối rất nhanh – chỉ có thứ tự trong dãy con đang xét. Sau đó 14 giảm độ dài các dãy con, tạo cơ hội so sánh một phần tử với nhiều phần tử khác trước đó không nằm cùng dãy con với nó. - Nguyên lý linh động Phương pháp Shell Sort chia dãy ban đầu thành các phần xen kẽ và tiến hành sắp xếp trên từng phần. Các phần này có khả năng dịch chuyển đối với nhau khi giảm khoảng cách h, khi đó mức độ xen kẽ tăng lên và các phần có cơ hội tương tác với nhau. III. Phƣơng pháp sắp xếp phân hoạch - Quick Sort 1. Ý tƣởng Chọn ngẫu nhiên một phần tử x, gọi là phần tử khóa, trong dãy a1, a2, …, aN, phân hoạch dãy này thành ba dãy con liên tiếp: Dãy con 1: ak < x với k=1…i Dãy con 2: ak = x với k=i…j (đã được sắp thứ tự) Dãy con 3: ak > x với k=j…N Nếu dãy con 1 và 3 chỉ có một phần tử thì dãy a1, a2, …, aN đã được sắp xếp. Ngược lại, dãy con 1 và 3 có nhiều hơn một phần tử, tiếp tục phân hoạch dãy con 1 và 3 thành các dãy con tương tự như trên. Phần tử x được chọn có tác động rất nhiều đến hiệu quả của thuật toán, vì nó quyết định số lần phân hoạch dãy. Số lần phân hoạch sẽ ít nhất nếu chọn được phần tử x có độ lớn trung bình của dãy. Tuy nhiên việc chọn được phần tử x như vậy là rất khó, nên người ta thường chọn phần tử ở giữa dãy làm mốc phân hoạch. Khi đó, với l=1 và r=N thì ak là phần tử mốc, với k=(l+r)/2. 2. Thuật toán Bước 1: Phân hoạch dãy al, al+1, …, 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: Đệ quy: Nếu (l<j): Phân hoạch dãy con al, al+1, …, aj Nếu (i<r): Phân hoạch dãy con ai, ai+1, …, ar 3. Minh họa Cho dãy 8 phần tử: 12 2 8 5 1 6 4 15 - Phân hoạch đoạn l=1, r=8, x=a4=5 15 12 2 8 5 1 6 4 15 4 2 1 5 8 6 12 15 - Phân hoạch đoạn l=1, r=3, x=a2=2 4 2 1 5 8 6 12 15 1 2 4 5 8 6 12 15 1 2 4 5 8 6 12 15 - Phân hoạch đoạn l=5, r=8, x=a6=6 1 2 4 5 8 6 12 15 1 2 4 5 6 8 12 15 1 2 4 5 6 8 12 15 - Phân hoạch đoạn l=7, r=8, x=a7=12 1 2 4 5 6 8 12 15 1 2 4 5 6 8 12 15 4. Độ phức tạp của thuật toán Hiệu quả của thuật toán phụ thuộc vào cách chọn giá trị khóa x. Trường hợp tốt nhất là mỗi lần phân hoạch chọn được phần tử trung bình - phần tử lớn hơn hay bằng nửa số phần tử và nhỏ hơn hay bằng nửa số phần tử còn lại. Trường hợp xấu nhất là khi phân hoạch một dãy luôn được hai phần, phần thứ nhất chỉ có một phần tử, trong khi phần còn lại có r-1 phần tử. Lúc này cần tới N lần phân hoạch. Độ phức tạp của thuật toán sẽ là O(N2). Trong khi độ phức tạp trong trường hợp 16 tốt nhất của thuật toán là O(log2N). Độ phức tạp trung bình của thuật toán: O(Nlog2N). 5. Đánh giá Như cái tên Quick Sort, thuật toán có chi phí trong trường hợp tốt nhất chỉ là log2N. Điều này đạt được nhờ kết hợp kỹ thuật chia để trị cùng với đệ quy. Có thể nhận thấy những nguyên lý sáng tạo trong thiết kế thuật toán này như sau. - Nguyên lý phân nhỏ Dãy ban đầu được phân nhỏ thành các dãy con với những đặc trưng riêng biệt phục vụ cho quá trình sắp xếp. Sau đó đến lượt các dãy con được xử lý độc lập, với cùng một cách thức như trên, nghĩa là tăng mức độ phân nhỏ các dãy con. Cho đến khi không thể phân nhỏ các dãy con được nữa thì dãy ban đầu đã được sắp thứ tự. - Nguyên lý “tách riêng” Trong quá trình sắp xếp, phép so sánh là thao tác được thực hiện nhiều nhất, đặc biệt là so sánh khóa x với các phần tử khác trong dãy. Sau khi phân hoạch, các phần tử có giá trị bằng với khoá x được tách riêng ra, sau đó thì không cần quan tâm đến nữa. như vậy giúp giảm những phép so sánh không cần thiết. - Nguyên lý phẩm chất cục bộ Dãy số cần sắp thứ tự là một cấu trúc đồng nhất – mảng một chiều, được chuyển thành đối tượng không đồng nhất với mỗi phần có chức năng khác nhau, cụ thể là so với phần tử khóa x, tạo điều kiện thuận lợi cho bước tiếp theo trong quá trình sắp xếp. 17 PHỤ LỤC: CÁC NGUYÊN LÝ SÁNG TẠO 1. Nguyên lý phân nhỏ - Chia đối tượng thành các phần độc lập. - Làm đối tượng trở nên tháo lắp được. - Tăng mức độ phân nhỏ đối tượng. 2. Nguyên lý “tách khỏi” - Tách phần gây “phiền phức” (tính chất “phiền phức”) hay ngược lại tách phần duy nhất “cần thiết” (tính chất “cần thiết”) ra khỏi đối tượng. 3. Nguyên lý phẩm chất cục bộ - Chuyển đối tượng (hay môi trường bên ngoài, tác động bên ngoài) có cấu trúc đồng nhất thành không đồng nhất. - Các phần khác nhau của đối tượng phải có các chức năng khác nhau. - Mỗi phần của đối tượng phải ở trong những điều kiện thích hợp nhất đối với công việc. 4. Nguyên lý phản đối xứng - Chuyển đối tượng có hình dạng đối xứng thành không đối xứng (nói chung giảm bậc đối xứng). 5. Nguyên lý kết hợp - Kết hợp các đối tượng đồng nhất hoặc các đối tượng dùng cho các hoạt động kế cận. - Kết hợp về mặt thời gian các hoạt động đồng nhất hoặc kế cận. 6. Nguyên lý vạn năng - Đối tượng thực hiện một số chức năng khác nhau, do đó là không cần sự tham gia của đối tượng khác. 7. Nguyên lý “chứa trong” - Một đối tượng được đặt bên trong đối tượng khác và bản thân nó lại chứa đối tượng thứ ba… - Một đối tượng chuyển động xuyên suốt bên trong đối tượng khác. 8. Nguyên lý phản trọng lƣợng - Bù trù trọng lượng của đối tượng bằng cách gắn nó với đối tượng khác, có lực nâng. 18 - Bù trừ trọng lượng của đối tượng bằng tương tác với môi trường như sử dụng các lực thủy động, khí động… 9. Nguyên lý gây ứng suất sơ bộ - Gây ứng suất trước đối với đối tượng để chống lại ứng suất không cho phép hoặc không mong muốn khi đối tượng làm việc (hoặc gây ứng suất trước để khi làm việc sẽ dùng ứng suất ngược lại). 10. Nguyên lý thực hiện sơ bộ - Thực hiện trước sự thay đổi cần có, hoàn toàn hoặc từng phần đối với đối tượng. - Cần sắp xếp đối tượng trước, sao cho chúng có thể hoạt động từ vị trí thuận lợi nhất, không mất thời gian dịch chuyển. 11. Nguyên lý dự phòng - Bù đắp độ tin cậy không lớn của đối tượng bằng cách chuẩn bị các phuơng tiện báo động, ứng cứu, an toàn. 12. Nguyên lý đẳng thế - Thay đổi điều kiện làm việc để không phải nâng lên hay hạ xuống các đối tượng. 13. Nguyên lý đảo ngƣợc - Thay vì hành động như yêu cầu của bài toán, hành động ngược lại (ví dụ không làm nóng mà làm lạnh đối tượng). - Làm phần chuyển động của đối tượng (hay mội trường bên ngoài) thành đứng yên và ngược lại phần đứng yên thành chuyển động. 14. Nguyên lý cầu (tròn) hóa - Chuyển những phần thẳng của đối tượng thành cong, mặt phẳng thành mặt cầu, kết cấu hình hộp thành kết cấu hình cầu. - Sử dụng các con lăn, viên bi, vòng xoắn. - Chuyển sang chuyển động quay, sử dụng lực ly tâm. 15. Nguyên lý linh động - Cần thay đổi các đặc trưng của đối tượng hay môi trường bên ngoài sao cho chúng tối ưu trong từng giai đoạn làm việc. - Phân chia đối tượng thành từng phần, có khả năng dịch chuyển đối với nhau. 19 16. Nguyên lý giải “thiếu” hoặc “thừa” - Nếu như khó nhận được 100% hiệu quả cần thiết, nên nhận ít hơn hoặc nhiều hơn “một chút”. Lúc đó bài toán có thể trở nên đơn giản hơn và dễ giải hơn. 17. Nguyên lý chuyển sang chiều khác - Những khó khăn do chuyển động (hay sắp xếp) đối tượng theo đường (một chiều) sẽ được khắc phục nếu cho đối tượng có khả năng di chuyển trên mặt phẳng (hai chiều), tương tự, những bài toán liên quan đến chuyển động (hay sắp xếp) các đối tượng trên mặt phẳng sẽ đơn giản hóa khi chuyển sang không gian (ba chiều). - Chuyển các đối tượng có kết cấu một tầng thành nhiều tầng. - Đặt đối tượng nằm nghiêng. - Sử dụng mặt sau của diện tích cho trước. - Sử dụng các luồng ánh sáng tới diện tích bên cạnh hoặc tới mặt sau của diện tích cho trước. 18. Nguyên lý sử dụng các dao động cơ học - Làm đối tượng dao động. - Nếu đã có dao động tăng tần số dao động (đến tần số siêu âm). - Sử dụng tần số cộng hưởng. - Thay vì dùng các bộ rung cơ học, dùng các bộ rung áp điện. - Sử dụng siêu âm kết hợp với trường điện từ. 19. Nguyên lý tác động theo chu kỳ - Chuyển tác động liên tục thành tác động theo chu kỳ (xung). - Nếu đã có tác động theo chu kỳ, hãy thay đổi chu kỳ. - Sử dụng các khoảng thời gian giữa các xung để thực hiện tác động khác. 20. Nguyên lý liên tục tác động có ích - Thực hiện công việc một cách liên tục (tất cả các phần của đối tượng cần luôn luôn làm việc ở chế độ đủ tải). - Khắc phục vận hành không tải và trung gian. - Chuyển chuyển động tịnh tiến qua lại thành chuyển động quay. 20 21. Nguyên lý “vƣợt nhanh” - Vượt qua những giai đoạn có hại hoặc nguy hiểm với vận tốc lớn. - Vượt nhanh để có được hiệu ứng cần thiết. 22. Nguyên lý biến hại thành lợi - Sử dụng những tác nhân có hại (ví dụ tác động có hại của môi trường) để thu được hiệu ứng có lợi. - Khắc phục tác nhân có hại bằng cách kết hợp nó với tác nhân có hại khác. - Tăng cường tác nhân có hại đến mức nó không còn có hại nữa. 23. Nguyên lý quan hệ phản hồi - Thiết lập quan hệ phản hồi. - Nếu đã có quan hệ phản hồi, hãy thay đổi nó. 24. Nguyên lý sử dụng trung gian - Sử dụng đối tượng trung gian, chuyển tiếp. 25. Nguyên lý tự phục vụ - Đối tượng phải tự phục vụ bằng cách thực hiện các thao tác phụ trợ, sửa chữa. - Sử dụng phế liệu, chất thải, năng lượng dư. 26. Nguyên lý sao chép (Copy) - Thay vì sử dụng cái không được phép, phức tạp, đắt tiền, không tiện lợi hoặc dễ vỡ, sử dụng bản sao. - Thay thế đối tượng hay hệ các đối tượng bằng bản sao quang học (ảnh, hình vẽ) với tỉ lệ cần thiết. - Nếu không thể sử dụng bản sao quang học ở vùng biểu kiến (vùng ánh sáng nhìn thấy được bằng mắt thường), chuyển sang sử dụng các bản sao hồng ngoại hoặc tử ngoại. 27. Nguyên lý “rẻ” thay cho “đắt” - Thay đối tượng đắt tiền bằng bộ các đối tượng rẻ có chất lượng kém hơn (ví dụ như về tuổi thọ). 28. Thay thế sơ đồ cơ học - Thay thế sơ đồ cơ học bằng điện, quang, nhiệt, âm hoặc mùi vị. 21 - Sử dụng điện trường, từ trường và điện từ trường trong tương tác đối với đối tượng. - Chuyển các trường đứng yên sang chuyển động, các trường cố định sang thay đổi theo thời gian, các trường đồng nhất sang có cấu trúc nhất định. - Sử dụng các trường kết hợp với các hạt sắt từ. 29. Sử dụng các kết cấu khí và lỏng - Thay cho các phần của đối tượng ở thể rắn, sử dụng các chất khí và lỏng; nạp khí, nạp chất lỏng, đệm không khí, thủy tĩnh, thủy phản lực. 30. Sử dụng vỏ dẻo và màng mỏng - Sử dụng các vỏ dẻo và màng mỏng thay cho các kết cấu khối. - Cách ly đối tượng với môi trường ngoài bên ngoài bằng các vỏ dẻo và màng mỏng. 31. Sử dụng các vật liệu nhiều lỗ - Làm cho đối tượng có nhiều lỗ hoặc sử dụng thêm những chi tiết nhiều lỗ (miếng đệm, tấm phủ…). - Nếu đối tượng đã có nhiều lỗ, sơ bộ tẩm nó bằng chất nào đó. 32. Nguyên lý thay đổi màu sắc - Thay đổi màu sắc của đối tượng hay môi trường bên ngoài. - Thay đổi độ trong suốt của đối tượng hay môi trường bên ngoài. - Để có thể quan sát được những đối tượng hoặc những quá trình, sử dụng các chất phụ gia màu, huỳnh quang. - Nếu các chất phụ gia đó đã được sử dụng, dùng các nguyên tử đánh dấu. - Sử dụng các hình vẽ, ký hiệu thích hợp. 33. Nguyên lý đồng nhất - Những đối tượng, tương tác với các đối tượng cho trước, phải được làm từ cùng một vật liệu (hoặc từ vật liệu gần về các tính chất) với các vật liệu chế tạo đối tượng cho trước. 34. Nguyên lý loại bỏ hoặc tái sinh từng phần - Phần đối tượng đã hoàn thành nhiệm vụ hoặc trở nên không cần thiết phải tự phân hủy (hoà tan, bay hơi…) hoặc phải biến dạng. - Các phần mất mát của đối tượng phải được phục hồi trực tiếp trong quá trình 22 làm việc. 35. Thay đổi các thông số lý hóa của đối tƣợng - Thay đổi trạng thái của đối tượng. - Thay đổi nồng độ hay độ đậm đặc. - Thay đổi độ dẻo. - Thay đổi nhiệt độ, thể tích. 36. Sử dụng chuyển pha - Sử dụng các hiện tượng, nảy sinh trong các quá trình chuyển pha như thay đổi thể tích, tỏa hay hấp thu nhiệt lượng… 37. Sử dụng sự nở nhiệt - Sử dụng sự nở (hay co) nhiệt của các vật liệu. - Nếu đã dùng sự nở nhiệt, sử dụng với vật liệu có các hệ số nở nhiệt khác nhau. 38. Sử dụng các chất oxy hóa - Thay không khí thường bằng không khí giàu Oxy. - Thay không khí giàu Oxy bằng chính Oxy. - Dùng các bức xạ ion hóa tác động lên không khí hoặc oxy. - Thay oxy giàu Ôzôn (hoặc ôxy bị ion hoá) bằng chính ôzôn. 39. Sử dụng môi trƣờng trơ - Thay môi trường thông thường bằng môi trường trung hòa. - Đưa thêm vào đối tượng các phần, các chất, phụ gia trung hòa… - Thực hiện quá trình trong chân không. 40. Sử dụng các vật liệu hợp thành (composite) - Chuyển từ các vật liệu đồng nhất sang sử dụng các vật liệu hợp thành (composite). Hay nói chung, sử dụng các loại vật liệu mới. 23 TÀI LIỆU THAM KHẢO 1. Bài giảng Phương pháp nghiên cứu khoa học trong tin học – Hoàng Văn Kiếm 2. Phương pháp luận sáng tạo khoa học kỹ thuật – Phan Dũng