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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:33

Thêm vào BST

Báo xấu

24
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 8 KHOA CÔNG NGHỆ THÔNG TIN
CÀI ĐẶT THUẬT TOÁN BUBBLE SORTDãy các đối tượng (Các số): Arr[0], Arr[1],…,Arr[n-1]. Input: Output: Dãy các đối tượng đã được sắp xếp (Các số): Arr[0], Arr[1],…,Arr[n-1] Actions: void BubbleSort(ref a[],int n) 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com { int i, j; for (i = 0 ; i a[j+1])// nếu sai vị trí thì đổi chỗ Swap(a[j], a[j+1]); } End 9 KHOA CÔNG NGHỆ THÔNG TIN
#Giải thuật Nổi bọt - Bubble Sort: B.1: Gán i = 0 B.2: Gán j = 0 //danh sách có n phần tử a0,a1,a2…,an-1 B.3: Nếu A[j] > A[j + 1] thì Hoán đối chỗ giữa A[j] và A[j + 1] 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com B.4: Nếu (j < n – i – 1): -Đúng thì j = j + 1 và quay lui bước 3 -Sai thì chuyển sang bước 5 B.5: Nếu (i < n – 1): -Đúng thì i = i + 1 và quay lui bước 2 -Sai thì dừng Kết Thúc. 10 KHOA CÔNG NGHỆ THÔNG TIN
Bài tập 1: Áp dụng giải thuật sắp xếp Nổi bọt – Bubble Sort. Cho Mảng A = [19,13,6] +B.1: i = 0; B.2: j = 0; B.3: nếu A[j] > A[j+1] (A[0] > A[1]; 19 > 13) thì Hoán đổi giữa 19 và 13 [13,19,6]; B.4: nếu j < (n-i-1) (0 < (2-0-1)) : Đúng thì j = j+1= 0+1= 1 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com và quay lui B.3; +B.3: nếu A[j] > A[j+1] (A[1] > A[2]; 19 > 6) thì Hoán đổi giữa 19 và 6 [13, 6,19]; B.4: nếu j < (n-i-1) (1 < (2-0-1)): Sai thì chuyển sang B.5 B.5: nếu i < (n-1) (0 < 1): Đúng thì i =i+1 = 0 +1 = 1 và quay lại B.2 11 KHOA CÔNG NGHỆ THÔNG TIN
+B.2: j = 0 (i= 1) ; B.3: nếu A[0] > A[1] (13 > 6) thì Hoán đổi giữa 13 và 6 [6, 13,19] ; B.4: Nếu (j < n – i – 1) (0 < 0) : Sai thì chuyển sang B.5 B.5: Nếu (i < n – 1) (1 < 1): Sai thì Dừng Kết thúc. 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ Vậy mảng được sắp xếp là: ibaotu.com [6, 13,19]. 12 KHOA CÔNG NGHỆ THÔNG TIN
Kiểm tra 30’: Áp dụng giải thuật sắp xếp Nổi bọt – Bubble Sort. Thực hiện sắp xếp mảng: A = [39, 25, 16, 20] 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 13 KHOA CÔNG NGHỆ THÔNG TIN
ĐÁNH GIÁ THUẬT TOÁN 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 14 KHOA CÔNG NGHỆ THÔNG TIN
Đánh giá độ phức tạp - thuật toán Bubble Sort void BubbleSort() { int i, j ; for (i = 2; i = i; j--) 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com if (a[j-1] > a[j]) //hoán chuyển swap(&a[j-1], &a[j]); } 15 KHOA CÔNG NGHỆ THÔNG TIN
02. SELECTION SORT • Thuật toán thực hiện sắp xếp dãy các đối tượng bằng cách lặp kiểu chọn. Thuật toán thực hiện sắp xếp dãy các đối tượng bằng cách lặp lại việc tìm kiếm phần tử có giá trị nhỏ nhất từ thành phần chưa được sắp xếp trong mảng và đặt nó vào vị trí đầu tiên của dãy. Trên dãy các đối tượng ban đầu, thuật toán 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com luôn duy trì hai dãy con: - Dãy con đã được sắp xếp: là các phần tử bên trái của dãy. - Dãy con chưa được sắp xếp là các phần tử bên phải của dãy. • Quá trình lặp sẽ kết thúc khi dãy con chưa được sắp xếp chỉ còn lại đúng một phần tử 16 KHOA CÔNG NGHỆ THÔNG TIN
CÁC BƯỚC CỦA THUẬT TOÁN Bước 1: i = 0; Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[N] 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ Bước 3 : Đổi chỗ a[min] và a[i] ibaotu.com Bước 4 : Nếu i < N-1 thì i = i+1; Lặp lại Bước 2; Ngược lại: Dừng. 17 KHOA CÔNG NGHỆ THÔNG TIN
MINH HỌA THUẬT TOÁN • Cho 1 dãy phần tử các giá trị như sau: { 15,2,8,7,3,6,9,17} I=0 15 2 8 7 3 6 9 17 I=1 2 15 8 7 3 6 9 17 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com I=2 2 3 8 7 15 6 9 17 I=3 2 3 6 7 15 8 9 17 I=4 2 3 6 7 15 8 9 17 I=5 2 3 6 7 8 15 9 17 I=6 2 3 6 7 8 9 15 17 18 KHOA CÔNG NGHỆ THÔNG TIN
#minh họa – giải thuật sắp xếp chọn arr[] = 65 – 27 – 16 – 24 - 3 // Tìm phần tử nhỏ nhất trong trong arr[0...4] // và đổi chỗ nó với phần tử đầu tiên [3] – 27 – 16 – 24 – 65 // Tìm phần tử nhỏ nhất trong trong arr[1...4] // và đổi chỗ nó với phần tử đầu tiên của arr[1...4] 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 3 - [16] – 27 – 24 - 65 // Tìm phần tử nhỏ nhất trong trong arr[2...4] // và đổi chỗ nó với phần tử đầu tiên của arr[2...4] 3 – 16 - [24] – 27 – 65 // Tìm phần tử nhỏ nhất trong trong arr[3...4] // và đổi chỗ nó với phần tử đầu tiên của arr[3...4] 3 – 16 – 24 - [27] – 65. 19 KHOA CÔNG NGHỆ THÔNG TIN
#Bài tập: Thực hiện tính toán từng bước theo giải thuật sắp xếp chọn – Selection Sort. Cho mảng: A = [30, 65, 100, 20, 40, 75] 感谢您下载包图网平台上提供的PPT作品，为了您和包图网以及原创作者的利益，请勿复制、传播、销售，否则将承担法律责任！包图网将对作品进行维权，按照传播下载次数进行十倍的索取赔偿！ ibaotu.com 20 KHOA CÔNG NGHỆ THÔNG TIN