Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 14: Các thuật toán sắp xếp (P1) - Nguyễn Mạnh Hiển

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 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) 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} 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ử 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) 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) 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) 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) 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! 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 Sắp xếp chèn: Ví dụ Sắp xếp chèn: Cài đặt 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)