Bài giảng Hệ thống thông tin: Bài 3 Các thuật toán sắp xếp, cung cấp cho người học những kiến thức như: Bài toán sắp xếp; Tiếp cận sắp xếp đơn giản; Tiếp cận sắp xếp độ phức tạp O(nlog(n)); Một số tiếp cận khác. Mời các bạn cùng tham khảo! | Giới thiệu Các thuật toán sắp xếp 08 02 2014 1 Nội dung trình bày Bài toán sắp xếp Tiếp cận sắp xếp đơn giản Sắp xếp chọn Sắp xếp chèn Sắp xếp nổi bọt Tiếp cận sắp xếp độ phức tạp O nlog n Sắp xếp theo phân đoạn Quick sort Sắp xếp hòa nhập Sắp xếp vung đống Một số tiếp cận khác Sắp xếp theo cơ số Sắp xếp hòa nhập hai file lớn 08 02 2014 2 Bài toán sắp xếp Cho một dãy dữ liệu có thể so sánh được theo tiêu chí so sánh Sắp xếp các phần tử mảng theo thứ tự không giảm không tăng Ví dụ Cho danh sách các mức xám của các điểm ảnh sắp xếp theo thứ tự không tăng của các mức xám Cho danh sách sinh viên sắp xếp sinh viên theo thứ tự không giảm theo ngày sinh 08 02 2014 3 Đánh giá ứng dụng Tính ứng dụng Bài toán lựa chọn theo thứ tự nào đó là bài toán sắp xếp theo tiêu chí Nhiều thuật toán thực hiện hiệu quả trên những bộ dữ liệu đã được sắp xếp theo xu hướng Đặc điểm Phải có tiêu chí so sánh lớn hơn bé hơn được Có thể so sánh một số thành phần của đối tượng để xác định tiêu chí Tính hiệu quả thuật toán phụ thuộc vào độ phức tạp của phép so sánh và hoán đổi vị trí Một số thuật toán độ phức tạp về bộ nhớ cũng là vấn đề trong dữ liệu lớn 08 02 2014 4 Phân loại theo độ phức tạp Thuật toán đơn giản O n2 Sắp xếp chọn Sắp xếp chèn Sắp xếp nổi bọt Sắp xếp theo phương pháp chia để trị O nlog n Sắp xếp phân đoạn Sắp xếp trộn Sắp xếp vun đống Sắp xếp theo phương pháp O n Sắp xếp theo cơ số 08 02 2014 5 Sắp xếp chọn selection sort - Sắp xếp dãy không giảm - 1 7 3 8 2 6 4 1 2 3 4 6 7 8 08 02 2014 6 Sắp xếp chọn t Ý tưởng Chọn phần tử bé nhất đổi chổ đưa lên đầu Tiếp theo chọn phần tử bé thứ 2 đưa lên vị trí thứ hai Chọn phần tử bé thứ k đưa đến vị trí thứ k Lặp lại đến phần tử thứ N-1 08 02 2014 7 Sắp xếp chọn t Phát biểu lại Chọn phần tử bé nhất đổi chổ đưa lên đầu Giả sử có k phần tử ở đầu đã được sắp xếp Tìm phần tử bé nhất từ k 1 đến n đổi chổ cho phần tử tại k 1. Lặp tương tự cho đến phần tử N-1 08 02 2014 8 Sắp xếp chọn t Thuật toán Input A Output A đã được sắp xếp không
