Đăng ký Đăng nhập
Trang chủ Tìm hiểu các thuật toán sắp xếp và đánh giá để so sánh...

Tài liệu Tìm hiểu các thuật toán sắp xếp và đánh giá để so sánh

.PDF
31
213
52

Mô tả:

Đồ án Cấu trúc dữ liệu và Giải thuật LỜI MỞ ĐẦU Ngày nay với sự phát triển nhảy vọt của khoa học vông nghệ nói chung của ngành tin học nói riêng,với những tính năng ưu việt, sự tiện dụng và ứng dụng rộng rãi, tin học ngày nay là một phần không thể thiếu được của nhiều ngành trong công cuộc xây dựng và phát triển xã hội. Hơn thế nữa nó còn đi sâu đời sống của con người. Tin học đã thâm nhập khá mạnh mẽ vào Việt Nam, nhiều lĩnh vực hoạt động từ lĩnh vực quản lý hành chính, quản lý kinh tế, tự động hóa công nghiệp …đến các lĩnh vực giáo dục và đào tạo đều có thay đổi đáng kể nhờ ứng dụng tin học. Máy tính là công cụ cần thiết đối với con người trong thời đại ngày nay. Trong các môn học Toán – Tin, đặc biệt là ngành Công nghệ thông tin, thuật toán đóng vai trò vô cùng quan trọng. Việc nắm vững thuật toán giúp ta tìm ra hướng giải quyết vấn đề nhanh hơn, viết code mạch lạc hơn. Nắm vững thuật toán, cấu trúc dữ liệu, ta sẽ ước tính được độ phức tạp của code, đánh giá code chạy nhanh hay chậm, có bền vững hay không. Đây là những kĩ năng vô cùng cần thiết để trở thành một kĩ sư giỏi. Vì vậy khoa Tin rất tập trung trong việc giảng dạy môn Phân tích và Thiết kế giải thuật. Bên cạnh đó, sinh viên em còn được thực hành và kiểm tra trình độ của mình qua việc làm Đồ án Giải thuật & Lập trình với các đề tài cụ thể và thiết thực. Mặc dù em đã rất cố gắng và nổ lực để làm đồ án này do kinh nghiệm còn hạn chế và kiến thức em nắm chưa sâu nên em biết sẽ không tránh khỏi những thiếu sót. Em rất mong nhận được sự thông cảm và đóng góp của các Thầy, Cô để lần sau làm đồ án được tốt hơn. Hoàn thành đồ án Giải thuật & Lập trình này là niềm vui của em, em rất là biết ơn Thầy Hồ Ngọc Tú đã hướng dẫn chúng em tận tình trong suốt thời gian chúng em làm đồ án. Một lần nữa nhóm chúng em xin gửi lời cám ơn chân thành nhất đến Thầy. Trang 2 Đồ án Cấu trúc dữ liệu và Giải thuật MỤC LỤC LỜI MỞ ĐẦU .......................................................................................................... 2 MỤC LỤC ............................................................................................................... 3 DANH MỤC HÌNH VẼ .......................................................................................... 4 1. GIỚI THIỆU ĐỀ TÀI ...................................................................................... 5 2. CƠ SỞ LÝ THUYẾT ...................................................................................... 5 3. 2.1. Thuâ ̣t toán ................................................................................................. 5 2.2. Đô ̣ phức ta ̣p thuâ ̣t toán .............................................................................. 6 2.3. Thuâ ̣t toán sắ p xế p .................................................................................... 6 2.4. Giải thuâ ̣t chia để tri ̣(Devide and Conquer) ............................................. 7 TỔ CHỨC CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN ................................ 7 3.1. Phát biểu bài toán ...................................................................................... 7 3.2. Cấu trúc dữ liệu ......................................................................................... 8 3.3. Thuật toán ................................................................................................. 8 3.3.1. Sắ p xế p cho ̣n (Selection Sort) ............................................................. 8 3.3.2. Sắ p xế p chèn (Insertion Sort) ............................................................ 11 3.3.3. Sắ p xế p nổ i bo ̣t (Bubble Sort) ........................................................... 14 3.3.4. Sắ p xế p trô ̣n (Merge Sort) ................................................................. 17 3.3.5. Sắ p xế p nhanh (Quick Sort) .............................................................. 21 4. CHƯƠNG TRÌNH VÀ KẾT QUẢ ............................................................... 24 4.1. Tổ chức chương trình .............................................................................. 24 4.2. Ngôn ngữ cài đặt ..................................................................................... 27 4.3. Kết quả .................................................................................................... 28 4.3.1. Giao diện chính của chương trình ..................................................... 28 4.3.2. Kết quả thực thi của chương trình ..................................................... 29 4.3.3. Nhận xét............................................................................................. 31 5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN..................................................... 31 5.1. Kết luận ................................................................................................... 31 5.2. Hướng phát triển ..................................................................................... 31 TÀI LIỆU THAM KHẢO ..................................................................................... 32 Trang 3 Đồ án Cấu trúc dữ liệu và Giải thuật DANH MỤC HÌNH VẼ Trang 4 Đồ án Cấu trúc dữ liệu và Giải thuật 1. GIỚI THIỆU ĐỀ TÀI Hiê ̣n nay, có rấ t nhiều vấn đề phổ biến trong các lĩnh vực thực tiễn về khoa học máy tính, ứng dụng cơ sở dữ liệu, mạng và trí tuệ nhân tạo. Một trong những vấn đề cơ bản nhấ t đó là thuật toán sắp xếp, mô ̣t vấn đề đã thu hút rất nhiều nghiên cứu. Quá triǹ h sắp xếp là quá trình bố trí lại các phầ n tử theo mô ̣t trâ ̣t tự nhấ t định để cho viê ̣c xử lý trở nên dễ dàng và hiê ̣u quả hơn so với xử lý các phần tử ngẫu nhiên. Sắp xếp là một trong những giải thuâ ̣t lập trình phổ biến nhất, ví dụ khi lấy cơ sở dữ liệu ứng dụng, nếu chúng ta muốn quản lý thông tin để thuâ ̣n tiê ̣n cho viê ̣c tìm kiế m, chúng ta phải giữ thông tin theo thứ tự hợp lý, ví dụ: thứ tự chữ cái theo tên, thứ tự tăng dần hoă ̣c giảm dần theo mã ID, lương, ngày nhâ ̣n vào làm viê ̣c,... Sự tăng trưởng thông tin mô ̣t cách nhanh chóng đã kéo theo sự phát triển của các thuật toán sắp xếp. Các thuâ ̣t toán này đươ ̣c phát triể n nhằ m nâng cao hiê ̣u suấ t và giảm thiể u đô ̣ phức ta ̣p. Dữ liê ̣u có thể xuấ t hiê ̣n dưới nhiề u dạng khác nhau và thường phải được lưu trữ mô ̣t khố i lươ ̣ng đáng kể , nên viê ̣c xây dựng các thuâ ̣t toán sắ p xế p cho phép tìm kiếm nhanh đem lại ý nghiã rấ t lớn. Hiê ̣n nay, có rấ t nhiề u thuâ ̣t toán sắ p xế p được ra đời như sắp xếp chọn, sắ p xế p nổ i bọt, sắ p xế p chèn, sắ p xế p trô ̣n, sắ p xế p nhanh,... mỗi thuâ ̣t toán đề u có một cơ chế khác nhau nhằ m làm tăng hiệu suất và hiệu quả của các ứng dụng thực tế và giảm độ phức tạp thời gian của từng ứng dụng. Khi so sánh giữa các thuật toán sắp xếp khác nhau, có ba yếu tố cầ n đươ ̣c xem xét: độ phức tạp thời gian, sự ổn định và không gian bộ nhớ. Qua viê ̣c so sánh, chúng ta có thể hiểu rõ hơn về ưu điể m, khuyế t điểm của các thuâ ̣t toán sắp xế p, từ đó vâ ̣n du ̣ng đúng thuâ ̣t toán theo yêu cầ u của bài toán đă ̣t ra mô ̣t cách hiê ̣u quả và đó cũng là mu ̣c đích của đề tài này. 2. CƠ SỞ LÝ THUYẾT 2.1. Thuâ ̣t toán Thuật toán , còn gọi là giải thuật, là một tập hợp hữu hạn hay một dãy các quy tắc chặt chẽ của các chỉ thị, phương cách hay 1 trình tự các thao tác trên một đối tượng cụ thể được xác định và định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán trước. Nói cách khác, thuật toán là một bộ các quy tắc hay quy trình cụ thể nhằm giải quyết một vấn đề nào đó trong một số bước hữu hạn, hoặc nhằm cung cấp một kết quả từ một tập hợp của các dữ kiện đưa vào [1]. Trang 5 Đồ án Cấu trúc dữ liệu và Giải thuật Một thuật toán có các tính chất sau: - Tính chính xác: để đảm bảo kết quả tính toán hay các thao tác mà máy tính thực hiện được là chính xác. Tính rõ ràng: Thuật toán phải được thể hiện bằng các câu lệnh minh bạch; các câu lệnh được sắp xếp theo thứ tự nhất định. Tính khách quan: Một thuật toán dù được viết bởi nhiều người trên nhiều máy tính vẫn phải cho kết quả như nhau. Tính phổ dụng: Thuật toán không chỉ áp dụng cho một bài toán nhất định mà có thể áp dụng cho một lớp các bài toán có đầu vào tương tự nhau. Tính kết thúc: Thuật toán phải gồm một số hữu hạn các bước tính toán. 2.2. Độ phức ta ̣p thuâ ̣t toán Độ phức tạp của một thuật toán là 1 hàm phụ thuộc vào độ lớn của dữ liệu đầu vào. Để ước lượng độ phức tạp của một thuật toán ta thường dùng khái niệm bậc O-lớn và bậc Θ. Giả sử f(n) và g(n) là các hàm thực không âm của đối số nguyên không âm n. Ta nói “g(n) là O của f(n)” và viết là: g(n) = O(f(n)) nếu tồn tại các hằng số dương C và n0 sao cho g(n) <= C * f(n) với mọi n >= n0. Việc xác định độ phức tạp tính toán của giải thuật trong thực tế có thể tính bằng một số quy tắc đơn giản sau: - Quy tắc bỏ hằng số: T(n) = O(c.f(n)) = O(f(n)) với c là một hằng số dương Quy tắc lấy max: T(n) = O(f(n)+ g(n)) = O(max(f(n), g(n))) Quy tắ c cô ̣ng: O(f(n)+g(n))=max{O(f(n)),O(g(n))} Quy tắ c nhân: O(f(n).g(n))=O(f(n)).O(g(n)) 2.3. Thuâ ̣t toán sắ p xế p Sắp xếp là quá trình biế n đổ i mô ̣t danh sách các phầ n từ thành mô ̣t danh sách thỏa mañ mô ̣t thứ tự xác đinh ̣ nào đó, nhằ m có lợi cho việc quản lý và đinh ̣ vi ̣ thông tin. Sắ p xế p đóng vai trò vô cùng quan tro ̣ng tim ̀ kiế m dữ liê ̣u. Chẳ ng ha ̣n, khi đã có một 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ử du ̣ng thuật toán tìm kiế m nhi ̣phân, hiê ̣u quả hơn nhiề u so với tìm kiế m tuầ n tự. Trên thực tế , nhiề u thuật toán đươ ̣c đưa ra dựa trên ý tưởng xử lý các đố i tươ ̣ng theo mô ̣t thứ tự xác đinh ̣ nên sắ p xế p là mô ̣t giải thuâ ̣t rấ t quan trọng và cầ n thiế t. Các thuâ ̣t toán sắ p xế p đươ ̣c chia làm 2 loa ̣i: internal sorting và external sorting. Với internal sorting, toàn bộ dữ liệu cần sắp xếp được đưa vào bộ nhớ trong, do vậy kích thước dữ liệu cần sắp xếp nhỏ và thời gian sắp xếp được thực hiện rất nhanh. Với Trang 6 Đồ án Cấu trúc dữ liệu và Giải thuật external sorting, 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, kích thước dữ liệu cần sắp xếp lúc này rất lớn, và thời gian sắp xếp thực hiện rất chậm [2]. Các thuật toán sắp xếp được phát triển để sắp xếp dữ liệu theo nhiều cách khác nhau. Ví dụ, một mảng các số nguyên có thể được sắp xếp theo thứ tự từ thấp nhấ t đến cao nhất hoặc từ cao nhất đến thấp nhấ t, hoặc mảng các phần tử chuỗi có thể được sắp xếp theo thứ tự bảng chữ cái. Hầu hết các thuật toán sắp xếp, như sắp xếp lựa chọn, sắp xếp nổ i bo ̣t sử dụng kỹ thuật hoán đổi các phầ n tử cho đến khi đạt được mục tiêu. Mỗi thuật toán sắp xếp được chọn dựa trên hiệu quả trường hợp tốt nhất, trường hợp trung bình và trường hợp xấu nhất. 2.4. Giải thuâ ̣t chia để tri (Devide and Conquer) ̣ Phương pháp chia để trị (Divide and Conquer) là một phương pháp quan trọng trong việc thiết kế các giải thuật. Ý tưởng của phương pháp này khá đơn giản và rất dễ hiểu: Khi cần giải quyết một bài toán, ta sẽ tiến hành chia bài toán đó thành các bài toán con nhỏ hơn. Tiếp tục chia cho đến khi các bài toán nhỏ này không thể chia thêm nữa, khi đó ta sẽ giải quyết các bài toán nhỏ nhất này và cuối cùng kết hợp giải pháp của tất cả các bài toán nhỏ để tìm ra giải pháp của bài toán ban đầu. Giải thuâ ̣t chia để trị bao gồ m 3 tiến triǹ h: - - Chia nhỏ: Trong bước này, chúng ta chia bài toán ban đầu thành các bài toán con. Mỗi bài toán con nên là một phần của bài toán ban đầu. Nói chung, bước này sử dụng phương pháp đệ qui để chia nhỏ các bài toán cho đến khi không thể chia thêm nữa. Khi đó, các bài toán con được gọi là "atomic – nguyên tử", nhưng chúng vẫn biểu diễn một phần nào đó của bài toán ban đầu. Giải bài toán con: Trong bước này, các bài toán con được giải. Kế t hơ ̣p lời giải: Sau khi các bài toán con đã được giải, trong bước này chúng ta sẽ kết hợp chúng một cách đệ qui để tìm ra giải pháp cho bài toán ban đầu [3]. 3. TỔ CHỨC CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 3.1. Phát biểu bài toán Đầ u vào (Input): tệp chứa mảng các phần tử số nguyên Phương pháp (Method): sắp xếp chọn, sắ p xế p chèn, sắp xế p nổ i bọt, sắ p xế p trô ̣n, sắ p xế p nhanh Đầu ra (Output): tê ̣p chứa mảng các phầ n tử số nguyên đã đươ ̣c sắ p xế p theo thứ tự tăng dầ n Trang 7 Đồ án Cấu trúc dữ liệu và Giải thuật 3.2. Cấu trúc dữ liệu - Sử du ̣ng mảng để triể n khai giải thuâ ̣t - int array[]; // chứa các phầ n tử của dãy số cầ n đươ ̣c sắ p xế p - int n; // số phầ n tử của mảng 3.3. Thuật toán 3.3.1. Sắp xế p cho ̣n (Selection Sort) 3.3.1.1 . Ý tưởng Phương pháp sắp xếp lựa chọn sẽ sắp xếp một mảng bằng cách liên tục tìm phần tử nhỏ nhất từ phần mảng chưa được sắp xếp và đưa nó về vị trí đầu của mảng đó. Cụ thể, duyệt mảng A ban đầu gồm n phần tử A[0], A[1], …, A[n-1]. Chọn ra phần tử nhỏ nhất và sau đó đưa về vị trí đầu tiên của mảng hiện hành. Vậy ta đã có được một phần tử đầu tiên A[0] đã được sắp xếp theo thứ tự, loại phần tử đó ra khỏi mảng đang xét. Tiếp tục duyệt mảng gồm n-1 phần tử, bắt đầu từ vị trí A[1]. Chọn ra phần tử nhỏ nhất và đưa về vị trí đầu tiên của mảng hiện hành, sau đó loại phần tử đó ra khỏi mảng đang xét. Vậy ta đã có được 2 phần tử đầu tiên A[0], A[1] đã được sắp xếp theo thứ tự. Tổng quát, ta duyệt mảng gồm n-i phần tử, bắt đầu từ A[i] (i = 0  n-2), chọn ra phần tử nhỏ nhất rồi đưa về vị trí A[i]. Cuối cùng ta sẽ thu được mảng đã được sắp xếp theo thứ tự. 3.3.1.2 . Thuâ ̣t toán Input: Mảng A[] gồm n phần tử Output: Mảng A[] gồm n phần tử đã được sắp xếp  Bước 1: i = 0;  Bước 2: Tìm phần tử nhỏ nhất A[min] trong mảng đang xét, từ A[i] đến A[n-1];  Bước 3: Hoán vị A[min] với A[i];  Bước 4: i=i+1. Nếu i < n-1, quay lại bước 2; Ngược lại: kết thúc. Trang 8 Đồ án Cấu trúc dữ liệu và Giải thuật 3.3.1.3 Minh ho ̣a thuâ ̣t toán j = 19 i=0 15 22 A[min] 13 27 20 12 23 24 25 10 A[min] i=1 10 22 13 27 20 12 23 24 25 15 20 22 23 24 25 15 A[min] j = 39 i=2 10 22 13 27 j = 49 i=3 10 12 13 27 20 A[min] 22 23 24 25 15 23 24 25 27 A[min] j = 59 i=4 10 12 13 15 20 22 Tiếp tục thực hiện như vậy trong khi i < n-1. Trang 9 Đồ án Cấu trúc dữ liệu và Giải thuật 3.3.1.4 . Sơ đồ khố i Bắt đầu Mảng A, n phần tử i0 F i++ i < n-1 ? T min  i J  i+1 F j++ JĐộ phức tạp là: 𝐓(𝐧) = ∑𝒊=𝟎 (𝐧 − 𝐢 − 𝟏) = = O(n2) - 𝟐 - Trường hơ ̣p trung bình: tương tự trường hơ ̣p xấ u nhấ t, đô ̣ phức ta ̣p là O(n2) Trường hơ ̣p tố t nhấ t: đô ̣ phức ta ̣p là O(n2) 3.3.2. Sắp xế p chèn (Insertion Sort) 3.3.2.1 . Ý tưởng Phương pháp sắp xếp chèn thực hiện bằng cách chèn phần tử đang xét vào vị trí thích hợp trong mảng đã được sắp xếp phía trước nó. Cụ thể, ban đầu, xem phần tử A[0] là mảng đã có thứ tự. Sau đó chèn phần tử A[1] vào đúng vị trí trong mảng gồm A[0] trên sao cho mảng A[0], A[1] được sắp xếp theo thứ tự. Tiếp tục chèn phần tử A[2] vào đúng vị trí trong mảng gồm A[0], A[1] trên sao cho mảng A[0], A[1], A[2] được sắp xếp theo thứ tự. Tổng quát, ta thực hiện chèn phần tử A[i] vào mảng gồm A[0], A[1], …, A[i-1] sao cho mảng A[0], A[1], …, A[i] (i = 1  n-1) được sắp xếp theo thứ tự. Cuối cùng ta sẽ thu được mảng đã được sắp xếp theo thứ tự. 3.3.2.2 . Thuâ ̣t toán Input: Mảng A[] gồm n phần tử Output: Mảng A[] gồm n phần tử đã được sắp xếp  Bước 1: i = 1;  Bước 2: Gán key = A[i];  Bước 3: Tìm vị trí thích hợp trong mảng A[0], …, A[i-1] để chèn A[i] vào;  Bước 4: Chèn key vào vị trí vừa tìm được;  Bước 5: i=i+1. Nếu i < n, quay lại bước 2; Ngược lại: kết thúc. Trang 11 Đồ án Cấu trúc dữ liệu và Giải thuật 3.3.2.3 Minh ho ̣a thuâ ̣t toán j=0 i=1 15 22 13 27 20 12 23 24 25 10 13 27 20 12 23 24 25 10 27 20 12 23 24 25 10 j=1 i=2 15 22 j=2 i=3 13 15 22 j=3 i=4 13 15 22 27 A[min] 20 22 23 24 25 10 12 23 24 25 10 j=4 i=5 13 15 20 22 27 Tiếp tục thực hiện như vậy trong khi i < n. Trang 12 Đồ án Cấu trúc dữ liệu và Giải thuật 3.3.2.4 Sơ đồ khố i Bắt đầu Mảng A, n phần tử i1 F i++ i= 0 && A[j] > key ? j-- T A[j+1]  A[j] A[j+1]  key Kết thúc Trang 13 Đồ án Cấu trúc dữ liệu và Giải thuật 3.3.2.5 . Đô ̣ phức ta ̣p Trường hơ ̣p xấ u nhấ t: với mỗi i thì số lần so sánh tối đa là i. 𝒏(𝒏−𝟏)  Độ phức tạp thuật toán là: 𝐓(𝐧) = ∑𝒏−𝟏 = O(n2) 𝒊=𝟏 𝐢 = - 𝟐 - Trường hơ ̣p trung bình: tương tự trường hơ ̣p xấ u nhấ t, đô ̣ phức ta ̣p là O(n2) Trường hơ ̣p tố t nhấ t: đô ̣ phức ta ̣p là O(n) 3.3.3. Sắp xế p nổ i bo ̣t (Bubble Sort) 3.3.3.1 . Ý tưởng Phương pháp sắp xếp nổi bọt thực hiện đúng như tên gọi của nó bằng cách cho “nổi bọt” những phần tử nhỏ hơn lên đầu mảng. Cụ thể, duyệt từ cuối về đầu mảng, lần lượt xét 2 phần tử kề nhau, nếu phần tử phía sau nhỏ hơn thì sẽ cho “nổi bọt lên”, đổi chỗ với phần tử kề trước nó. Kết thúc lần xét duyệt đầu tiên, ta sẽ thu được A[0] là phần tử nhỏ nhất của mảng, loại ra khỏi mảng đang xét. Tiếp tục duyệt từ cuối về đầu mảng hiện hành, sau quá trình “nổi bọt” ta tiếp tục thu được A[1] là phần tử nhỏ nhất tiếp theo, loại ra khỏi mảng đang xét. Tổng quát, ta duyệt từ cuối về đầu mảng gồm n-i phần tử (i = 0  n-1). Lần lượt so sánh 2 phần tử kề nhau và “nổi bọt” lên phần tử nhỏ hơn. Sau vòng duyệt thứ i ta sẽ thu được phần tử thứ A[i] của mảng đã được sắp xếp. 3.3.3.2 Thuật toán Input: Mảng A[] gồm n phần tử Output: Mảng A[] gồm n phần tử đã được sắp xếp  Bước 1: i = 0;  Bước 2: j = n – 1;  Bước 3: Nếu A[j] < A[j-1], đổi chỗ A[j] và A[j-1];  Bước 4: j=j-1. Nếu j > i, quay lại bước 3. Ngược lại: sang bước 5;  Bước 5: i=i+1. Nếu i < n-1, quay lại bước 2; Ngược lại: kết thúc. Trang 14 Đồ án Cấu trúc dữ liệu và Giải thuật 3.3.3.3 Minh ho ̣a thuâ ̣t toán j=9 i=0 15 22 13 12 20 27 10 15 22 13 12 20 10 27 15 22 13 12 10 20 27 15 22 13 10 12 20 27 15 22 10 13 12 20 27 15 10 22 13 12 20 27 10 15 22 13 12 20 27 j=8 i=1 10 15 22 13 12 20 27 10 15 22 12 13 20 27 10 15 12 22 13 20 27 10 12 15 22 13 20 27 Tiếp tục thực hiện như vậy trong khi i < n-1. Trang 15 Đồ án Cấu trúc dữ liệu và Giải thuật 3.3.3.4 Sơ đồ khố i Bắt đầu Mảng A, n phần tử i0 F i++ i < n-1 ? T j  n-1 F j-- j>i? T F A[j] < A[j-1] T swap(A[min], A[i]) Kết thúc Trang 16 Đồ án Cấu trúc dữ liệu và Giải thuật 3.3.3.5 Độ phức ta ̣p Trường hơ ̣p xấ u nhấ t: với mỗi i thì số lần so sánh tối đa là n – i - 1. 𝒏−𝟐 𝒏(𝒏−𝟏)  Độ phức tạp là: 𝐓(𝐧) = ∑𝒊=𝟎 (𝐧 − 𝐢 − 𝟏) = = O(n2) - 𝟐 - Trường hơ ̣p trung bình: tương tự trường hơ ̣p xấ u nhấ t, đô ̣ phức ta ̣p là O(n2) Trường hơ ̣p tố t nhấ t: đô ̣ phức ta ̣p là O(n) 3.3.4. Sắp xế p trô ̣n (Merge Sort) 3.3.4.1 . Ý tưởng Sắp xếp trộn là một thuật toán được thiết kế bằng kĩ thuật chia để trị. Để sắp xếp mảng ban đầu A gồm n phần tử A[0], A[1], …, A[n-1], ta sẽ chia mảng cần xếp thành 2 mảng con phân cách nhau bởi phần tử chính giữa mảng. Sau khi thu được 2 mảng con, ta sẽ tiến hành sắp xếp từng mảng con theo thứ tự đúng rồi ghép 2 mảng con lại với nhau, tạo thành mảng A gồm n phần tử ban đầu. Trong quá trình sắp xếp từng mảng con, ta lại tiến hành chia đôi, sắp xếp rồi ghép lại. Quá trình đó cứ lần lượt được lặp lại cho đến mảng con nhỏ nhất chỉ còn 1 phần tử. Sau đó ta so sánh 2 mảng con trong cùng mảng cơ sở (khi chia đôi 1 mảng lớn thành 2 mảng con, mảng lớn đó được gọi là mảng cơ sở), sắp xếp và ghép 2 mảng con đó lại thành mảng cơ sở. Việc so sánh và ghép các mảng con được lặp lại đến khi còn lại mảng cơ sở duy nhất thì đó là mảng đã được sắp xếp. Trong phương pháp này, các mảng con sau khi được phân hoạch sẽ tiến hành sắp xếp và ghép lại thành mảng cơ sở theo quy trình sau: ta xét 2 phần tử đầu tiên của từng mảng, phần tử nào nhỏ hơn sẽ được đưa vào mảng cơ sở và bị loại khỏi mảng con đang xét. Tiếp tục xét 2 phần tử đầu tiên của 2 mảng con đó, chọn ra phần tử nhỏ hơn rồi đưa vào mảng cơ sở. Quá trình này được lặp lại cho đến khi 1 trong 2 mảng con trở thành mảng rỗng. các phần tử còn lại của mảng con còn lại sẽ được đưa hết vào mảng cơ sở. Cuối cùng, ta sẽ thu được 1 mảng cơ sở có số phần tử bằng 2 mảng con cộng lại và đã được sắp xếp theo thứ tự đúng. 3.3.4.2 . Thuâ ̣t toán Input: Mảng A[] gồm n phần tử với vị trí bắt đầu - l, vị trí kết thúc - r Output: Mảng A[] gồm n phần tử đã được sắp xếp  Bước 1: Kiểm tra l < r? Trong đó, l là vị trí bắt đầu, r là vị trí kết thúc của mảng đang xét. Nếu đúng, chuyển sang bước 2;  Bước 2: Tìm điểm chính giữa mảng đang xét: m = l + (r – l) / 2;  Bước 3: Sắp xếp trộn cho mảng con bắt đầu từ l đến m;  Bước 4: Sắp xếp trộn cho mảng con bắt đầu từ m+1 đến r; Trang 17 Đồ án Cấu trúc dữ liệu và Giải thuật  Bước 5: Ghép 2 mảng con đã sắp xếp ở trên thành mảng cơ sở: - Bước 5.1: So sánh 2 phần tử đầu tiên của 2 mảng con; - Bước 5.2: Đưa phần tử nhỏ hơn vào mảng cơ sở, rồi loại phần tử đó ra khỏi 2 mảng con đang xét; - Bước 5.3: Kiểm tra 1 trong 2 mảng con đã rỗng chưa? Nếu sai, quay lại bước 5.1; ngược lại, chuyển đến bước 5.4; - Bước 5.4: Gán tất cả phần tử còn lại của mảng con còn lại vào mảng cơ sở; 3.3.4.3 Minh ho ̣a thuâ ̣t toán 15 15 15 22 22 13 13 22 15 13 22 13 13 15 12 22 13 20 27 20 27 20 27 12 20 22 23 12 24 23 24 23 12 12 23 24 24 23 23 20 12 27 15 12 20 27 13 22 15 27 20 24 23 24 24 27 Trang 18 Đồ án Cấu trúc dữ liệu và Giải thuật 3.3.4.4 Sơ đồ khố i Đầu tiên ta xây dựng sơ đồ khối cho công việc ghép 2 mảng con thành mảng cơ sở: Merge (A, l, m, r) Bắt đầu Mảng cơ sở A, vị trí bắt đầu l, vị trí kết thúc r, vị trí giữa m n1  m-l+1 n2  r-m Mảng L  Mảng con bắt đầu từ vị trí l, có n1 phần tử Mảng R  Mảng con bắt đầu từ vị trí m+1, có n2 phần tử i  0; j  0; k  l i < n1 && j < n2 ? T A[k]  R[j] j++ F L[i] < R[j] ? A[k]  L[i] i++ k++ A[k]  L[i] i++; k++ T i < n1 ? F Kết thúc F j < n2 ? T A[k]  R[j] j++; k++ Trang 19 Đồ án Cấu trúc dữ liệu và Giải thuật Sơ đồ khố i hàm MergeSort(A, l, r): Bắt đầu Mảng cơ sở A, vị trí bắt đầu l, vị trí kết thúc r F l - Xem thêm -

Tài liệu liên quan