om du on g th an co ng .c Phần 3: Cấu trúc dữ liệu và giải thuật cu u Chương 12: Các giải thuật sắp xếp 1 Nội dung chính Đặt vấn đề Các giải thuật sắp xếp cơ bản ng .c 1. om   co Sắp xếp chọn (selection sort) Sắp xếp nổi bọt (bubble sort) Sắp xếp chèn (insertion sort) th an  du on g 2. Các giải thuật sắp xếp nâng cao    Sắp xếp nhanh (quick sort) Sắp xếp vun đống (heap sort) Sắp xếp trộn (merge sort) cu u 3. Trường ĐHBK Hà nội Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 2 Đặt vấn đề om .c  Yêu cầu: Bài toán tổng quát: Cho trước một dãy N phần tử a1, a2, …, aN. Ta cần tìm giải thuật sắp xếp các phần tử của dãy trên trên một thứ tự nào đó theo một tiêu chuẩn nào đó.  Bài toán đơn giản: Không giảm tính tổng quát của các giải thuật sắp xếp, đồng thời để đơn giản hóa việc trình bầy, sau này ta sẽ minh họa các giải thuật thông qua việc sắp xếp một dãy N số theo trật tự tăng dần. cu u du on g th an co ng  Trường ĐHBK Hà nội Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 3 Đặt vấn đề Sorting Algorithm? a’1,a’2,…,a’N th an co a1,a2,…,aN ng .c om du on g  Với mỗi giải thuật, sẽ đưa ra: Ý tưởng giải thuật  Cài đặt cơ bản (gồm 1 hoặc 1 số hàm) cu u  Trường ĐHBK Hà nội Khoa Điện tử Viễn thông Bộ môn Điện tử Tin học 4 Các giải thuật sắp xếp cơ bản .c Giới thiệu chung: Các GTSX cơ bản đều có chung ý tưởng là ở mỗi bước, chỉ tập trung vào việc đưa từng phần tử của dãy cần SX vào đúng vị trí của nó trong dãy kết quả, mà không cần quan tâm đến vị trí của các phần tử khác  Với các GTSX nâng cao, mỗi bước của giải thuật không chỉ