Tìm hiểu về thuật toán sắp xếp

Nội dung text: Tìm hiểu về thuật toán sắp xếp

1. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp NGHIÊN CỨU KHOA HỌC Đề tài : Tìm hiểu về Thuật Tốn Sắp Xếp Sinh viên thực hiện:Nguyễn Hải Nam 1
2. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp Mục lục NGHIÊN CỨU KHOA HỌC 1 Đề tài : Tìm hiểu về Thuật Tốn Sắp Xếp 1 Mục lục 2 PHẦN MỞ ĐẦU 4 1. Lý do chọn đề tài 4 2. Mục tiêu và nhiệm vụ 5 Chƣơng 1. MỘT SỐ KIẾN THỨC CƠ SỞ 6 1.1. Thuật tốn 6 1.1.1. Khái niệm thuật tốn 6 1.1.2. Các đặc trƣng của thuật tốn 7 Chƣơng 2. MƠ PHỎNG THUẬT TỐN 10 2.1. Tổng quan về mơ phỏng thuật tốn 10 2.1.1. Khái niệm mơ phỏng thuật tốn 10 2.1.2. Lịch sử mơ phỏng thuật tốn 11 2.1.3. Tác dụng của mơ phỏng thuật tốn 14 2.1.4. Kiến trúc của hệ thống mơ phỏng thuật tốn 18 2.1.5. Lựa chọn cơng cụ mơ phỏng thuật tốn 20 2.2. Một số yêu cầu đối với mơ phỏng thuật tốn 21 2.2.1. Mơ tả đúng theo thuật tốn 21 2.2.2. Hệ thống mơ phỏng phải đƣợc thực hiện theo từng bƣớc 21 2.2.3. Mơ phỏng thuật tốn phải cĩ tính động 21 2.2.4. Phải tạo ra sự phân cấp cho ngƣời học 22 2.2.5. Cấu trúc của mơ phỏng thuật tốn 22 2.3. Quy trình thiết kế nhiệm vụ mơ phỏng thuật tốn 23 2.3.1. Nghiên cứu và phân tích giải thuật 23 2.3.2. Phân tích giải thuật thành nhiều bƣớc, sau đĩ lần lƣợt mơ phỏng từng bƣớc đĩ 26 2.3.3. Phân tích khả năng tổng hợp các bƣớc đã phân tích thành giải thuật 27 2.3.4. Phân tích những khĩ khăn và thuận lợi với những ngƣời lần đầu tiên biết đến giải thuật 27 2.4. Kết luận 28 Chƣơng3 : CHƢƠNG TRÌNH ỨNG DỤNG THUẬT TỐN SẮP XẾP 29 3.1 CÁC THUẬT TỐN SẮP XẾP ĐƠN GIẢN 30 3.1.1 Sắp xếp lựa chọn 30 3.1.2 Sắp xếp xen vào 32 3.1.3 Sắp xếp nổi bọt 33 3.2 Sắp xếp hịa nhập 35 Sinh viên thực hiện:Nguyễn Hải Nam 2
3. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp 3.3 Sắp xếp nhanh 38 3.4 Sắp xếp sử dụng cây thứ tự bộ phận 45 Sinh viên thực hiện:Nguyễn Hải Nam 3
4. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp PHẦN MỞ ĐẦU 1. Lý do chọn đề tài Trong hai thập kỷ qua, mơ phỏng thuật tốn đã đƣợc các nhà sƣ phạm của ngành cơng nghệ thơng tin sử dụng nhƣ một cơng cụ cĩ tính chất giúp đỡ trong việc dạy các thuật tốn đồ thị, các thuật tốn sắp xếp, khác nhau bằng máy tính. Nguyên nhân của việc mơ phỏng thuật tốn đƣợc sử dụng nhƣ một cơng cụ trợ giúp cho việc giảng dạy là do nĩ cĩ thể cung cấp các mơ phỏng động bằng đồ họa của một thuật tốn và các thay đổi trong cấu trúc dữ liệu của nĩ trong suốt quá trình thực thi. Nhƣ một phần của quá trình học thuật tốn, những sinh viên ngành cơng nghệ thơng tin sẽ học về cấu trúc của một trình biên dịch (compiler) trong một ngơn ngữ lập trình cho quá trình đĩ. Điều này sẽ chỉ ra cho chúng ta từng nhiệm vụ của các giai đoạn khác nhau trong trình biên dịch. Hiện nay, một số hệ thống mơ phỏng thuật tốn đƣợc phát triển sau hai thập kỷ. Hầu hết các thuật tốn đƣợc đề cập đến trong giai đoạn này đều là các hệ thống phổ biến hơn và tinh vi hơn các hệ thống mà thực tế đang sử dụng. Mơ phỏng thuật tốn ngày càng trở nên hữu ích và trở thành một giáo cụ trực quan rất quan trọng trong hầu hết các lĩnh vực, nhất là trong mơi trƣờng giáo dục. Với các nhà sƣ phạm của ngành cơng nghệ thơng tin thì mơ phỏng thuật tốn cĩ tác dụng nhƣ một tài liệu hƣớng dẫn trong việc dạy các thuật tốn bằng máy tính. Đặc biệt, nĩ giúp học sinh và sinh viên hiểu cấu trúc dữ liệu và thuật tốn nhanh hơn. Nhƣ vậy, mơ phỏng thuật tốn gĩp phần to lớn vào việc ứng dụng CNTT trong giảng dạy và gĩp phần vào sự phát triển nhanh chĩng của hệ thống elearning. Sinh viên thực hiện:Nguyễn Hải Nam 4
5. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp Thuật tốn về sắp xếp rất đa dạng và phong phú. Vì vậy vấn đề “ Mơ phỏng thuật tốn sắp xếp ” đƣợc chọn để nghiên cứu trong khĩa luận này. 2. Mục tiêu và nhiệm vụ Nghiên cứu tổng quan về mơ phỏng thuật tốn. Hƣớng đến các kỹ thuật lập trình với mã nguồn mở và ngơn ngữ lập trình C# Áp dụng kết quả nghiên cứu làm một demo mơ phỏng thuật tốn sắp xếp 3. Cấu trúc khĩa luận Chƣơng 1: Một số kiến thức cơ sở Trình bày khái niệm thuật tốn, các đặc trƣng của thuật tốn Độ phức tạp của thuật tốn Chƣơng 2: Mơ phỏng thuật tốn Tổng quan về mơ phỏng thuật tốn Một số yêu cầu đối với mơ phỏng thuật tốn Quy trình thiết kế nhiệm vụ mơ phỏng thuật tốn Chƣơng 3: Chƣơng trình ứng dụng thuật tốn sắp xếp Phân tích và thiết kế hệ thống mơ phỏng thuật tốn sắp xếp Phân tích một số thuật tốn hiện tại Sinh viên thực hiện:Nguyễn Hải Nam 5
6. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp Chƣơng 1. MỘT SỐ KIẾN THỨC CƠ SỞ 1.1. Thuật tốn 1.1.1. Khái niệm thuật tốn Thuật ngữ “algorithm” (thuật tốn hoặc cịn gọi là giải thuật) đƣợc gọi theo tên nhà tốn học Ả rập thế kỷ IX al-Khowarizmi, ngƣời đã viết cuốn sách về các chữ số Hindu – cơ sở của kí hiệu số thập phân hiện đại (xem [4], trang 118). Xuất xứ ban đầu là từ algorism, đƣợc dùng để chỉ các quy tắc thực hiện các phép tính số học trên các số thập phân. Sau đĩ, vào thế kỷ XVIII algorism biến thành algorithm. Với sự quan tâm ngày càng tăng đối với máy tính, khái niệm thuật tốn đã đƣợc cho một ý nghĩa chung hơn, bao hàm cả các thủ tục xác định để giải các bài tốn, chứ khơng phải chỉ là thủ tục để thực hiện các phép tính số học. Thuật tốn là một dãy hữu hạn các thao tác đƣợc sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy các thao tác ấy, từ Input của bài tốn ta nhận đƣợc Output cần tìm. Cũng cĩ thế xem thuật tốn nhƣ một cơng cụ để giải quyết một bài tốn cụ thể. Phát biểu bài tốn sẽ chỉ định tổng quát mối quan hệ Input/Output cần thiết. Thuật tốn mơ tả một thủ tục tính tốn cụ thể để đạt đƣợc mối quan hệ Input/Output đĩ. Vào khoảng những năm 1930 - 1936, lần lƣợt các nhà tốn học K.Gưdel, S. Kleene, A. Church, A. Turing đã đề ra một số định nghĩa khác nhau cho Sinh viên thực hiện:Nguyễn Hải Nam 6
7. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp khái niệm thuật tốn. Trong số các định nghĩa tốn học khác nhau (nhƣng tƣơng đƣơng) về thuật tốn, các khái niệm Máy Turing (1937) và Hàm đệ quy (1931-1936) đƣợc sử dụng rộng rãi hơn vì cĩ nhiều thuận tiện cho các nghiên cứu cả về lí thuyết lẫn thực hành. 1.1.2. Các đặc trƣng của thuật tốn Các thuật tốn cĩ một số tính chất chung, đĩ là: Đầu vào (Input): Một thuật tốn cĩ các giá trị đầu vào từ một tập xác định. Đầu ra (Output): Từ mỗi tập giá trị đầu vào, thuật tốn sẽ tạo ra các giá trị đầu ra. Các giá trị đầu ra chính là nghiệm của bài tốn. Tính xác định: Các bƣớc của thuật tốn phải đƣợc xác định một cách chính xác. Tính đúng đắn: Một thuật tốn phải cho các giá trị đầu ra đúng đối với mỗi tập giá trị đầu vào. Tính hữu hạn: Một thuật tốn phải tạo ra các giá trị đầu ra sau một số hữu hạn (cĩ thể rất lớn) các bƣớc thực hiện đối với mỗi tập đầu vào. Tính hiệu quả: Mỗi bƣớc của thuật tốn phải thực hiện đƣợc một cách chính xác và trong một khoảng thời gian chấp nhận đƣợc. Sinh viên thực hiện:Nguyễn Hải Nam 7
8. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp Tính tổng quát: Thuật tốn cần phải áp dụng đƣợc cho mọi tập dữ liệu đầu vào của bài tốn, chứ khơng phải chỉ cho một tập đặc biệt các giá trị đầu vào. 1.2.Độ phức tạp của thuật tốn Cần chú ý rằng mỗi thuật tốn chỉ giải một lớp bài tốn nào đĩ, nhƣng cĩ thể cĩ nhiều thuật tốn khác nhau giải cùng một bài tốn. Một vấn đề đặt ra là ta cần chọn một thuật tốn tốt để giải bài tốn đã cho. Nhƣng thế nào là thuật tốn tốt? Thƣớc đo hiệu quả là thời gian máy tính sử dụng để giải bài tốn theo thuật tốn đang xét khi các giá trị đầu vào cĩ kích thƣớc xác định, và dung lƣợng bộ nhớ địi hỏi để thực hiện thuật tốn đĩ. Nhƣ vậy khi xem xét đến độ phức tạp tính tốn của thuật tốn ta phải xem xét đến độ phức tạp thời gian và độ phức tạp khơng gian. Độ phức tạp khơng gian gắn liền với cấu trúc dữ liệu cụ thể đƣợc dùng để thực hiện thuật tốn. Độ phức tạp thời gian: Độ phức tạp thời gian của một thuật tốn cĩ thể biểu diễn qua số phép tốn thực hiện thuật tốn đĩ khi các giá trị đầu vào cĩ kích thƣớc xác định. Độ phức tạp trong trƣờng hợp xấu nhất là trƣờng hợp phải dùng tối đa các phép tốn để giải bài tốn theo thuật tốn đang xét. Độ phức tạp trong trƣờng hợp trung bình, trong trƣờng hợp này ta phải đi tìm số trung bình các phép tốn để giải bài tốn trên tồn bộ các giá trị đầu vào cĩ kích thƣớc đã cho. Các thuật ngữ thường dùng cho độ phức tạp của thuật tốn: O(1): Độ phức tạp hằng số Sinh viên thực hiện:Nguyễn Hải Nam 8
9. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp O(logn): Độ phức tạp lơgarit O(n): Độ phức tạp tuyến tính O(nlogn): Độ phức tạp nlogn O(nb): Độ phức tạp đa thức O(bn), b > 1: Độ phức tạp hàm mũ O(n!): Độ phức tạp giai thừa Sinh viên thực hiện:Nguyễn Hải Nam 9
10. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp Chƣơng 2. MƠ PHỎNG THUẬT TỐN 2.1. Tổng quan về mơ phỏng thuật tốn 2.1.1. Khái niệm mơ phỏng thuật tốn Mơ phỏng thuật tốn là quá trình tách dữ liệu, thao tác, ngữ nghĩa và tạo mơ phỏng đồ họa cho quá trình trên [Stasko 1990] (xem [23]). Mơ phỏng thuật tốn đƣợc thiết kế để giúp ngƣời dùng cĩ thể hiểu thuật tốn, đánh giá chƣơng trình và sửa lỗi chƣơng trình. Một chƣơng trình máy tính chứa các cấu trúc dữ liệu của thuật tốn mà nĩ thực thi. Trong quá trình thực thi chƣơng trình, các giá trị trong cơ sở dữ liệu đƣợc thay đổi. Mơ phỏng thuật tốn sử dụng biểu diễn đồ họa để biểu diễn cấu trúc dữ liệu và chỉ ra sự thay đổi giá trị trong cơ sở dữ liệu trong mỗi trạng thái. Thơng qua đĩ, ngƣời sử dụng cĩ thể xem đƣợc từng bƣớc thực thi chƣơng trình và nhờ vậy cĩ thể hiểu chi tiết đƣợc thuật tốn. Mơ phỏng thuật tốn cũng đƣợc dùng để đánh giá một chƣơng trình đã cĩ bằng cách cung cấp các mơ phỏng cho các thành phần của hệ thống, nhờ đĩ cĩ thể kiểm tra đƣợc hiệu năng của hệ thống. Bên cạnh việc giúp ngƣời sử dụng hiểu hơn về hệ thống, mơ phỏng thuật tốn cịn đƣợc dùng để giúp thực hiện quá trình dị lỗi dễ dàng hơn. Để sử dụng mơ phỏng thuật tốn trong quá trình dị lỗi của một chƣơng trình, ngƣời sử dụng chú thích vào các trạng thái của chƣơng trình để tạo ra các lệnh mơ phỏng, sau đĩ chúng sẽ đƣợc đƣa vào hệ thống mơ phỏng thuật tốn để tạo mơ phỏng. Ngƣời sử dụng cĩ thể xem chƣơng trình của họ đã thực hiện nhƣ thế nào, các giá trị dữ liệu ở mỗi bƣớc và một bƣớc sẽ ảnh hƣởng Sinh viên thực hiện:Nguyễn Hải Nam 10
11. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp tới các bƣớc sau nhƣ thế nào. Nĩ sẽ giúp ngƣời sử dụng tìm ra tất cả các lỗi cĩ thể xảy ra trong chƣơng trình. 2.1.2. Lịch sử mơ phỏng thuật tốn Mơ phỏng thuật tốn đã đƣợc xây dựng từ hai thập kỷ gần đây. Nhƣng chƣơng trình mơ phỏng thuật tốn đầu tiên là của Ken Knowlton ở Bell Telephone Laboratories khi mơ phỏng ngơn ngữ liên kết danh sách vào năm 1966. Mơ phỏng thuật tốn phát triển mạnh vào đầu những năm 80 của thế kỷ 20. Vào năm 1981, video (sorting out sorting) đƣợc xây dựng bởi Ronald Baecker ở đại học Toronto đƣợc coi là khởi điểm của lĩnh vực mơ phỏng thuật tốn. Từ đĩ các nhà giáo dục đã sử dụng mơ phỏng thuật tốn để trợ giúp quá trình dạy học. Giữa những năm 80 và đầu những năm 90, hai hệ thống cĩ ảnh hƣởng mạnh đến về sau đƣợc phát triển và cĩ ý nghĩa lớn trên tất cả những hệ thống sau này. Hai hệ thống này là BALSA-I (Brown ALgorithm Simulator and Animator) [Brown 1984] và TANGO (Transition- based Animation GeneratiOn) [Stasko 1990]. BALSA-I là hệ thống mơ phỏng thuật tốn nổi tiếng rộng khắp đầu tiên. Nĩ đƣợc phát triển bởi Marc Brown và Robert Sedgewick tại trƣờng đại học Brown. BALSA-I là hệ thống mơ phỏng thuật tốn tƣơng tác mà hỗ trợ đồng thời nhiều cái nhìn của một cấu trúc dữ liệu thuật tốn và cĩ thể hiển thị nhiều thuật tốn thực thi đồng thời. Sự phát triển của nĩ là động cơ thúc đẩy các nhà nghiên cứu khác tham gia vào việc phát triển các hệ thống mơ phỏng thuật tốn khác nữa. Một hệ thống khác là TANGO, đƣợc phát triển bởi John Stasko của trƣờng đại học Brown. Sự nổi bật của TANGO là chỉ ra mơ hình path- Sinh viên thực hiện:Nguyễn Hải Nam 11
12. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp transition để thiết kế mơ phỏng và một framework cho hệ thống mơ phỏng thuật tốn. Nĩ đƣa ra một khái niệm framework mới mà đƣợc chấp nhận bởi một số hệ thống sau này nhƣ kiến trúc cơ sở của chúng. Kiến trúc này sẽ đƣợc mơ tả trong mục tiếp theo. Từ khi hai hệ thống của BALSA và TANGO đƣợc phát triển, các hệ thống đi sau của hai hệ thống đáng chú ý này cũng đƣợc phát triển. BALSA- I cĩ một hệ thống đi sau đĩ là BALSA-II [Brown 1988]. BALSA-II là một hệ thống mơ phỏng thuật tốn vùng-độc lập thao tác các ảnh với nhiều cái nhìn và cung cấp quá trình tạo ra bộ điều khiển dễ dàng. TANGO thì khác, cĩ nhiều hệ thống đi sau. XTANGO [Stasko 1992] là hệ thống trực tiếp đi sau TANGO. POLKA đƣợc thiết kế để xây dựng mơ phỏng đồng thời cho các chƣơng trình song song. Nĩ là một hệ thống mơ phỏng thuật tốn hƣớng đối tƣợng 2-D và đƣợc mở rộng thành hệ thống 3-D, POLKA 3-D. POLKA 3-D cung cấp cái nhìn 3-D và 3-D nguyên thủy, ví dụ nhƣ: hình nĩn, hình cầu, hình lập phƣơng và một số hình khác nữa. Ngƣời dùng khơng bị yêu cầu phải cĩ hiểu biết trƣớc về đồ họa máy tính 3-D để sử dụng POLKA 3-D. Samba cho phép thể hiện mơ phỏng tƣơng tác mà đọc các câu lệnh ASCII và thực hiện các hành động mơ phỏng tƣơng ứng. Cĩ một phiên bản Java của Samba đƣợc gọi là JSamba (xem samba.html). Các hệ thống mơ phỏng thuật tốn khác bao gồm: Zeus, Leonardo, CATAI, Mocha. Zeus [Brown 1991] đƣợc phát triển tại trƣờng đại học Brown cùng với BALSA và BALSA-II, nĩ đƣợc coi nhƣ một trong số các hệ thống phần mềm cĩ ảnh hƣởng lớn đến nhau đầu tiên. Zeus đƣợc thực thi trong mơi trƣờng multi-threaded và multi-processor, vì thế nĩ cĩ thể làm cho các chƣơng trình song song. CATAI (xem Sinh viên thực hiện:Nguyễn Hải Nam 12
13. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp là một hệ thống mơ phỏng các chƣơng trình C++. Nĩ tin tƣởng vào những cơng nghệ đối tƣợng phân tán và cho phép một vài ngƣời dùng chia sẻ mơ phỏng đĩ thơng qua sự trừu tƣợng hĩa lớp học thực tế. Truyền thơng và sự đồng bộ hĩa giữa các khách hàng mơ phỏng và thuật tốn đƣợc mơ phỏng đƣợc đảm bảo bởi ngƣời phục vụ mơ phỏng Java mà sử dụng cơng nghệ CORBA. Mocha (xem là một mơ hình phân tán với kiến trúc client-server nhằm tối ƣu phân chia những thành phần của phần mềm trong một hệ thống mơ phỏng thuật tốn tiêu biểu. Trong mơ hình Mocha, chỉ mã giao diện đƣợc xuất tới máy ngƣời dùng, trong khi thuật tốn đƣợc thực hiện trên một server chạy trên máy của nhà cung cấp. Với việc phát triển của cơng nghệ mới, tính phổ dụng của mạng tồn cầu và sự tiến hĩa của ngơn ngữ lập trình Java, những ngƣời phát triển đã xây dựng những hệ thống mơ phỏng thuật tốn trực tuyến, cĩ lợi thế của những hệ thống mở dễ tiếp cận hơn. Một số nhà phát triển cũng hợp nhất việc sử dụng đa phƣơng tiện trong các hệ thống của họ. Việc sử dụng các hệ thống mơ phỏng thuật tốn khơng cịn bị bĩ hẹp trong các lớp học truyền thống hoặc phịng thí nghiệm giảng dạy nữa mà đã đƣợc mở rộng để dạy từ xa. Trong khoảng hai thập niên gần đây, một số rất lớn các hệ thống mơ phỏng thuật tốn đã ra đời và phát triển mạnh mẽ. Phần lớn các hệ thống mơ phỏng thuật tốn đã đề cập trong mục này đều phổ biến hơn và phức tạp hơn các hệ thống đang đƣợc sử dụng trong thực tế. Chúng đã đƣợc phát triển và sử dụng bởi những nhà chuyên mơn, với mục đích giáo dục hoặc nghiên cứu thực nghiệm của họ. Một trong số các hệ thống này cĩ một kiến trúc phức tạp và cần những cơng nghệ đặc biệt để chạy nĩ. Chúng ta khơng cĩ bất kỳ Sinh viên thực hiện:Nguyễn Hải Nam 13
14. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp tiện ích nào của các hệ thống này để xây dựng hệ thống mơ phỏng các thuật tốn đồ thị; thay vào đĩ, chúng ta đã ƣớc lƣợng đƣợc các hệ thống mơ phỏng hiện hữu khác mà kích thƣớc nhỏ hơn và cĩ những kiến trúc đơn giản hơn. 2.1.3. Tác dụng của mơ phỏng thuật tốn Các hệ thống mơ phỏng thuật tốn đƣợc sử dụng rộng rãi nhƣ cơng cụ hỗ trợ giảng dạy trong ngành giáo dục khoa học máy tính. Một số nghiên cứu thực nghiệm đã ƣớc lƣợng hiệu quả của chúng trong giáo dục và kết quả nhận đƣợc cĩ thay đổi. Cụ thể là: Brown (1984) đã sử dụng BALSA-I để dạy một khĩa giới thiệu lập trình và một khĩa “ cấu trúc dữ liệu và giải thuật”. Hệ thống đƣợc sử dụng nhƣ một chƣơng trình trực quan trong khĩa giới thiệu, và nhƣ một ngƣời mơ phỏng thuật tốn mức cao trong lớp cấu trúc dữ liệu. Ơng ta báo cáo rằng việc sử dụng các hoạt cảnh mơ phỏng để phụ thêm vào thuyết trình dẫn tới „những lợi ích cĩ thể chứng minh được trong việc tăng tốc độ hiểu biết‟ qua thuyết trình truyền thống. Stasko (1997) đã sử dụng Samba, chƣơng trình mơ phỏng của hệ thống XTango dạy một khĩa thuật tốn khoa học máy tính. Những sinh viên đƣợc yêu cầu sử dụng hệ thống cĩ thêm vào mơ phỏng cho các chƣơng trình ấn định của họ. Các kết quả thu đƣợc cho biết rằng những sinh viên thích các mơ phỏng và những mơ phỏng đĩ cĩ thể làm tăng tính sáng tạo của các sinh viên. Hơn nữa, sự hiểu biết của sinh viên về thuật tốn đƣợc tăng lên nhờ việc mơ phỏng. Tuy nhiên, sử dụng thuật tốn trong việc dạy học khơng phải lúc nào cũng thành cơng. Các nhà giáo dục đã làm các thực nghiệm và thu đƣợc các kết quả pha trộn. Stasko et al. (1993) đã chỉ ra một thí nghiệm bằng việc dạy hai nhĩm sinh viên với hai cách thuyết trình khác nhau. Cả hai nhĩm sinh viên này cùng nghiên cứu thuật tốn “ Pairing heap” (ghép đơi đống). Một Sinh viên thực hiện:Nguyễn Hải Nam 14
15. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp nhĩm học thuật tốn dựa vào sự mơ tả văn bản và nhĩm kia cũng nhận các tài liệu đĩ nhƣng cĩ thêm sự trợ giúp bằng các chƣơng trình mơ phỏng thuật tốn. Mặc dầu những kết quả chỉ ra rằng nhĩm thứ hai đạt đƣợc nhiều điểm hơn nhĩm kia, nhƣng khơng cĩ điểm nổi trội nào cĩ thể đƣợc kết luận là nhờ sự trợ giúp của mơ phỏng. Tƣơng tự, Byrne et al. (1996) đã chủ đạo hai thí nghiệm mà trong đĩ các kết quả chỉ ra rằng lợi ích của mơ phỏng khơng phải là hiển nhiên. Những kết quả pha trộn này đã gây ra chán nản, nhƣng đa số các nhà giáo dục đều tin tƣởng rằng mơ phỏng hỗ trợ việc học. Tuy nhiên, những kết quả thí nghiệm bất lợi này gợi ý những yếu tố quan trọng khác trong việc sử dụng mơ phỏng thuật tốn. Các kết quả đã thơng báo rằng để đạt đƣợc hiệu quả mơ phỏng thuật tốn đầy đủ thì điều quan trọng là mơ phỏng đƣợc sử dụng phối hợp với những yếu tố khác. Lawrence et al. (1994) đã sử dụng các hệ thống XTANGO và POLKA để dạy thuật tốn cây khung nhỏ nhất Kruskal. Trong số nhĩm sinh viên tham dự các thí nghiệm, kết quả của những sinh viên mà tham dự một phiên thí nghiệm tƣơng tác tốt hơn đáng kể so với những sinh viên mà tham dự những phiên thí nghiệm bị động. Các kết quả này đã cho phép các sinh viên điều khiển và tƣơng tác với mơ phỏng tốt hơn, chẳng hạn, chƣơng trình mơ phỏng cho phép sinh viên đƣa vào tập dữ liệu của chính họ và thực hiện mơ phỏng trên tập dữ liệu này chứ khơng chỉ dừng lại ở việc quan sát những tập dữ liệu mẫu. Hơn nữa, nhiều nghiên cứu gần đây bởi Kehoe et al. (1999) cho thấy cĩ thể sử dụng mơ phỏng nhƣ một cơng cụ giáo dục. Thí nghiệm đƣợc thực hiện trong một thái độ khác từ các thí nghiệm khác. Những sinh viên đƣợc chia thành hai nhĩm và cả hai nhĩm đều học thuật tốn „binomial heap” Sinh viên thực hiện:Nguyễn Hải Nam 15
16. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp (đống nhị thức). Một nhĩm học thuật tốn bởi sự tƣơng tác với mơ phỏng trong khi nhĩm cịn lại là đọc những hình dạng phẳng về các điểm khĩa thao tác của thuật tốn. Sự khác nhau trong thí nghiệm này là kịch bản bài tập về nhà. Những sinh viên đƣợc đƣa cho những câu hỏi trƣớc khi bắt đầu khĩa học. Trong suốt thời gian kiểm tra thử, những sinh viên cĩ thể truy cập tới bài dạy và thời gian để hồn thành bài kiểm tra thử này đƣợc cho tƣơng đối nhiều. Các kết quả của thí nghiệm này cho thấy nhĩm đƣợc trang bị chƣơng trình mơ phỏng thuật tốn thực hiện bài kiểm tra thử tốt hơn nhĩm kia. Các sinh viên của nhĩm cĩ sử dụng mơ phỏng thuật tốn phản hồi rằng mơ phỏng đã giúp đỡ họ hiểu thuật tốn tốt hơn. Báo cáo của Kehoe et al (1999) đã trình diễn một cách sử dụng mơ phỏng thuật tốn trong việc dạy để đạt đƣợc giá trị sƣ phạm cao hơn. Nĩ đã đƣợc thuyết trình rằng mơ phỏng thuật tốn đƣợc sử dụng tốt hơn trong các tình trạng học tƣơng tác và mơ phỏng (nhƣ một bài tập về nhà). Cũng nhƣ vậy, mơ phỏng thuật tốn cĩ thể cĩ tính sƣ phạm hơn khi nĩ đƣợc sử dụng trong việc phối hợp với các cách học khác hoặc giúp đỡ những chỉ dẫn khác để giải thích làm thế nào thực hiện một thao tác của thuật tốn. Báo cáo cũng nĩi rằng với mơ phỏng thuật tốn ngƣời ta cĩ thể dễ dàng học các thao tác theo thủ tục của các thuật tốn. Ngồi ra nĩ cĩ thể làm cho việc học một thuật tốn bớt đáng sợ hơn vì nĩ làm cho thuật tốn dễ tiếp cận hơn. Stasko et al. (1993) đã kết luận từ thí nghiệm của họ một số điều kiện mà mơ phỏng thuật tốn cĩ thể cĩ lợi nhất. Một trong số những điều kiện này là hỗ trợ mơ phỏng thuật tốn với những chỉ dẫn thúc đẩy tồn diện. Khi mơ phỏng thuật tốn đĩng vai trị chỉ dẫn này, màn hình mơ phỏng phải đƣợc bổ sung bởi các mơ tả văn bản của các thao tác đang diễn ra. Một điều kiện khác đĩ là hệ thống mơ phỏng thuật tốn cần phải bao gồm các chức Sinh viên thực hiện:Nguyễn Hải Nam 16
17. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp năng: quay lại hoặc lặp lại những bƣớc thực hiện thuật tốn để cho phép những ngƣời dùng sao lƣu và xem lại những thao tác quan trọng. Một số bài giảng địi hỏi các trạng thái thực hiện thuật tốn cũng cần phải đƣợc ghi lại và cung cấp lại đƣợc. Sự phản hồi của sinh viên cũng là quý giá trong việc cải thiện chất lƣợng chỉ dẫn của mơ phỏng. Mặc dù những kết quả đƣợc đƣa ra từ những nghiên cứu thực nghiệm này khơng phải luơn cĩ lợi, thì cũng khơng cĩ nghĩa rằng mơ phỏng thuật tốn khơng hiệu quả trong dạy học. Hiện nay đang cĩ nhiều nghiên cứu đang đƣợc tiến hành về thiết kế và đánh giá mơ phỏng thuật tốn. Hansen et al. (1999) tin rằng các kết quả trong các nghiên cứu thực nghiệm trên chƣa tốt khơng phải vì mơ phỏng thuật tốn là phƣơng pháp dạy học khơng tốt, mà vì cách thức thực hiện các mơ phỏng chƣa tốt. Họ đã phát triển một hệ thống trực quan hĩa giải thuật siêu phƣơng tiện gọi là HalVis (Hypermedia Algorithm Visualizations). Dựa vào framework của chúng, họ đã thiết kế các trực quan hĩa giải thuật, và họ đã hƣớng dẫn vài thí nghiệm thực nghiệm bởi việc sử dụng hệ thống này. Tất cả các kết quả thí nghiệm cho thấy trực quan hĩa giải thuật bằng đồ họa cĩ hiệu quả hơn so với các phƣơng pháp dạy truyền thống. Những kết quả này cho thấy rằng để mơ phỏng thuật tốn cĩ hiệu quả và cĩ lợi cho ngƣời dùng, thì việc thiết kế cho thích hợp và cách thức mơ phỏng là những yếu tố quan trọng. Để mơ phỏng thuật tốn cĩ hiệu quả thì hệ thống mơ phỏng cần phải đáp ứng những điều sau :  Truy cập mở (Open access): Ngƣời dùng cĩ thể truy cập hệ thống mơ phỏng mở. Hơn nữa, nếu cĩ cài đặt hệ thống mơ phỏng trong trƣờng học, thì họ cĩ thể truy cập tới hệ thống này từ nhà hoặc từ bất cứ nơi nào khác. Sinh viên thực hiện:Nguyễn Hải Nam 17
18. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp  Mơ phỏng một cách cĩ điều khiển (Control animation): Ngƣời dùng cĩ thể tự tạo tập dữ liệu của chính mình khi sử dụng hệ thống mơ phỏng. Trong khi các tập dữ liệu đƣợc cài đặt sẵn cũng cĩ thể giúp đỡ sinh viên cĩ những sự hiểu biết ban đầu, hệ thống nên cĩ cả 2 tùy chọn này.  Tương tác (Ineractivity): Hệ thống mơ phỏng phải cung cấp đƣợc sự tƣơng tác giữa ngƣời dùng và hệ thống. Sự tƣơng tác bao gồm: ngƣời dùng xem theo từng bƣớc, hủy, chạy nhanh tới một bƣớc mong muốn, hay xem lại từ đầu,  Lịch sử (History): Hệ thống mơ phỏng cho phép ngƣời dùng xem lại các bƣớc trƣớc trong quá trình thực hiện.  Phản hồi (Feedback): Phải tiếp thu phản hồi của sinh viên về việc sử dụng hệ thống mơ phỏng để ƣớc lƣợng hiệu quả của hệ thống cũng nhƣ để cải thiện hệ thống. 2.1.4. Kiến trúc của hệ thống mơ phỏng thuật tốn Đa số các hệ thống mơ phỏng thuật tốn cĩ những thƣ viện hỗ trợ thủ tục mơ phỏng và giao diện mơ phỏng. Vài hệ thống mơ phỏng địi hỏi phải đƣa vào trực tiếp bằng tay những thơng điệp gửi tới các thủ tục mơ phỏng trong chƣơng trình thực hiện thuật tốn. Những hệ thống mơ phỏng thuật tốn ra đời sớm nhƣ: BALSA and TAGO là sự kiện – điều khiển (event- driven), nghĩa là chúng cĩ một chƣơng trình phát sinh những sự kiện trong dạng những thơng điệp tới một máy chủ thơng điệp. Máy chủ thơng điệp chuyển thơng điệp tới những cảnh quan tƣơng ứng. Một cảnh quan là một cửa sổ trong một thiết bị màn hình nơi ngƣời dùng nhìn những đối tƣợng mơ phỏng. Thơng điệp bao gồm thơng tin của một đối tƣợng mơ phỏng. Sau khi Sinh viên thực hiện:Nguyễn Hải Nam 18
19. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp cảnh quan nhận thơng điệp, nĩ tính tốn lại đối tƣợng và kéo lại nĩ trên cảnh quan. Vài hệ thống gần đây đƣợc viết bằng Java và tất cả đều cĩ những kiến trúc tƣơng tự nhau. Ví dụ nhƣ: JSamba, hệ thống POLKA tiền tiêu (xem gatech.due/gvu/softviz/parviz/samba.html) và JAWAA (Java và mơ phỏng thuật tốn trên mạng, xem phát triển bởi Pierson và Rodger tại trƣờng đại học Duke vào năm 1996. Những hệ thống này chấp nhận framework của TANGO nhƣ kiến trúc của nĩ. Tất cả các hệ thống sẽ gồm cĩ 3 thành phần, các hàm mơ phỏng (animator), kênh mơ phỏng (animation interpreter) và trình diễn mơ phỏng (animation viewer) nhƣ đã chỉ ra trong sơ đồ sau: File Kênh mơ Các hàm Màn hình kịch bản phỏng mơ phỏng trình diễn mơ ASCII phỏng Hình 1. Kiến trúc của hệ thống mơ phỏng thuật tốn - Các hàm mơ phỏng: Chứa các thƣ viện để vẽ các đối tƣợng mơ phỏng trên thiết bị màn hình. - Màn hình trình diễn mơ phỏng: Cung cấp một mơi trƣờng đồ họa để trình diễn mơ phỏng trên thiết bị màn hình tới ngƣời dùng cuối. - Kênh mơ phỏng: Đĩng vai trị nhƣ một kênh truyền thơng giữa hệ thống mơ phỏng và ngƣời dùng cuối. Nĩ đọc một file kịch bản ASCII đƣợc cung cấp bởi ngƣời dùng cuối mà trong đĩ cĩ chứa mơ phỏng văn bản cung cấp việc phát sinh những lệnh. Sinh viên thực hiện:Nguyễn Hải Nam 19
20. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp - Kênh mơ phỏng dịch các lệnh kịch bản thành các lệnh mơ phỏng tƣơng ứng và chuyển qua những tham số điều khiển của đối tƣợng mơ phỏng tới các hàm mơ phỏng. - Các hàm mơ phỏng vẽ đối tƣợng đƣợc mơ phỏng theo các tham số điều khiển của đối tƣợng đĩ tới Animation viewer. - Các tham số điều khiển bao gồm tọa độ x và y chỉ rõ nơi đối tƣợng đƣợc mơ phỏng xuất hiện trong Animation viewer hoặc màu sắc của đối tƣợng đƣợc mơ phỏng. 2.1.5. Lựa chọn cơng cụ mơ phỏng thuật tốn Trong mục này, chúng ta sẽ phân tích cách tiếp cận khác để xây dựng hệ thống mơ phỏng và tính khả thi của chúng. Chúng ta cũng sẽ ƣớc lƣợng một vài cơng cụ mơ phỏng thuật tốn thích hợp để xây dựng hệ thống mơ phỏng thuật tốn. Cơng cụ thích hợp nhất sẽ đƣợc lựa chọn và các căn chỉnh trên sự lựa chọn này sẽ đƣợc cung cấp. Cĩ ba cách tiếp cận cĩ thể để xây dựng hệ thống mơ phỏng phân tách. Cách tiếp cận đầu tiên sẽ xây dựng hệ thống từ đầu nhờ việc sử dụng ngơn ngữ C#. Cách tiếp cận thứ hai sẽ lựa chọn hệ thống mơ phỏng thuật tốn cĩ mục đích chung thích hợp để xây dựng các thành phần tƣơng tác của hệ thống phân tách từ đầu. Cách tiếp cận cuối cùng là lựa chọn một hệ thống mơ phỏng thuật tốn phân tách đã tồn tại và sửa đổi hệ thống đĩ thành hệ thống cuối cùng. Sinh viên thực hiện:Nguyễn Hải Nam 20
21. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp 2.2. Một số yêu cầu đối với mơ phỏng thuật tốn 2.2.1. Mơ tả đúng theo thuật tốn Thuật tốn đƣợc đƣa ra mơ phỏng phải chính xác, các bƣớc thực hiện thuật tốn phải trực quan và phản ánh đúng theo nội dung thuật tốn đã đƣa ra để đảm bảo tính đúng đắn của thuật tốn. Để kiểm tra tính đúng đắn của thuật tốn, ta cĩ thể cài đặt giải thuật đĩ trên máy tính rồi đƣa vào các bộ dữ liệu xác định, lấy kết quả thu đƣợc xác định với kết quả đã biết. Bộ dữ liệu đƣa vào phải đảm bảo kết quả thu đƣợc phải vét kín các trƣờng hợp nghiệm của bài tốn (trƣờng hợp thơng thƣờng và các trƣờng hợp đặc biệt). Làm theo cách này thì khơng chắc chắn, ta chỉ phát hiện đƣợc thuật tốn sai chứ khơng khẳng định đƣợc luơn đúng. Tính đúng đắn chỉ cĩ thể khẳng định bằng phƣơng pháp chứng minh tốn học. 2.2.2. Hệ thống mơ phỏng phải đƣợc thực hiện theo từng bƣớc Thuật tốn thƣờng là trìu tƣợng, nếu để chƣơng trình chạy tự động thì ngƣời dùng sẽ khĩ hiểu. Vì vậy, cần phải cĩ chế độ thực hiện mơ phỏng thuật tốn theo từng bƣớc, để ngƣời học cĩ thể quan sát, theo dõi sự thay đổi giá trị của từng biến. Nhờ đĩ, sẽ giúp cho ngƣời học hiểu thuật tốn rõ hơn và nhanh hơn. 2.2.3. Mơ phỏng thuật tốn phải cĩ tính động Để mơ tả trực quan hĩa quá trình thực hiện của thuật tốn ta nên đƣa vào hình ảnh động (cĩ thể cĩ âm thanh) để thể hiện sự thay đổi của dữ liệu trong quá trình thực thi. Thuật tốn phải đƣợc thử nghiệm trong mọi trƣờng hợp để đảm bảo thời gian thực thi tốt nhất Sinh viên thực hiện:Nguyễn Hải Nam 21
22. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp Một thuật tốn đƣợc mơ phỏng phải đảm bảo là thuật tốn tốt, dễ hiểu và đúng đắn. Muốn vậy ta phải thử nghiệm trong các trƣờng hợp dữ liệu ngẫu nhiên, tốt nhất, xấu nhất. Nếu thuật tốn vẫn chạy tốt và trong một thời gian cho phép thì thuật tốn mới hiệu quả. Ta khơng thể chấp nhận một thuật tốn đúng mà thời gian chạy quá lớn. 2.2.4. Phải tạo ra sự phân cấp cho ngƣời học Đối tƣợng học thuật tốn thƣờng là các sinh viên. Họ cĩ trình độ tiếp thu khác nhau, nên ta phải đƣa ra nhiều chế độ thao tác khác nhau để ngƣời học đƣợc phép lựa chọn. 2.2.5. Cấu trúc của mơ phỏng thuật tốn INPUT ALGORITHM OUTPUT - Dữ liệu mẫu Cấu trúc dữ liệu trừu tƣợng - Dữ liệu trực tiếp - Tự động - Từng bƣớc Biểu diễn bằng demo Độ phức tạp của thuật tốn Hình 2. Cấu trúc của mơ phỏng thuật tốn Sinh viên thực hiện:Nguyễn Hải Nam 22
23. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp 2.3. Quy trình thiết kế nhiệm vụ mơ phỏng thuật tốn Nghiên cứu và Xây dựng mơ hình Cơ chế sinh dữ liệu phân tích giải thuật mơ phỏng Input, vào Output Những khĩ khăn Tổng hợp các bƣớc Phân tích giải thuật thuận lợi khi tiếp thành giải thuật thành nhiều bƣớc thu giải thuật Hình 3. Sơ đồ quy trình thiết kế nhiệm vụ mơ phỏng thuật tốn 2.3.1. Nghiên cứu và phân tích giải thuật Trƣớc khi lập trình cho máy tính giải một bài tốn, điều đầu tiên là chúng ta phải đi xác định bài tốn, để từ đĩ xây dựng giải thuật cho bài tốn. Một bài tốn đƣa ra cĩ thể cĩ nhiều hơn một giải thuật, vấn đề là ta phải đi đánh giá các giải thuật đĩ để lựa chọn ra một giải thuật tốt nhất. Vậy nhƣ thế nào là một giải thuật tốt? Để làm đƣợc điều này ta cĩ thể căn cứ vào các tiêu chuẩn sau:  Giải thuật đƣa ra phải đúng đắn  Giải thuật phải đơn giản (dễ hiểu)  Giải thuật phải thực hiện nhanh (độ phức tạp của thuật tốn phải thấp) Khi đƣa ra một giải thuật, điều đầu tiên chúng ta quan tâm đến đĩ là tính đúng đắn của giải thuật đĩ. Để biết giải thuật mình đƣa ra cĩ đúng đắn hay chƣa ta cĩ thể cài đặt giải thuật bằng một ngơn ngữ lập trình cụ thể và cho thực hiện trên máy với bộ dữ liệu mẫu, lấy kết quả thu đƣợc so sánh với kết quả đã biết. Cách làm này nĩi chung là chƣa chắc chắn, vì kết quả cĩ thể đúng với bộ dữ liệu mẫu, nhƣng với bộ dữ liệu khác thì chƣa khẳng định là đúng đƣợc. Mặt khác, cách làm này thực tế chỉ phát hiện ra giải thuật sai chứ Sinh viên thực hiện:Nguyễn Hải Nam 23
24. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp khơng kết luận đƣợc là giải thuật đúng. Tính đúng đắn của giải thuật cần phải đƣợc chứng minh bằng tốn học. Nhƣng điều này khơng hề đơn giản. Vì vậy, chúng ta cĩ thể kiểm tra tính đúng đắn của giải thuật bằng cách kiểm tra với các bộ dữ liễu mẫu, sao cho các bộ dữ liệu này phải phủ kín các trƣờng hợp nghiệm cĩ thể của bài tốn. Sau khi xây dựng giải thuật của bài tốn xong. Khâu tiếp theo là chúng ta tiến hành cài đặt giải thuật của bài tốn bằng một ngơn ngữ lập trình nào đĩ. Nếu bài tốn với dữ liệu nhỏ, khơng quan tâm đến thời gian chạy chƣơng trình (tức là thuật tốn chỉ đƣợc sử dụng một vài lần) thì giải thuật sẽ tốt hơn nếu việc cài đặt nĩ là dễ dàng và ngƣời dùng dễ hiểu. Tuy nhiên, giải thuật cho một bài tốn sau khi đƣợc cài đặt thƣờng xử lý với dữ liệu lớn và đƣợc sử dụng nhiều lần trong chƣơng trình. Vì thế khi xây dựng một giải thuật, ngƣời lập trình thƣờng quan tâm đến độ phức tạp của thuật tốn (thƣờng là độ phức tạp về thời gian mà đã đƣợc đề cập rất kỹ ở mục 1.3). Điều này dẫn đến việc giải thuật đƣợc xây dựng phải cĩ tính hiệu quả về thời gian thực hiện chƣơng trình. Các phương pháp diễn tả giải thuật - Phƣơng pháp liệt kê từng bƣớc (sử dụng ngơn ngữ tự nhiên) - Giả mã và ngơn ngữ lập trình thân thiện với ngƣời dùng (ví dụ nhƣ: PASCAL) - Dùng sơ đồ khối Hiện nay, trong ba phƣơng pháp trên thì việc dùng giả mã và một ngơn ngữ lập trình thân thiện với ngƣời dùng để diễn tả một giải thuật đƣợc đề cập đến nhiều hơn cả; đƣợc sử dụng trong dạy học cấu trúc dữ liệu và giải thuật mà rất nhiều tài liệu đã đƣa ra. Sinh viên thực hiện:Nguyễn Hải Nam 24
25. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp Phân tích các trường hợp đặc biệt của dữ liệu đầu vào, các giá trị của biến điều khiển lúc thốt khỏi vịng lặp. Các giá trị của biến lúc thốt khỏi vịng lặp thƣờng là một dấu hiệu đặc biệt để thốt khỏi vịng lặp. Dữ liệu đầu vào thƣờng gồm nhiều bộ dữ liệu khác nhau về giá trị, tuy nhiên trong số đĩ phải cĩ một số bộ dữ liệu đặc biệt. Những bộ dữ liệu đĩ đặc biệt về giá trị dữ liệu đầu vào hoặc đặc biệt về kết quả trả ra. Bộ dữ liệu đầu vào đặc biệt giúp ta khơng cần chạy thử chƣơng trình cũng cĩ thể biết kết quả thu đƣợc. Vì vậy, những bộ dữ liệu đặc biệt thƣờng đƣợc dùng làm giá trị kiểm thử để đánh giá thuật tốn đúng hay sai, hoặc đánh giá chƣơng trình đƣợc viết để chạy trên máy tính cĩ đúng với thuật tốn đƣa ra hay khơng? Phân tích đánh giá các lỗi cĩ thể mắc phải khi viết chương trình thực thi giải thuật Bài tốn sau khi đƣợc xác định và dựa trên ý tƣởng ta sẽ xây dựng đƣợc giải thuật của bài tốn đĩ. Sau đĩ tiến hành cài đặt thuật tốn này bằng một ngơn ngữ lập trình cụ thể ở một mơi trƣờng lập trình trên máy tính để máy thực hiện tự động giải thuật cho ta kết quả của bài tốn. Một bài tốn cĩ thể đƣợc viết bằng nhiều ngơn ngữ lập trình. Vì vậy giải thuật phải đƣợc viết sao cho mọi lập trình viên của các ngơn ngữ lập trình đều cĩ thể hiểu đƣợc và dễ dàng chuyển từ giải thuật sang cài đặt bằng ngơn ngữ lập trình mà họ thơng thạo. Vì thế, khi viết giải thuật cho một bài tốn, nên viết bằng ngơn ngữ tự nhiên, gần gũi, dễ hiểu và ít gị bĩ. Tuy nhiên, việc sử dụng một ngơn ngữ lập trình bậc cao để cài đặt giải thuật thƣờng gặp phải một số vấn đề: - Phải tuân thủ chặt chẽ các quy tắc về cú pháp Sinh viên thực hiện:Nguyễn Hải Nam 25
26. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp - Phụ thuộc vào cấu trúc dữ liệu mặc định của ngơn ngữ Ngơn ngữ tự nhiên thƣờng rất đa nghĩa, nên việc chuyển từ ngơn ngữ tự nhiên sang ngơn ngữ lập trình cũng dễ mắc phải lỗi bởi vì câu lệnh đƣợc chuyển khơng đúng với nghĩa thực của nĩ. Chính vì vậy mà ta cĩ thể sử dụng giả mã để viết giải thuật. Vì giả mã dùng ngơn ngữ tựa Pascal – một ngơn ngữ lập trình bậc cao thân thuộc với hầu hết ngƣời dùng để viết giải thuật cho một bài tốn. Phân tích sự giống nhau và khác nhau của các giải thuật tương tự Một bài tốn khi đƣa ra cĩ thể cĩ nhiều giải thuật, tuy nhiên trong số những giải thuật đĩ ta cần lựa chọn ra một giải thuật để làm việc. Câu hỏi đặt ra ở đây là nên chọn giải thuật nào trong số các giải thuật đĩ? Muốn vậy ta phải đánh giá xem giải thuật nào là đơn giản, thời gian thực hiện nhanh, tốn ít bộ nhớ, tối ƣu, nhằm lựa chọn ra giải thuật tốt nhất để giải bài tốn sao cho dễ mơ phỏng. 2.3.2. Phân tích giải thuật thành nhiều bƣớc, sau đĩ lần lƣợt mơ phỏng từng bƣớc đĩ Việc phân chia giải thuật ra làm các modul, mỗi modul thực hiện một cơng việc khác nhau rất cĩ ý nghĩa trong việc tinh chỉnh giải thuật. Phân tích giải thuật ra thành nhiều bƣớc khác nhau và tiến hành mơ phỏng từng bƣớc của giải thuật đĩ giúp ngƣời dùng dễ theo dõi giải thuật hơn. Từ đĩ cĩ thể hiểu đƣợc cơ chế hoạt động của chƣơng trình. Sinh viên thực hiện:Nguyễn Hải Nam 26
27. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp Dựa trên các bƣớc của giải thuật đƣợc phân tích, ta xây dựng các đoạn code mơ phỏng từng bƣớc của thuật tốn. Nhờ đĩ ngƣời dùng dễ dàng hiểu thuật tốn hơn. 2.3.3. Phân tích khả năng tổng hợp các bƣớc đã phân tích thành giải thuật Với mỗi thuật tốn, khi đã phân tích thành các bƣớc, vấn đề cịn lại là tổng hợp chúng lại thành giải thuật của bài tốn. Điều này khơng cĩ gì khĩ khăn, ta chỉ việc cài đặt lại giải thuật đĩ bằng một ngơn ngữ lập trình cụ thể (Java chẳng hạn) rồi thiết kế, chỉnh sửa để thực hiện mơ phỏng thuật tốn đĩ là tốt nhất cĩ thể. 2.3.4. Phân tích những khĩ khăn và thuận lợi với những ngƣời lần đầu tiên biết đến giải thuật Khi ngƣời học lần đầu tiên tiếp thu giải thuật mới sẽ gặp những thuận lợi và khĩ khăn sau: - Khĩ khăn: Đối với mơn học cấu trúc dữ liệu và giải thuật, cĩ rất nhiều giải thuật phức tạp, trừu tƣợng, khĩ hiểu và khĩ hình dung. Vì vậy, để nắm đƣợc giải thuật này thật chắc khơng phải là điều đơn giản với ngƣời học. - Thuận lợi: Khi học những giải thuật bằng phƣơng pháp truyền thống, tức là chỉ bằng lý thuyết sẽ làm cho ngƣời học cảm thấy rất mơ hồ về giải thuật đĩ. Chính vì lẽ đĩ, nếu ta sử dụng mơ phỏng với một bên là hình vẽ và một bên cho phép hiển thị giả mã của giải thuật thì ngƣời dùng cĩ thể vừa theo dõi thuật tốn, vừa cĩ thể „nhìn thấy‟ cách mà thuật tốn thực hiện trên một hình cụ thể. Từ đĩ ngƣời dùng hiểu thuật tốn dễ hơn và sâu sắc hơn. Sinh viên thực hiện:Nguyễn Hải Nam 27
28. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp 2.4. Kết luận Thơng qua việc giới thiệu một cách tổng quan nhất về mơ phỏng thuật tốn, ta đã thấy đƣợc tác dụng to lớn của mơ phỏng thuật tốn trong giáo dục. Trên cơ sở đĩ, ta cũng đã hiểu đƣợc kiến trúc của một hệ thống mơ phỏng thuật tốn. Từ đĩ đƣa ra một số cơng cụ cho phép xây dựng một hệ thống mơ phỏng thuật tốn bằng cách lựa chọn một cơng cụ thích hợp nhất. Sau khi đã cĩ cơng cụ lập trình, ta tiến hành xây dựng một quy trình thiết kế hệ thống mơ phỏng thuật tốn nhằm đáp ứng nhu cầu ngƣời dùng. Sinh viên thực hiện:Nguyễn Hải Nam 28
29. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp CHƢƠNG 3 : CHƢƠNG TRÌNH ỨNG DỤNG THUẬT TỐN SẮP XẾP Sắp xếp là một quá trình biến đổi một danh sách các đối tƣợng thành một danh sách thoả mãn một thứ tự xác định nào đĩ. Sắp xếp đĩng vai trị quan trọng trong tìm kiếm dữ liệu. Chẳng hạn, nếu danh sách đã đƣợc sắp xếp theo thứ tự tăng dần (hoặc giảm dần), ta cĩ thể sử dụng kỹ thuật tìm kiếm nhị phân hiệu quả hơn nhiều tìm kiếm tuần tự Trong thiết kế thuật tốn, ta cũng thƣờng xuyên cần đến sắp xếp, nhiều thuật tốn đƣợc thiết kế dựa trên ý tƣởng xử lý các đối tƣợng theo một thứ tự xác định. Các thuật tốn sắp xếp đƣợc chia làm 2 loại: sắp xếp trong và sắp xếp ngồi. Sắp xếp trong đƣợc thực hiện khi mà các đối tƣợng cần sắp xếp đƣợc lƣu ở bộ nhớ trong của máy tính dƣới dạng mảng. Do đĩ sắp xếp trong cịn đƣợc gọi là sắp xếp mảng. Khi các đối tƣợng cần sắp xếp quá lớn cần lƣu ở bộ nhớ ngồi dƣới dạng file, ta cần sử dụng các phƣơng pháp sắp xếp ngồi, hay cịn gọi là sắp xếp file. Trong chƣơng này, chúng ta trình bày các thuật tốn sắp xếp đơn giản, các thuật tốn này dịi hỏi thời gian O(n2) để sắp xếp mảng n đối tƣợng. Sau đĩ chúng ta đƣa ra các thuật tốn phức tạp và tinh vi hơn, nhƣng hiệu quả hơn, chỉ cần thời gian O(nlogn). Mảng cần đƣợc sắp xếp cĩ thể là mảng số nguyên, mảng các số thực, hoặc mảng các xâu ký tự. Trong trƣờng hợp tổng quát, các đối tƣợng cần đƣợc sắp xếp chứa một số thành phần dữ liệu, và ta cần sắp xếp mảng các đối tƣợng đĩ theo một thành phần dữ liệu nào đĩ. Thành phần dữ liệu đĩ đƣợc gọi là khố sắp xếp. Chẳng hạn, ta cĩ một mảng các đối tƣợng sinh viên, mỗi sinh viên gồm các thành phần dữ liệu: tên, tuổi, chiều cao, , và ta muốn sắp xếp các sinh viên theo thứ tự chiều cao tăng, khi đĩ chiều cao là khố sắp xếp. Từ đây về sau, ta giả thiết rằng, mảng cần đƣợc sắp xếp là mảng các đối tƣợng cĩ kiểu Item, trong đĩ Item là cấu trúc sau: struct Item Sinh viên thực hiện:Nguyễn Hải Nam 29
30. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp { keyType key; // Khố sắp xếp // Các trƣờng dữ liệu khác }; Vấn đề sắp xếp bây giờ đƣợc phát biểu chính xác nhƣ sau. Cho mảng A[0 n-1] chứa n Item, chúng ta cần sắp xếp lại các thành phần của mảng A sao cho: A[0].key <= A[1].key <= <= A[n-1].key 3.1 CÁC THUẬT TỐN SẮP XẾP ĐƠN GIẢN Mục này trình bày các thuật tốn sắp xếp đơn giản: sắp xếp lựa chọn (selection sort), sắp xếp xen vào (insertion sort), và sắp xếp nổi bọt (bubble sort). Thời gian chạy của các thuật tốn này là O(n2), trong đĩ n là cỡ của mảng. 3.1.1 Sắp xếp lựa chọn Ý tƣởng của phƣơng pháp sắp xếp lựa chọn là nhƣ sau: Ta tìm thành phần cĩ khĩa nhỏ nhất trên tồn mảng, giả sử đĩ là A[k]. Trao đổi A[0] với A[k]. Khi đĩ A[0] là thành phần cĩ khố nhỏ nhất trong mảng. Giả sử đến bƣớc thứ i ta đã cĩ A[0].key <= A[1].key <= <= A[i-1]. Bây giờ ta tìm thành phần cĩ khĩa nhỏ nhất trong các thành phần từ A[i] tới A[n-1]. Giả thành phần tìm đƣợc là A[k], i <= k <= n-1. Lại trao đổi A[i] với A[k], ta cĩ A[0].key <= <= A[i].key. Lặp lại cho tới khi i = n-1, ta cĩ mảng A đƣợc sắp xếp. Ví dụ. Xét mảng A[0 5] các số nguyên. Kết quả thực hiện các bƣớc đã mơ tả đƣợc cho trong bảng sau A[0] A[1] A[2] A[3] A[4] A[5] I k 5 9 1 8 3 7 0 2 1 9 5 8 3 7 1 4 1 3 5 8 9 7 2 2 Sinh viên thực hiện:Nguyễn Hải Nam 30
31. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp 1 3 5 8 9 7 3 5 1 3 5 7 9 8 4 5 1 3 5 7 8 9 Sau đây là hàm sắp xếp lựa chọn: void SelectionSort(Item A[] , int n) // Sắp xếp mảng A[0 n-1] với n > 0 { (1) for (int i = 0 ; i < n-1 ; i++) { (2) int k = i; (3) for (int j = i + 1 ; j < n ; j++) (4) if (A[j].key < A[k].key) k = j; (5) swap(A[i],A[k]); } } Trong hàm trên, swap là hàm thực hiện trao đổi giá trị của hai biến. Phân tích sắp xếp lựa chọn. Thân của lệnh lặp (1) là các lệnh (2), (3) và (5). Các lệnh (2) và (5) cĩ thời gian chạy là O(1). Ta đánh giá thời gian chạy của lệnh lặp (3). Số lần lặp là (n-1-i), thời gian thực hiện lệnh (4) là O(1), do đĩ thời gian chạy của lệnh (3) là (n-1-i)O(1). Nhƣ vậy, thân của lệnh lặp (1) cĩ thời gian chạy ở lần lặp thứ i là (n-1-i)O(1). Do đĩ lệnh lặp (1) địi hỏi thời gian n 2  (n-1-i)O(1) = O(1)(1 + 2 + + n-1) i 0 = O(1)n(n-1)/2 = O(n2) Vậy thời gian chạy của hàm sắp xếp lựa chọn là O(n2). Sinh viên thực hiện:Nguyễn Hải Nam 31
32. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp 3.1.2 Sắp xếp xen vào Phƣơng pháp sắp xếp xen vào là nhƣ sau. Giả sử đoạn đầu của mảng A[0 i-1] (với i >= 1) đã đƣợc sắp xếp, tức là ta đã cĩ A[0].key = A[0] nên ta dừng lại và cĩ đoạn đầu A[0 3] đã đƣợc sắp Hàm sắp xếp xen vào đƣợc viết nhƣ sau: void InsertionSort (Item A[], int n) { Sinh viên thực hiện:Nguyễn Hải Nam 32
33. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp (1) for ( int i = 1 ; i 0 ; k ) (3) if (A[k].key A[k+1].key thì ta trao đổi hai thành phần A[k] và A[k+1]. Làm nhƣ vậy ta đẩy đƣợc dữ liệu cĩ khố lớn nhất lên vị trí sau cùng A[n-1]. Ví dụ. Giả sử ta cĩ mảng số nguyên A[0 4]= (6,1,7,3,5).Kết quả thực hiện quá trình trên đƣợc cho trong bảng sau: A[0] A[1] A[2] A[3] A[4] 6 1 7 3 5 Trao đổi A[0] và A[1] 1 6 7 3 5 Trao đổi A[2] và A[3] 1 6 3 7 5 Trao đổi A[3] và A[4] 1 6 3 5 7 Lặp lại quá trình trên đối với mảng A[0, , n-2] để đẩy dữ liệu cĩ khố lớn nhất lên vị trí A[n-2]. Khi đĩ ta cĩ A[n-2].key ≤ A[n-1].key. Tiếp Sinh viên thực hiện:Nguyễn Hải Nam 33
34. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp tục lặp lại quá trình đã mơ tả trên các đoạn đầu A[0 i], với i = n-3, ,1, ta sẽ thu đƣợc mảng đƣợc sắp . Ta cĩ hàm sắp xếp nổi bọt nhƣ sau: void BubbleSort( Item A[] , int n) { (1) for (int i = n-1 ; i > 0 ; i ) (2) for (int k = 0 ; k A[k+1].key) Swap(A[k],A[k+1]); } Tƣơng tự nhƣ hàm sắp xếp xen vào ,ta cĩ thể đánh giá thời gian chạy của 2 hàm sắp xếp nổi bọt là O(n ). Trong hàm BubbleSort khi thực hiện lệnh lặp (1), nếu đến chỉ số i nào đĩ, n-1 ≥ i > 1, mà đoạn đầu A[0 i] đã đƣợc sắp, thì ta cĩ thể dừng. Do đĩ ta cĩ thể cải tiến hàm BubbleSort bằng cách đƣa vào biến sorted, biến này nhận giá trị true nếu A[0 i] đã đƣợc sắp và nhận giá trị false nếu ngƣợc lại. Khi sorted nhận giá trị true thì lệnh lặp (1) sẽ dừng lại. void BubbleSort (Item A[] , int n) { for (int i = n-1 ; i > 0 ; i ) { bool sorted = true; for( int k = 0 ; k A[k+1].key) { swap (A[k], A[k+1]); sorted = false; } if (sorted) break; } } Sinh viên thực hiện:Nguyễn Hải Nam 34
35. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp 3.2 SẮP XẾP HỒ NHẬP Thuật tốn sắp xếp hồ nhập (MergeSort) là một thuật tốn đƣợc thết kế bằng kỹ thuật chia - để - trị. Giả sử ta cần sắp xếp mảng A[a b], trong đĩ a, b là các số nguyên khơng âm, a b, a là chỉ số đầu và b là chỉ số cuối của mảng. Ta chia mảng thành hai mảng con bởi chỉ số c nằm giữa a và b ( c = ( a + b ) / 2). Các mảng con A[a c] và A[c+1 b] đƣợc sắp xếp bằng cách gọi đệ quy thủ tục sắp xếp hồ nhập. Sau đĩ ta hồ nhập hai mảng con A[a c] và A[c+1 b] đã đƣợc sắp thành mảng A[a b] đƣợc sắp. Giả sử Merge(A,a,c,b) là hàm kết hợp hai mảng con đã đƣợc sắp A[a c] và A[c+ 1 b] thành mảng A[a b] đƣợc sắp. Thuật tốn sắp xếp hồ nhập đƣợc biểu diễn bởi hàm đệ quy sau. void MergeSort( Item A[ ], int a, int b) { if (a < b) { int c = (a + b)/2; MergeSort ( A, a, c ); MergeSort ( A, c+1, b); Merge ( A, a, c, b); } } Cơng việc cịn lại của ta là thiết kế hàm hồ nhập Merge ( A, a, c, b), nhiệm vụ của nĩ là kết hợp hai nửa mảng đã đƣợc sắp A[a c] và A[ c+1 b] thành mảng đƣợc sắp. Ý tƣởng của thuật tốn hồ nhập là ta đọc lần lƣợt các thành phần của hai nửa mảng và chép vào mảng phụ B[0 b-a] theo đúng thứ tự tăng dần. Giả sử i là chỉ số chạy trên mảng con A[a c], i đƣợc khởi tạo là a ; j là chỉ số chạy trên mảng con A[c+1 b], j đƣợc khởi tạo là c + 1. So sánh A[i] và A[j], nếu A[i].key < A[j].key thì ta chép A[i] vào mảng B và tăng i lên 1, cịn nếu ngƣợc lại thì ta chép A[j] vào mảng B va tăng j lên 1. Lặp lại hành động đĩ cho đến khi i vƣợt quá c hoặc j vƣợt quá b. Nếu chỉ số i chƣa vƣợt quá c nhƣng j đã vƣợt quá b thì ta cần phải chép phần cịn lại Sinh viên thực hiện:Nguyễn Hải Nam 35
36. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp A[i c] vào mảng B. Tƣơng tự, nếu i > c, nhƣng j b thì ta cần chép phần cịn lại A[j b] vào mảng B. Chẳng hạn, xét mảng số nguyên A[ 5 14], trong đĩ A[5 9] và A[10 14] đã đƣợc sắp nhƣ sau: i j A 10 12 20 31 35 3 5 15 26 21 a = 5 6 7 8 c= 9 10 11 12 13 14 Bắt đầu i = 5 , j = 10. Vì A[5] > A[10] nên A[10] = 3 đƣợc chép vào mảng B và j = 11. Ta lại cĩ A[5] > A[11], nên A[11] = 5 đƣợc chép vào mảng B và j = 12. Đến dây A[5] b = 14, cịn i = 8 < c = 9, do đĩ ta chép nốt A[8] = 31 và A[9] = 35 sang B để nhận đƣợc mảng B đƣợc sắp. Bây giờ chỉ cần chép lại mảng B sang mảng A. Hàm Merge đƣợc viết nhƣ sau: void Merge( Item A[] , int a , int c , int b) // a, c, b là các số nguyên khơng âm, a c b. // Các mảng con A[a c] và A[c+1 b] đã đƣợc sắp. { Sinh viên thực hiện:Nguyễn Hải Nam 36
37. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp int i = a; int j = c + 1; int k = 0; int n = b – a + 1; Item * B = new Item[n]; (1) while (( i 1 Giả sử thời gian thực hiện các phép tốn trong mỗi lần lặp ở hàm Merge là hằng số d nào đĩ, ta cĩ : Sinh viên thực hiện:Nguyễn Hải Nam 37
38. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp T(1) d T(n) 2T(n/2) + nd Áp dụng phƣơng pháp thế lặp vào bất đẳng thức trên ta nhận đƣợc T(n) 2T(n/2) + n d 22 T(n/22) + 2 (n/2)d + n d 2k T(n/2k) + n d + + n d (k lần nd) Giả sử k là số nguyên dƣơng lớn nhất sao cho 1 n / 2k. Khi đĩ, ta cĩ T(n) 2k T(1) + n d + + n d ( k lần n d) T(n) (k + 1) n d T(n) (1 + log n) n d Vậy T(n) = O (n log n). 3.3 SẮP XẾP NHANH Trong mục này chúng ta trình bày thuật tốn sắp xếp đƣợc đƣa ra bởi Hoare, nổi tiếng với tên gọi là sắp xếp nhanh (QuickSort). Thời gian chạy của thuật tốn này trong trƣờng hợp xấu nhất là O(n2). Tuy nhiên thời gian chạy trung bình là O(n logn). Thuật tốn sắp xếp nhanh đƣợc thiết kế bởi kỹ thuật chia-để-trị nhƣ thuật tốn sắp xếp hịa nhập. Nhƣng trong thuật tốn sắp xếp hịa nhập, mảng A[a b] cần sắp đƣợc chia đơn giản thành hai mảng con A[a c] và A[c+1 b] bởi điểm chia ở giữa mảng, c = (a+b)/2. Cịn trong thuật tốn sắp xếp nhanh, việc “chia mảng thành hai mảng con” là một quá trình biến đổi phức tạp để từ mảng A[a b] ta thu đƣợc hai mảng con A[a k-1] và A[k+1 b] thỏa mãn các tính chất sau : A[i].key ≤ A[k].key với mọi i, a ≤ i ≤ k-1. Sinh viên thực hiện:Nguyễn Hải Nam 38
39. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp A[j].key > A[k].key với mọi j, k+1 ≤ j ≤ b. Nếu thực hiện đƣợc sự phân hoạch mảng A[a b] thành hai mảng con A[a k-1] và A[k+1 b] thỏa mãn các tính chất trên, thì nếu sắp xếp đƣợc các mảng con đĩ ta sẽ cĩ tồn bộ mảng A[a b] đƣợc sắp xếp. Giả sử Partition(A, a, b, k) là hàm phân hoạch mảng A[a b] thành hai mảng con A[a k-1] và A[k+1 b]. Thuật tốn sắp xếp nhanh là thuật tốn đệ quy đƣợc biểu diễn bởi hàm đệ quy nhƣ sau : void QuickSort(Item A[] , int a , int b) //Sắp xếp mảng A[a b] với a ≤ b. { if (a < b) { int k; Partition(A, a, b, k); if (a <= k – 1) QuickSort(A, a, k – 1); if (k + 1 <= b) QuickSort(A, k + 1, b); } } Hàm phân hoạch Partition là thành phần chính của thuật tốn sắp xếp nhanh. Vấn đề cịn lại là xây dựng hàm phân hoạch. Ý tƣởng của thuật tốn phân hoạch là nhƣ sau. Đầu tiên ta chọn một thành phần trong mảng A[a b] làm mốc (pivot). Sau đĩ ta chuyển tất cả các thành phần cĩ khĩa nhỏ hơn hoặc bằng khĩa của mốc sang bên trái mốc, chuyển tất cả các thành phần cĩ khĩa lớn hơn khĩa của mốc sang bên phải mốc. Kết quả là, ta cĩ mốc đứng ở vị trí k, bên trái là mảng con A[a k – 1], và bên phải là mảng con A[k + 1 b], các mảng con này cĩ tính chất mong muốn, tức là mọi thành phần trong mảng con A[a k - 1] cĩ khỏa nhỏ hơn hay bằng khĩa của A[k] và mọi thành phần trong mảng con A[k + 1 b] cĩ khĩa lớn hơn khĩa của A[k]. Chọn mốc phân hoạch nhƣ thế nào? Đƣơng nhiên là, ta mong muốn chọn đƣợc phần tử làm mốc sao cho kết quả phân hoạch cho ta hai mảng con Sinh viên thực hiện:Nguyễn Hải Nam 39
40. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp bằng nhau. Điều này là cĩ thể làm đƣợc, tuy nhiên nĩ địi hỏi nhiều thời gian hơn sự cần thiết. Vì vậy, ta sẽ chọn ngay thành phần đầu tiên của mảng làm mốc, tức là pivot = A[a].key. Sau đĩ ta sử dụng hai chỉ số, chỉ số left chạy từ trái sang phải, ban đầu left = a + 1, chỉ số right chạy từ phải sang trái, ban đầu right = b. Biến left sẽ tăng và dừng tại vị trí mà A[left].key > pivot, cịn biến right sẽ giảm và dừng lại tại vị trí mà A[right].key ≤ pivot. Khi đĩ nếu left right. Lúc này ta dễ thấy rằng, mọi thành phần trong mảng A[a right] cĩ khĩa nhỏ hơn hay bằng mốc, cịn mọi thành phần trong mảng A[left b] cĩ khĩa lớn hơn mốc. Cuối cùng ta trao đổi A[a] và A[right] để đặt mốc vào vị trí k = right. Hàm phân hoạch đƣợc viết nhƣ sau : void Partition( Item A[] , int a , int b , int & k) { keyType pivot = A[a].key; int left = a + 1; int right = b; do { while (( left pivot )) right ; if (left < right) { swap(A[left], A[right]); left ++; right ; } } while (left <= right); swap (A[a], A[right]) ; k = right ; } Để thấy đƣợc hàm phân hoạch làm việc nhƣ thế nào, ta hãy xét ví dụ sau. Giả sử ta cần phân hoạch mảng số nguyên A[0 9] nhƣ sau : Sinh viên thực hiện:Nguyễn Hải Nam 40
41. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp 8 3 17 12 6 14 7 5 13 15 left right Lấy mốc pivot = A[0] = 8, ban đầu left = 1, right = 9. Chỉ số left tăng và dừng lại tại vị trí left = 2, vì A[2] = 17 > 8, chỉ số right giảm và dừng lại tại vị trí right = 7, vì A[7] = 5 8 và A[right] = 7 8. A[right] = 14 > 8 nên right đƣợc giảm đi và dừng lại tại right = 4, vì A[4] < 8. Ta cĩ hồn cảnh sau : 8 3 5 7 6 14 12 17 13 15 right left Sinh viên thực hiện:Nguyễn Hải Nam 41
42. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp Đến đây right 1. Đây là quan hệ đệ quy mà ta đã gặp khi phân tích sắp xếp hịa nhập. Nhƣ vậy trong trƣờng hợp tốt nhất thời gian chạy của QuickSort là O(n logn). Thời gian trong trường hợp xấu nhất. Trƣờng hợp xấu nhất là trƣờng hợp mà sau mỗi lần phân hoạch mảng n phần tử ta nhận đƣợc mảng con n – 1 phần tử ở một phía của mốc, cịn phía kia khơng cĩ phần tử nào. (Dễ thấy rằng trƣờng hợp này xẩy ra khi ta phân hoạch một mảng đã đƣợc sắp). Khi đĩ ta cĩ quan hệ đệ quy sau : Sinh viên thực hiện:Nguyễn Hải Nam 42
43. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp T(1) = O(1) T(n) = T(n – 1) + O(n) với n > 1 Ta cĩ : T(1) = C T(n) = T(n – 1) + nC với n > 1 Trong đĩ C là hằng số nào đĩ. Bằng cách thế lặp ta cĩ : T(n) = T(1) + 2C + 3C + + nC n = C i = Cn(n+1)/2 i 1 Do đĩ trong trƣờng hợp xấu nhất, thời gian chạy của sắp xếp nhanh là O(n2). Thời gian trung bình. Bây giờ ta đánh giá thời gian trung bình Ttb(n) mà QuickSort địi hịi để sắp xếp một mảng cĩ n phần tử. Giả sử mảng A[a b] chứa n phần tử đƣợc đƣa vào mảng một cách ngẫu nhiên. Khi đĩ hàm phân hoạch Partition(A, a, b, k) sẽ cho ra hai mảng con A[a k – 1] và A[k + 1 b] với k là một trong các chỉ số từ a đến b với xác suất nhƣ nhau và bằng 1/n. Vì thời gian thực hiện hàm phân hoạch là O(n), từ hàm QuickSort ta suy ra quan hệ đệ quy sau : n 1 Ttb(n) = n  [ Ttb(k - 1) + Ttb(n - k)] + O(n) k 1 Hay n Ttb(n) =  [ Ttb(k - 1) + Ttb(n - k)] + nC (1) k 1 Trong đĩ C là hằng số nào đĩ. Chú ý‎ rằng Sinh viên thực hiện:Nguyễn Hải Nam 43
44. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp n  Ttb(k - 1) = Ttb(n - k) k 1 Do đĩ cĩ thể viết lại (1) nhƣ sau : n 2 Ttb(n) = n  Ttb(k - 1) + nC (2) k 1 Trong (2) thay n bới n – 1 ta cĩ : n 1 2 Ttb(n - 1) = n 1  Ttb(k - 1) + (n – 1)C (3) k 1 Nhân (2) với n, nhân (3) với n – 1 và trừ cho nhau ta nhận đƣợc n Ttb(n) = (n + 1) Ttb(n - 1) + (2n – 1)C Chia đẳng thức trên cho n(n + 1) ta nhận đƣợc quan hệ đệ quy sau : 2n - 1 Ttb (n) Ttb (n - 1) n 1 = n + nn( 1) C (4) Sử dụng phép thế lặp, từ (4) ta cĩ = + C Ttb (n - 2) 2n - 3 = n 1 + (nn 1) + C . . . Ttb (1) n 21i = 2 + c  (5) i 1 ii( 1) Ta cĩ đánh giá Sinh viên thực hiện:Nguyễn Hải Nam 44
45. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp n 21i n 2 n dx  ≤  ≤ 2 ≤ 2logn k 1 ii( 1) i 1 i 1 x Do đĩ từ (5) ta suy ra Ttb (n) n 1 = O(logn) hay Ttb(n) = O(n logn). Trong trƣờng hợp xấu nhất, QuickSort địi hỏi thời gian O(n2), nhƣng trƣờng hợp này rất ít khi xảy ra. Thời gian trung bình của QuickSort là O(n logn), và thời gian trong trƣờng hợp xấu nhất của MergeSort cũng là O(n logn). Tuy nhiên thực tiễn cho thấy rằng, trong phần lớn các trƣờng hợp QuickSort chạy nhanh hơn các thuật tốn sắp xếp khác. 3.4 SẮP XẾP SỬ DỤNG CÂY THỨ TỰ BỘ PHẬN Trong mục này chúng ta trình bày phƣơng pháp sắp xếp sử dụng cây thứ tự bộ phận (heapsort). Trong mục 10.3, chúng ta biết rằng một cây thứ tự bộ phận n đỉnh cĩ thể biểu diễn bởi mảng A[0 n-1], trong đĩ gốc cây đƣợc lƣu trong A[0], và nếu một đỉnh đƣợc lƣu trong A[i], thì đỉnh con trái (nếu cĩ) của nĩ đƣợc lƣu trong A[2*i + 1], cịn đỉnh con phải nếu cĩ của nĩ đƣợc lƣu trong A[2*i + 2]. Mảng A thoả mãn tính chất sau (ta sẽ gọi là tính chất heap): A[i].key = 1, trừ i = 0. Biến đổi mảng A[0 n-2] để nĩ thoả mãn tính chất heap. Lại trao đổi Sinh viên thực hiện:Nguyễn Hải Nam 45
46. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp A[0] và A[n-2]. Rồi lại biến đổi mảng A[0 n-3] trở thành mảng thoả mãn tính chất heap. Lặp lại quá trình trên, cuối cùng ta sẽ nhận đƣợc mảng A[0 n-1] đƣợc sắp theo thứ tự giảm dần: A[0].key >= A[1].key >= >= A[n-1].key Trong quá trình trên, sau mỗi lần trao đổi A[0] với A[m] (với m=n- 1, ,1), ta sẽ nhận đƣợc mảng A[0 m-1] thoả mãn tính chất heap với mọi i >= 1, trừ i = 0. Điều này cĩ nghĩa là cây nhị phân đƣợc biểu diễn bởi mảng A[0 m-1] đã thoả mãn tính chất thứ tự bộ phận, chỉ trừ gốc. Để nĩ trở thành cây thứ tự bộ phận, ta chỉ cần đẩy dữ liệu lƣu ở gốc xuống vị trí thích hợp trong cây, bằng cách sử dụng hàm ShiftDown (Xem mục 10.3.3). Cịn một vấn đề cần giải quyết, đĩ là biến đổi mảng cần sắp xếp A[0 n-1] thành mảng thoả mãn tính chất heap. Điều này cĩ nghĩa là ta phải biến đổi cây nhị phân đƣợc biểu diễn bởi mảng A[0 n-1] thành cây thứ tự bộ phận. Muốn vậy, với i chạy từ n/2-1 giảm xuống 0, ta chỉ cần sử dụng hàm SiftDown để đẩy dữ liệu lƣu ở đỉnh i xuống vị trí thíc hợp trong cây. Đây là cách xây dựng cây thứ tự bộ phận mà chúng ta đã trình bày trong 10.3.2. Bây giờ ta viết lại hàm ShiftDown cho thích hợp với sự sử dụng nĩ trong thuật tốn. Giả sử mảng A[a b] (a = a+1. Hàm ShiftDown(a,b) sau đây thực hiện việc đẩy A[a] xuống vị trí thích hợp trong mảng A[a b] để mảng thoả mãn tính chất heap với mọi i >= a. void ShiftDown(int a, int b) { int i = a; int j = 2 * i + 1; while (j A[j].key) { Sinh viên thực hiện:Nguyễn Hải Nam 46
47. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp swap(A[i],A[j]); i = j; j = 2 * i + 1; } else break; } } Sử dụng hàm ShiftDown, ta đƣa ra thuật tốn sắp xếp HeapSort sau đây. Cần lƣu ý rằng, kết quả của thuật tốn là mảng A[0 n-1] đƣợc sắp xếp theo thứ tự giảm dần. void HeapSort(Item A[] , int n) //Sắp xếp mảng A[0 n-1] với n > 1 { for (int i = n / 2 – 1 ; i >= 0 ; i ) ShiftDown(i,n-1); //Biến đổi mảng A[0 n-1] // thành mảng thoả mãn tính chất heap for (int i = n – 1 ; i >= 1 ; i ) { swap(A[0],A[i]); ShiftDown(0,i - 1); } } Phân tích HeapSort. Thời gian thực hiện lệnh lặp (1) là thời gian xây dựng cây thứ tự bộ phận mà chúng ta đã xét trong mục 10.3.2. Theo chứng minh đã đƣa ra trong 10.3.2, lệnh lặp (1) chỉ địi hỏi thời gian O(n). Trong lệnh lặp (2), số lần lặp là n-1. Thân vịng lặp (2), với i = n-1 là swap(A[0],A[n - 1]); ShiftDown(0,n - 2); Đây là các lệnh thực hiện DeleteMin trên cây thứ tự bộ phận đƣợc biểu diễn bởi mảng A[0 n-1], và dữ liêụ cĩ khố nhỏ nhất đƣợc lƣu vào A[n-1]. Trong Sinh viên thực hiện:Nguyễn Hải Nam 47
48. Nghiên cứu khoa học Mơ phỏng thuật tốn sắp xếp mục 10.3.1, ta đã chứng tỏ rằng DeleteMin chỉ cần thời gian O(logn). Nhƣ vậy thân của lệnh lặp (2) cần thời gian nhiều nhất là O(logn). Do đĩ lệnh (2) cần thời gian O(nlogn). Vì vậy, thời gian thực hiện HeapSort là O(nlogn). Sinh viên thực hiện:Nguyễn Hải Nam 48