Cấu trúc dữ liệu và giải thuật - Các thuật toán sắp xếp

Nội dung text: Cấu trúc dữ liệu và giải thuật - Các thuật toán sắp xếp

1. Các thuật toán sắp xếp (p1) (sorting algorithms) Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn
2. Các thuật toán sắp xếp - phần 1 • Sắp xếp chọn (selection sort) • Sắp xếp nổi bọt (bubble sort) • Sắp xếp chèn (insertion sort)
3. Sắp xếp chọn (selection sort) • Cho 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 1: USL = {a0, a1, , aN-1} − Bước 2: USL = {a1, , aN-1} − − Bước N-1: USL = {aN-2, aN-1}
4. 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 của USL sang phải một phần tử
5. Sắp xếp chọn: Ví dụ • Ban đầu: 64, 25, 12, 22, 11 • Sau bước 1: 11, 25, 12, 22, 64 • Sau bước 2: 11, 12, 25, 22, 64 • Sau bước 3: 11, 12, 22, 25, 64 • Sau bước 4: 11, 12, 22, 25, 64 (danh sách con chưa sắp xếp được gạch chân)
6. Cài đặt và phân tích sắp xếp chọn • Viết hàm selectionSort() • Chứng minh thời gian chạy là O(N2)
7. Sắp xếp nổi bọt (bubble sort) • Mỗi bước: − So sánh hai phần tử kề nhau − Đổ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 • Thời gian chạy: O(N2)
8. Sắp xếp nổi bọt: Ví dụ • Ban đầu: 2, 3, 1, 15 • Sau bước 1: 2, 1, 3, 15 • Sau bước 2: 1, 2, 3, 15 • Sau bước 3: 1, 2, 3, 15 (danh sách con chưa sắp xếp được gạch chân)
9. Sắp xếp nổi bọt: Cài đặt for (i = 0; i < N-1; i++) { for (j = 0; j < N-1-i; j++) if (a[j+1] < a[j]) { tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; } } • Trong trường hợp tốt nhất (dãy đã sắp xếp rồi), sắp xếp nổi bọt chỉ nên mất thời gian O(N) hãy tối ưu hóa cài đặt bên trên!
10. Sắp xếp chèn (insertion sort) • 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ử ở vị trí p (ap) − Chèn ap vào vị trí đã xác định, vì vậy các vị trí từ 0 đến p được sắp xếp
11. Sắp xếp chèn: Ví dụ
12. Sắp xếp chèn: Cài đặt
13. Phân tích sắp xếp chèn • Trường hợp tốt nhất: O(N) • Trường hợp tồi nhất: O(N2)