Bài giảng Độ phức tạp thuật toán - Bài 5: Sắp xếp - 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 - Lê Sỹ Vinh

1. Sp x p (sorting) Lê S Vinh B môn Khoa Hc Máy Tính – Khoa CNTT i Hc Công Ngh - HQGHN Email: vinhioi@yahoo.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 mt danh sách mi, trong ó các ph n t c sp xp theo mt 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 n i b t Thu t toán: Ln l t duy t qua danh sách, nu hai ph n t li n k ng không úng th t thì i ch . Lp li quá trình trên cho n khi danh sách c sp xp. Ví d: Sp tng dn dãy s A = (9, 7, 6, 2) (9, 7, 6, 2 ) (9, 7, 2 , 6) ( 9, 2 , 7, 6) (2, 9, 7, 6) (2, 9, 7, 6 ) (2, 9, 6 , 7) (2, 6, 9, 7) (2, 6, 9, 7 ) (2, 6, 7, 9) Ví d 2, 3, 5: Ch ươ ng trình ph c tp: O( n2)
4. Sp x p hòa nh p (Merge sort) Chia tr (Divide and conquer): Chia bài toán l n thành nh ng bài toán nh h ơn. Gi i quy t nh ng bài toán nh sau ó g p l i c l i gi i cho bài toán l n. Ý t ư ng merge sort: s p x p m t m ng A[start end ], ta chia m ng A thành 2 m ng con A1 và A2 . S p x p A1 và A2 , sau ó hòa nh p chúng thành m t c mang A ã s p x p. Mô t thu t toán: B c 1: – Mid = (start + end) / 2 – Sp x p hai n a m ng A[start mid ] và A[( mid + 1 ) end ]. Vi c s p x p hai n a m ng c th c hi n b ng cách g i quy th t c s p x p hòa nh p B c 2: Hòa nh p hai n a m ng A[start mid ] và A[(mid + 1) end ] thu c m ng A trong ó các ph n t ã c s p x p. Ví d : A = (7, 3, 9, 1) Sp x p hai n a m ng: A = ( 3, 7, 1, 9) Hòa nh p hai n a m ng: A = (1, 3, 7, 9)
5. Image taken from Skiena’s lecture note at Stony brook
6. Ví dụ • 7 2 9 4 3 8 6 1 • C D A B G H I J K AB F E
7. Sp x p hòa nh p (Merge sort) void MergeSort( Item A[ ], int start, int end) { if (start < end) { int mid = (start + end)/2; MergeSort ( A, start, mid ); MergeSort ( A, mid+1, end); Merge ( A, start, mid, end); } }
8. Hòa nh p hai m ng t ng d n ↓ ↓ 3 7 1 9 1 ↓ ↓ 3 7 1 9 1 3 ↓ ↓ 3 7 1 9 1 3 7 ↓ ↓ 3 7 1 9 1 3 7 9
9. Sp x p hòa nh p Thu t toán merge: Xem ch ơ ng trình ph c t p thu t toán s p x p hòa nh p: O( n log n)