Cấu trúc dữ liệu & Giải thuật (Data Structures and Algorithms) Các thuật toán sắp xếp (Sorting algorithms) Sắp xếp 1 mảng các số nguyên • Giả sử có 1 mảng gồm 6 70 số nguyên. 60 Ta cần sắp 50 xếp các phần 40 tử của mảng 30 theo thứ tự 20 tăng dần 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 2 Thuật toán “Chọn trực tiếp” (Selection sort Algorithm) • Bắt đầu bằng cách tìm 70 phần tử nhỏ 60 nhất 50 40 30 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 3 Selection sort Algorithm • Hoán vị phần tử nhỏ 70 nhất tìm 60 được với 50 phần tử đầu 40 tiên của 30 mảng 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 4 Selection sort Algorithm Phần đã sắp Phần chưa sắp 70 • 1 phần của 60 mảng đã 50 được sắp 40 xếp 30 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 5 Selection sort Algorithm Phần đã sắp Phần chưa sắp 70 • Tìm phần tử 60 nhỏ nhất 50 trong phần 40 chưa được 30 sắp 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 6 Selection sort Algorithm Phần đã sắp Phần chưa sắp 70 • Hoán vị phần 60 tử nhỏ nhất 50 trong phần 40 chưa được 30 sắp với phần 20 tử đầu tiên 10 trong phần 0 này [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 7 Selection sort Algorithm Phần đã sắp Phần chưa sắp 70 • Phần đã 60 được sắp 50 xếp của 40 mảng được 30 tăng thêm 1 20 phần tử 10 0 [1] [2] [3] [4] [5] [6] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 8 Selection sort Algorithm Phần đã sắp Phần chưa sắp 70 • Tiếp tục 60 tương tự. 50 Phần tử nhỏ nhất 40 30 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 9 Selection sort Algorithm Phần đã sắp Phần chưa sắp 70 • Tiếp tục 60 tương tự. 50 40 30 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 10 Selection sort Algorithm Phần đã sắp Phần đã sắp Phần chưa sắp tăng thêm 70 • Tiếp tục 60 tương tự.
50 40 30 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 11 Selection sort Algorithm • Quá trình lần Phần đã sắp Phần chưa sắp lượt thêm từng 70 phần tử vào 60 phần đã sắp… 50 • Phần đã sắp 40 chứa các phần 30 tử nhỏ nhất, sắp 20 tăng dần 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 12 Selection sort Algorithm • Thuật toán Phần đã sắp Phần chưa … dừng khi chỉ 70 còn 1 phần tử 60 (đó là phần tử 50 lớn nhất). 40 30 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 13 Selection sort Algorithm • Toàn bộ mảng đã được sắp 70 thứ tự. 60 • Tổng quát: chọn 50 phần tử nhỏ 40 nhất và đưa nó 30 về vị trí đầu của 20 phần chưa được 10 sắp trong mảng. 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 14 Selection sort Algorithm (Minh họa chương trình) void SelectionSort (int a[ ], int n ) { int min; // vị trí của phần tử nhỏ nhất (trong phần chưa sắp) int tmp; // biến tạm dùng khi hoán vị for (int i = 0; i < n; i++ ) { // tìm phần tử nhỏ nhất trong phần chưa sắp min = i; for (int j = i + 1; j < n; j++) if (a[j] < a[min] ) min = j; // hoán vị phần tử nhỏ nhất được tìm thấy với phần tử đầu if (a[min] < a[i]) { tmp = a[i]; a[i] = a[min]; a[min] = tmp; } } // end of for i } 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 15 Đánh giá thuật toán (Selection sort Algorithm) • Trong mọi trường hợp, số phép so sánh là: (n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n2) • Số phép hoán vị: – Trường hợp xấu nhất: O(n) – Trường hợp tốt nhất (mảng đã sắp tứ tự tăng dần): 0 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 16 Thuật toán “Chèn trực tiếp” (Insertion sort Algorithm) • Thuật toán “Chèn trực 70 tiếp” cũng 60 chia mảng 50 thành 2 40 phần: phần 30 đã được sắp 20 và phần 10 chưa được 0 sắp [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 17 Insertion sort Algorithm Phần đã sắp Phần chưa sắp • Phần đã sắp 70 lúc đầu chỉ 60 có 1 phần tử 50 đầu tiên của 40 mảng 30 (không cần 20 thiết là phần 10 tử nhỏ nhất) 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 18 Insertion sort Algorithm Phần đã sắp Phần chưa sắp 70 • Mở rộng 60 phần đã sắp 50 bằng cách thêm vào 40 phần tử đầu 30 tiên trong 20 phần chưa 10 được sắp… 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 19 Insertion sort Algorithm Phần đã sắp Phần chưa sắp • .và đặt nó 70 vào vị trí 60 thích hợp, 50 sao cho 40 phần đã sắp 30 vẫn giữ 20 nguyên tính 10 thứ tự (tăng 0 [1] [2] [3] [4] [5] [6] dần).
[0] [1] [2] [3] [4] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 20 Insertion sort Algorithm Phần đã sắp Phần chưa sắp • Trong ví dụ 70 này, phần tử 60 mới được 50 đặt vào vị trí 40 đầu của 30 phần đã sắp. 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 21 Insertion sort Algorithm Phần đã sắp Phần chưa sắp • Đôi khi 70 chúng ta 60 “gặp may”, 50 phần tử mới 40 không cần 30 phải di 20 chuyển. 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 22 Insertion sort Algorithm Phần đã sắp Phần chưa sắp • … và lại “gặp 70 may” thêm 60 1 lần nữa. 50 40 30 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 23 Insertion sort Algorithm Làm sao để chèn 1 phần tử ? Copy phần Phần đã sắp Phần chưa sắp tử mới vào 1 70 biến trung 60 gian… 50 40 30 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 24 Insertion sort Algorithm Làm sao để chèn 1 phần tử ? …Dịch chuyển các 70 phần tử 60 trong phần 50 đã sắp sang 40 phải… 30 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 25 Insertion sort Algorithm Làm sao để chèn 1 phần tử ? …để tạo 1 chỗ trống 70 cho phần tử 60 mới… 50 40 30 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 26 Insertion sort Algorithm Làm sao để chèn 1 phần tử ? …tiếp tục dịch chuyển 70 các phần 60 tử.
50 40 30 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 27 Insertion sort Algorithm Làm sao để chèn 1 phần tử ? …tiếp tục dịch chuyển 70 các phần 60 tử. 50 40 30 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 28 Insertion sort Algorithm Làm sao để chèn 1 phần tử ? .cho đến khi tìm thấy 70 vị trí thích 60 hợp cho 50 phần tử 40 mới. 30 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 29 Insertion sort Algorithm Làm sao để chèn 1 phần tử ? Copy phần Phần đã sắp Phần chưa… tử mới vào 70 lại mảng, tại 60 vị trí này. 50 40 30 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 30 Insertion sort Algorithm Làm sao để chèn 1 phần tử ? • Phần tử Phần đã sắp Phần chưa… cuối cùng 70 cũng phải 60 “chèn”.
50 Copy nó vào 40 1 biến trung 30 gian. 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 31 Insertion sort Algorithm Câu hỏi ? Có bao nhiêu phép dịch 70 chuyển xảy ra 60 ? 50 40 30 20 10 0 [1] [0] [2] [1] [3] [2] [4] [3] [5] [4] [6] [5] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 32 Insertion sort Algorithm Câu hỏi ? • Có 4 phép dịch chuyển 70 … 60 50 40 30 20 10 0 [1] [2] [3] [4] [5] [6] 09/2013 Data Structures & Algorithms - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.