Bài giảng Độ phức tạp thuật toán - Bài 5: Sắp xếp (Phần 2) - Lê Sỹ Vinh

Nội dung text: Bài giảng Độ phức tạp thuật toán - Bài 5: Sắp xếp (Phần 2) - Lê Sỹ Vinh

1. Sp xp (ph n 2) Lê S Vinh B môn Khoa Hc Máy Tính – Khoa CNTT i Hc Công Ngh - HQGHN Email: vinhbio@gmail.com
2. Bài toán s p x p Input: Danh sách các i t ng A = (a 0, ,a n) Problem: i ch các ph n t thu c m t danh sách m i, trong ó các ph n t c s p x p theo m t th t nào ó Output: A’ = (a’ 0, ,a’ n) | a’ i < a’ i+1 , i = 0 n - 1 Ví d : A = (1 , 5, 0, 3) (0, 1, 3, 5) A = (‘Vinh’, ‘Tuan’, ‘Anh’) (‘Anh’, ‘Vinh’, ‘Tuan)
3. Sp x p nhanh (Quick sort) Tư t ưở ng c ủa Quick sort: Phân chia danh sách d li u c n s p x p ra thành hai ph n “ph n bên trái” và “ph n bên ph i” sao cho các ph n t ph n bên trái nh h ơn ho c b ng các ph n t ph n bên ph i. Sau khi phân chia, ti p t c th c hi n “quick sort trên hai ph n d li u trên. C th h ơn, g i “pivot” là ph n t trung tâm c a danh sách, các ph n t nh h ơn ho c b ng “pivot” thi n m bên trái “pivot”, các ph n t l n h ơn ho c b ng “pivot” thì n m bên ph i “pivot”
4. Quick sort Void quickSort (Item A[], int start, int end) { if (start < end) { pivotLocation = partition (A, start, end); quickSort (A, start, pivotLocation – 1); quickSort (A, pivotLocation + 1, end) } }
5. Partition (A, start, end) Tư t ưở ng phân chia: Danh sách g m ba ph n: – Ph n bên trái (các giá tr nh h ơn pivot) – Ph n bên ph i (các giá tr l n h ơn pivot) – Ph n gi a ch a c phân chia Duy t trên danh sách m r ng d n ph n bên trái và ph n bên ph i, ng th i thu hp ph n ch a c phân chia, cho n khi ph n ch a c phân chia b ng rng.
6. Partition (A, start, end) Kh ởi t ạo: Ph n bên trái và ph n bên b ng r ng. Ph n ch a c phân chia t v trí start → end. Xác nh pivot = A[start] Bướ c 1: Duy t t trái sang ph i c a ph n ch a c phân chia, n u ph n t hi n t i nh h ơn ho c b ng pivot thì m r ng ph n bên trái và thu h p ph n ch a c phân chia, n u không d ng l i. Bướ c 2: Duy t t ph i sang tr i c a ph n ch a c phân chia, n u ph n t hi n t i l n h ơn ho c b ng pivot thì m r ng ph n bên ph i và thu h p ph n ch a c phân chia, n u không d ng l i. Bướ c 3: i ch ph n t bên trái nh t và ph n t bên ph i nh t c a ph n ch a c phân chia. M r ng ph n bên trái và ph n bên ph i, ng th i thu h p hai u c a ph n ch a c phân chia. Bướ c 4: Nu ph n ch a c phân chia khác r ng thì quay l i B c 1. Bướ c 5: Chuy n pivot vào úng v trí
7. Ví d ụ Sp x p dãy s sau b ng quick sort • 3 1 4 5 9 2 6 8 7
8. Tr ng h p t t nh t T(n) = O( n log n)
9. Tr ng h p t i nh t T(n) = O( n2)
10. Nh ận xét v ề quick sort - Th i gian trung bình: O(n log n) - Là m t thu t toán s p x p nhanh nh t trong th c t
11. Bucket sort 1, c 3, a 3, b 7, d 7, g 7, e ∅ ∅ ∅ ∅ ∅ ∅ ∅ B 0 1 2 3 4 5 6 7 8 9