Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 5: Sắp xếp (sorting) - Lê Sỹ Vinh

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 5: Sắp xếp (sorting) - Lê Sỹ Vinh

1. Sp xp (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 sp xp Input: Danh sỏch cỏc ủi tưng A = (a 0, ,a n) Problem: ði ch cỏc phn t ủ thu ủưc mt danh sỏch mi, trong ủú cỏc phn 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 xp ni bt Thut toỏn: Ln lưt duyt qua danh sỏch, nu hai phn t lin 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 tăng 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) Chương trỡnh ð phc tp : O( n2)
4. Sp xp hũa nhp (Merge sort) Chia ủ tr (Divide and conquer): Chia bài toỏn ln thành nhng bài toỏn nh hơn. Gii quyt nhng bài toỏn nh sau ủú gp li ủ ủưc li gii cho bài toỏn ln. í tưng merge sort: ð sp xp mt mng A[start end ], ta chia mng A thành 2 mng con A1 và A2 . Sp xp A1 và A2 , sau ủú hũa nhp chỳng thành mt ủ ủưc mang A ủó sp xp. Mụ t thut toỏn: Bưc 1: – Mid = (start + end) / 2 – Sp xp hai na mng A[start mid ] và A[( mid + 1 ) end ]. Vic sp xp hai na mng ủưc thc hin bng cỏch gi ủ quy th tc sp xp hũa nhp Bưc 2: Hũa nhp hai na mng A[start mid ] và A[(mid + 1) end ] ủ thu ủưc mng A trong ủú cỏc phn t ủó ủưc sp xp. Vớ d: A = (7, 3, 9, 1) Sp xp hai na mng: A = ( 3, 7, 1, 9) Hũa nhp hai na mng: A = (1, 3, 7, 9)
5. Image taken from Skiena’s lecture note at Stony brook
6. Sp xp hũa nhp (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); } }
7. Hũa nhp hai mng tăng dn ↓ ↓ 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
8. Sp xp hũa nhp Thut toỏn merge: Xem chương trỡnh ð phc tp thut toỏn sp xp hũa nhp: O( n log n)
9. Vớ d 0
10. Vớ d Sp tăng dóy s 1. 9 8 7 6 5 4 3 2 1 2. C D A B G H I J K AB F E
11. Sp xp nhanh (Quick sort) Tư tưng ca Quick sort: Phõn chia danh sỏch d liu cn sp xp ra thành hai phn “phn bờn trỏi” và “phn bờn phi” sao cho cỏc phn t phn bờn trỏi nh hơn hoc bng cỏc phn t phn bờn phi. Sau khi phõn chia, tip tc thc hin “quick sort trờn hai phn d liu trờn. C th hơn, gi “pivot” là phn t trung tõm ca danh sỏch, cỏc phn t nh hơn hoc bng “pivot” thi nm bờn trỏi “pivot”, cỏc phn t ln hơn hoc bng “pivot” thỡ nm bờn phi “pivot”
12. 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) } }
13. Partition (A, start, end) Tư tưng phõn chia: Danh sỏch gm ba phn: – Phn bờn trỏi (cỏc giỏ tr nh hơn pivot) – Phn bờn phi (cỏc giỏ tr ln hơn pivot) – Phn gia chưa ủưc phõn chia Duyt trờn danh sỏch ủ m rng dn phn bờn trỏi và phn bờn phi, ủng thi thu hp phn chưa ủưc phõn chia, cho ủn khi phn chưa ủưc phõn chia bng rng.
14. Partition (A, start, end) Khi to: Phn bờn trỏi và phn bờn bng rng. Phn chưa ủưc phõn chia t v trớ start → end. Xỏc ủnh pivot = A[start] Bưc 1: Duyt t trỏi sang phi ca phn chưa ủưc phõn chia, nu phn t hin ti nh hơn hoc bng pivot thỡ m rng phn bờn trỏi và thu hp phn chưa ủưc phõn chia, nu khụng dng li. Bưc 2: Duyt t phi sang tri ca phn chưa ủưc phõn chia, nu phn t hin ti ln hơn hoc bng pivot thỡ m rng phn bờn phi và thu hp phn chưa ủưc phõn chia, nu khụng dng li. Bưc 3: ði ch phn t bờn trỏi nht và phn t bờn phi nht ca phn chưa ủưc phõn chia. M rng phn bờn trỏi và phn bờn phi, ủng thi thu hp hai ủu ca phn chưa ủưc phõn chia. Bưc 4: Nu phn chưa ủưc phõn chia khỏc rng thỡ quay li Bưc 1. Bưc 5: Chuyn pivot vào ủỳng v trớ
15. Vớ d Sp xp dóy s sau bng quick sort • 3 1 4 5 9 2 6 8 7
16. Trưng hp tt nht T(n) = O( n log n)
17. Trưng hp ti nht T(n) = O( n2)
18. Nh n xột v quick sort Thi gian trung bỡnh: O(n log n) Là mt thut toỏn sp xp nhanh nht trong thc t
19. T ủc • Heap sort