Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 5: Phương pháp sắp xếp đơn giản

"Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 5: Phương pháp sắp xếp đơn giản" thông tin đến các bạn những kiến thức về khái niệm và vai trò của sắp xếp; sắp xếp chèn; sắp xếp chọn; sắp xếp nổi bọt.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 5: Phương pháp sắp xếp đơn giản Cấu trúc dữ liệu và giải thuật Bài 5. Phương pháp sắp xếp đơn giản Lecturer: PhD. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com1 Ngo Huu Phuc, Le Quy Don Technical University Bài 5: Các phương pháp sắp xếp đơn giảnNội dung: 6.1. Khái niệm và vai trò của sắp xếp (13) 6.2. Sắp xếp chèn (6) 6.3. Sắp xếp chọn (4) 6.4. Sắp xếp nổi bọt (4)Tham khảo:1. Lecture 16 Introduction to Sorting.htm2. Data Structures and Algorithms Sorting.htm3. Tham khảo bài giảng của TS Nguyễn Nam Hồng2 Ngo Huu Phuc, Le Quy Don Technical University 5.1. Khái niệm và vai trò của sắp xếp5.1.1. Các thuật toán sắp xếp.5.1.2. Vai trò của sắp xếp.5.1.3. Các vấn đề của sắp xếp.5.1.4. Một số ứng dụng của sắp xếp.5.1.5. Ý tưởng sắp xếp và phương pháp thực hiện.5.1.6. Phân tích hiệu quả của giải thuật sắp xếp.3 Ngo Huu Phuc, Le Quy Don Technical University 5.1.1. Các thuật toán sắp xếp (1/2) Thế nào là sắp xếp?  Đưa một dãy các đối tượng về dạng thứ bậc nào đó. Giải thuật sắp xếp dựa trên sự so sánh nào đó.  Việc sắp xếp chỉ dựa trên phép toán so sánh. Các phép toán cơ bản của sắp xếp.  So sánh.  Tráo đổi giữa các phần tử.4 Ngo Huu Phuc, Le Quy Don Technical University 5.1.1. Các thuật toán sắp xếp (1/2) Quy ước.  Phương pháp sắp xếp của chương này là sắp xếp trong.  Các giải thuật có thể thay thế cho nhau được.  Mỗi mảng có một số phần tử.  Thành phần để xem xét trong sắp xếp có thể so sánh được.  N là số phần tử cần sắp xếp.5 Ngo Huu Phuc, Le Quy Don Technical University 5.1.2. Vai trò của sắp xếp (1/2) Nếu các đối tượng trong một mảng nào đó đã được sắp theo trật tự nào đó, có thể truy xuất thông tin nhanh chóng và chính xác. Việc xây dựng giải thuật cho phép sắp xếp từng phần tử của mảng sẽ mất nhiều thời gian, độ phức tạp của giải thuật cỡ O(n2).  ≈ 50,000,000,000,000 bước cho việc sắp một mảng có 10,000,000 phần tử ⇒ 500,000 giây = 58 ngày, v ới máy tính có thể thực hiện 100 triệu phép tính toán/giây. Với giải thuật sắp xếp cho cả mảng, độ phức tạp của giải thuật cỡ O(nlogn).  ≈ 250,000,000 bước cho việc sắp một mảng có 10,000,000 phần tử ⇒ 2.5 giây, với máy tính có thể thực hiện 100 triệu phép tính toán/giây.6 Ngo Huu Phuc, Le Quy Don Technical University 5.1.2. Vai trò của sắp xếp (2/2) Như vậy, sắp xếp là giải thuật cơ bản. Thông thường, 25% khả năng của CPU dành cho việc sắp xếp. Sắp xếp là bước cơ bản cho một số giải thuật khác, ví dụ: tìm kiếm nhị phân. Có nhiều cách tiếp cận đến giải thuật sắp xếp, từ đó, có nhiều giải thuật săp xếp khác nhau.7 Ngo Huu Phuc, Le Quy Don Technical University 5.1.3. Các vấn đề của sắp xếp Sắp xếp theo trật tự tăng hay giảm?  Với cùng một giải thuật sắp xếp, có thể dùng cho cả sắp theo trật tăng hay giảm, bằng việc thay đổi phép so sánh: =. Các khóa của giải thuật sắp xếp?  Có thể dùng nhiều khóa cho cùng một giải thuật sắp xếp. Cần lưu ý đến ý tưởng của bài toán. Với các dữ liệu không phải là số thì sao? Với chuỗi, sử dụng phép so sánh chuỗi, từ điển, hay quy tắc nào đó. Ví dụ: Sắp chuỗi Brown-Williams, Brown America, Brown, John?8 Ngo Huu Phuc, Le Quy Don Technical University 5.1.4. Một số ứng dụng của sắp xếp (1/2) Với kết quả của quá trình sắp xếp, một số vấn đề có thể được thực hiện dễ dàng. Nói chung, nếu có quá trình sắp xếp sẽ tăng tốc cho tìm kiếm trong ứng dụng cụ thể. Ví dụ, nếu có một mảng đã sắp, có thể dễ dàng tìm được phần tử lớn thứ k trong mảng, với thời gian hằng số.9 Ngo Huu Phuc, Le Quy Don Technical University 5.1.4. Một số ứng dụng của sắp xếp (2/2) Một số ứng dụng có dùng sắp xếp.  Các từ trong từ điển đã được sắp xếp.  Thông thường, các Files trong thư mục được sắp theo một trật tự nào đó.  Trong thư viện, các quyển sách được sắp theo một trật tự nào đó.  Các khóa học của một trường đại học được sắp theo khoa, theo mã của khóa học.  Các sự kiện được sắp theo thời gian.  …10 Ngo Huu Phuc, Le Quy Don Technical University 5.1.5. Ý tưởng sắp xếp và phương pháp thực hiện (1/2) Có nhiều ý tưởng cho giải thuật sắp xếp:  Chèn - Insertion: đặt các phần tử vào một vị trí thích hợp của một dãy các phần tử đã sắp.  Tráo đổi - Exchange: với mỗi cặp các phần tử, tráo đổi chúng về đúng thứ tự, thực hiện cho đến khi không còn cặp nào chưa đưa về đúng thứ tự.  Chọn - Selection: chọn phần tử lớn nhất (nhỏ nhất) trong danh sách, đưa về đúng vị trí.  Phân loại - Distribution: chia nhỏ thành nhiều mảnh dựa trên tiêu chí nào đó, sau đó sắp từng mảnh.  Hợp - Merging: có thể nối 2 dãy đã sắp xếp thành 1 dãy được sắp xếp.11 Ngo Huu Phuc, Le Quy Don Technical University 5.1.5. Ý tưởng sắp xếp và phương pháp thực hiện (2/2) Phương pháp sắp xếp:  Sắp xếp chọn:  Tìm phần tử lớn nhất (nhỏ nhất) trong số các phần tử chưa xét và đặt chúng vào đúng vị trí.  Thực hiện cho đến khi các phần tử đều được xét.  Sắp xếp chèn:  Với mỗi phần tử, chèn chúng vào mảng con đã sắp đúng trật tự.  Thực hiện tương tự cho các phần tử còn lại.  So sánh và tráo đổi – Sắp xếp nổi bọt:  Tìm 2 phần tử trong dãy không đúng trật tự, tráo đổi vị trí của chúng.  Giữ lại danh sách đã hiệu chỉnh.12 Ngo Huu Phuc, Le Quy Don Technical University 5.1.6. Phân tích hiệu quả của giải thuật sắp xếp (1/2) ...