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

Chia sẻ: Minh Nhân | Ngày: | Loại File: PDF | Số trang:38

Thêm vào BST

Báo xấu

40
lượt xem 4
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: 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.

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: Sắp xếp - Phan Mạnh Hiển (2020)

Sắp xếp (Sorting) Nguyễn Mạnh Hiển hiennm@tlu.edu.vn
Nội dung 1. Sắp xếp chọn 2. Sắp xếp nổi bọt 3. Sắp xếp chèn 4. Sắp xếp vun đống 5. Sắp xếp trộn 6. Sắp xếp nhanh
1. 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ọn template 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 ) 2
2. 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ọt template 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èn
Cài đặt sắp xếp chèn template void insertionSort(vector & a) { int j; for (int p = 1; p < a.size(); p++) { T tmp = a[p]; for (int j = p; j > 0; j--) { if (tmp < a[j-1]) a[j] = a[j-1]; else break; } a[j] = tmp; } }
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 𝑝=1
4. 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