Bài giảng Cấu trúc dữ liệu và giải thuật: Sắp xếp - Nguyễn Mạnh Hiển (HKI năm 2020-2021)

Bài giảng "Cấu trúc dữ liệu và giải thuật: Sắp xếp" cung cấp cho người học các kiến thức: Sắp xếp chọn, sắp xếp nổi bọt, sắp xếp chèn, sắp xếp vun đống, sắp xếp trộn, sắp xếp nhanh. Mời các bạn cùng tham khảo nội dung chi tiế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: Sắp xếp - Nguyễn Mạnh Hiển (HKI năm 2020-2021)Sắp xếp(Sorting)Nguyễn Mạnh Hiểnhiennm@tlu.edu.vnNội dung1. Sắp xếp chọn2. Sắp xếp nổi bọt3. Sắp xếp chèn4. Sắp xếp vun đống5. Sắp xếp trộn6. Sắp xếp nhanh1. Sắp xếp chọn (selection sort)Sắp xếp chọn• Dãy A gồm n phần tử a0, a1, …, an-1.• Mỗi bước xét một danh sách con chưa sắp xếp (unsorted sublist - USL).• Có n-1 bước: − Bước 0: USL0 = {a0, a1, …, an-1} − Bước 1: USL1 = {a1, …, an-1} … − Bước n-2: USLn-1 = {an-2, an-1}Sắp xếp chọn (tiếp)• Mỗi bước: − Tìm phần tử nhỏ nhất amin trong USL. − Đổi chỗ amin và phần tử đầu tiên của USL. − Dịch chuyển biên trái của USL sang phải một vị trí.Ví dụ sắp xếp chọn• Ban đầu: 64, 25, 12, 22, 11 (11  64)• Sau bước 0: 11, 25, 12, 22, 64 (12  25)• Sau bước 1: 11, 12, 25, 22, 64 (22  25)• Sau bước 2: 11, 12, 22, 25, 64 (25  25)• Sau bước 3: 11, 12, 22, 25, 64 (Danh sách con chưa sắp xếp được gạch chân)Cài đặt sắp xếp chọntemplate void selectionSort(vector & a) { for (int i = 0; i < a.size() - 1; i++) { int vt = i; // Vị trí của min for (int j = i + 1; j < a.size(); j++) if (a[vt] > a[j]) vt = j; // Cập nhật vị trí của min if (vt != i) { // Đổi chỗ min và phần tử đầu USL T tg = a[vt]; a[vt] = a[i]; a[i] = tg; } }}Phân tích sắp xếp chọn• Đếm số phép so sánh a[vt] > a[j].• Vòng for bên trong lặp với j từ i+1 đến n-1, tức là có n-1-i phép so sánh.• Vòng for bên ngoài lặp với i từ 0 đến n-2. ?−2 ? ? = ෍ ? − 1 − ? = ? − 1 + ? − 2 + ⋯+ 1 ?=0 ? ?−1 = = ?(?2 ) 22. Sắp xếp nổi bọt (bubble sort)Sắp xếp nổi bọt• Mỗi bước duyệt qua các phần tử a0, a1, …, ak.• Tại mỗi phần tử ai (i < k): − So sánh ai với ai+1 − Đổi chỗ nếu chúng chưa đúng thứ tự• Sau mỗi bước, phần tử lớn nhất sẽ được đặt (“nổi bọt”) xuống cuối dãy (ak là max).Ví dụ sắp xếp nổi bọt• Ban đầu: 64, 25, 12, 22, 11 (k = n-1-0)• Sau bước 0: 25, 12, 22, 11, 64 (k = n-1-1)• Sau bước 1: 12, 22, 11, 25, 64 (k = n-1-2)• Sau bước 2: 12, 11, 22, 25, 64 (k = n-1-3)• Sau bước 3: 11, 12, 22, 25, 64 (Danh sách con chưa sắp xếp được gạch chân)Cài đặt sắp xếp nổi bọttemplate void bubbleSort(vector & a) { for (int i = 0; i < a.size()-1; i++) { // Bước i for (int j = 0; j < a.size()-1-i; j++) { if (a[j] > a[j+1]) { T tg = a[j]; a[j] = a[j+1]; a[j+1] = tg; } } }}Phân tích sắp xếp nổi bọt• Đếm số phép so sánh a[j] > a[j+1].• Vòng for bên trong lặp với j từ 0 đến n-2-i, tức là có n-1-i phép so sánh.• Vòng for bên ngoài lặp với i từ 0 đến n-2. ?−2 ? ? = ෍ ?−1−? ?=0 ? ?−1 = ? − 1 + ? − 2 + ⋯+ 1 = 2 = ?(?2 )3. Sắp xếp chèn (insertion sort)Sắp xếp chèn• Có n-1 bước ứng với p = 1, 2, …, n-1.• Ở bước p: (Khi bắt đầu bước p, các vị trí 0, …, p-1 đã được sắp xếp rồi) − Xác định vị trí phù hợp trong các vị trí 0, …, p-1 cho phần tử ap đang nằm ở vị trí p. − Chèn ap vào vị trí đã xác định được, vì vậy các vị trí từ 0 đến p được sắp xếp.Ví dụ sắp xếp chènCài đặt sắp xếp chèntemplate void insertionSort(vector & a) { int j; for (int p = 1; p < a.size(); p++) { T tmp = a[p]; // Lay ra phan tu can chen for (j = p; j > 0; j--) { // j: vi tri don nhan if (tmp < a[j-1]) a[j] = a[j-1]; // Dich ve phia sau else break; } a[j] = tmp; // Dat phan tu can chen }}Phân tích sắp xếp chèn• Đếm số phép so sánh tmp < a[j-1].• Trong trường hợp tồi nhất, vòng for bên trong lặp với j từ p giảm dần về 1, tức là có p phép so sánh.• Vòng for bên ngoài lặp với p từ 1 đến n-1. ?−1 ? ?−1 ? ? = ෍? = = ?(?2 ) 2 ?=14. Sắp xếp vun đống (heap sort)Sắp xếp vun đống• Các bước thực hiện: − Xây dựng đống từ dãy n phần tử đã cho (dùng buildHeap)  mất thời gian O(n). − Thực hiện n lần cặp thao tác findMin/deleteMin để lấy ra lần lượt các phần tử từ nhỏ nhất đến lớn nhất  mất thời gian O(n log n).• Thời gian chạy tổng thể: O(n log n).• Nhược điểm: Yêu cầu thêm một vector nữa để lưu trữ các phần tử được rút ra từ đống. ...