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
Bạn đang xem tài liệu "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", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tài liệu đính kèm:
bai_giang_cau_truc_du_lieu_va_giai_thuat_bai_5_sap_xep_sorti.pdf
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
- 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
- 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)
- 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)
- 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)
- Image taken from Skiena’s lecture note at Stony brook
- 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); } }
- 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
- 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)
- Vớ d 0
- 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
- 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”
- 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) } }
- 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.
- 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ớ
- Vớ d Sp xp dóy s sau bng quick sort • 3 1 4 5 9 2 6 8 7
- Trưng hp tt nht T(n) = O( n log n)
- Trưng hp ti nht T(n) = O( n2)
- 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
- T ủc • Heap sort