Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - Trường ĐH Văn Lang

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 Các giải thuật sắp xếp, cung cấp cho người học những kiến thức như: Giới thiệu về sắp xếp; bài toán sắp xếp; các thuật toán sắp xếp đơn giản; các bước thuật toán; đánh giá thuật toán. Mời các bạn cùng tham khảo!
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: Chương 3 - Trường ĐH Văn Lang KHOA CÔNG NGHỆ THÔNG TIN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (Data Structures And Algorithms) BÀI 3: CÁC GIẢI THUẬT SẮP XẾP GIỚI THIỆU ▪ Sắp xếp là gì? Trong thực tế chúng ta đã từng thấy những thứ gì được sắp xếp? Giá trị của việc sắp xếp mang lại là gì? - Danh sách học sinh trong lớp 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com - Danh sách xếp hạng điểm người chơi - Các sản phẩm trên thương mại điện tử - Tra cứu từ điển ▪ Trong phần này các thuật toán sắp xếp sẽ dùng các số nguyên để biểu diễn. 2 KHOA CÔNG NGHỆ THÔNG TIN BÀI TOÁN SẮP •XẾP Cho danh sách có n phần tử a0, a1, a2…, an-1. • Sắp xếp là quá trình xử lý các phần tử trong danh sách để đặt chúng theo một thứ tự thỏa mãn một số tiêu chuẩn nào đó dựa trên thông tin lưu tại mỗi phần tử, 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com như: - Sắp xếp danh sách lớp học tăng theo điểm trung bình. - Sắp xếp danh sách sinh viên tăng theo tên. • Để đơn giản trong việc trình bày giải thuật ta dùng mảng 1 chiều a để lưu danh sách trên trong bộ nhớ chính. 3 KHOA CÔNG NGHỆ THÔNG TIN BÀI TOÁN SẮP XẾP a:(tt) là dãy các phần tử dữ liệu Để sắp xếp dãy a theo thứ tự (giả sử theo thứ tự tăng), ta tiến hành triệt tiêu tất cả các nghịch thế trong a. ▪Nghịch thế: •Cho dãy có n phần tử a0, a1,…,an-1 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com •Nếu iaj 34 3 4 8 a[0], a[1] là cặp nghịch thế Đánh giá độ phức tạp của giải thuật, ta tính Css: Số lượng phép so sánh cần thực hiện CHV: Số lượng phép hoán vị cần thực hiện 4 KHOA CÔNG NGHỆ THÔNG TIN CÁC THUẬT TOÁN SẮP XẾP ĐƠN ▪GIẢN Các thuật toán sắp xếp được trình bày ở đây gồm: - Thuật toán sắp xếp kiểu sủi bọt (Bubble Sort) - Thuật toán sắp xếp kiểu lựa chọn (Selection Sort) 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com - Thuật toán sắp xếp kiểu chèn (Insertion Sort) 5 KHOA CÔNG NGHỆ THÔNG TIN 01. BUBBLE SORT ▪ Xuất phát từ đầu dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn trong cặp phần tử đó về vị trí đứng đầu dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com dãy là i. ▪ Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét. 6 KHOA CÔNG NGHỆ THÔNG TIN CÁC BƯỚC THUẬT TOÁN Bước 1 : i = 0; // lần xử lý đầu tiên Bước 2 : j = 0;//Duyệt từ đầu dãy về cuối vị trí N-1 Trong khi (j < N-1) thực hiện: Nếu a[j]>a[j+1] 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com Doicho(a[j],a[j+1]); j = j+1; Bước 3 : i = i+1; // lần xử lý kế tiếp Nếu i >=N-1: Hết dãy. Dừng Ngược lại : Lặp lại Bước 2. 7 KHOA CÔNG NGHỆ THÔNG TIN MINH HỌA THUẬT TOÁN • Cho 1 dãy các phần tử như sau: {5, 1, 6, 2, 4, 3} Lượt 1(i=0) Lượt 2(i=1) Lượt 3(i=2) 5 1 6 2 4 3 1 5 2 4 3 6 1 2 4 3 5 6 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ 1 5 6 2 4 3 1 ibaotu.com 2 5 4 3 6 1 2 3 4 5 6 1 5 2 6 4 3 1 2 4 5 3 6 1 2 3 4 5 6 1 5 2 4 6 3 1 2 4 3 5 6 1 2 3 4 5 6 1 5 2 4 3 6 1 2 4 3 5 6 1 2 3 4 5 6 ...