Khoa học máy tính - Sắp xếp (Phần 2)

Tham khảo tài liệu khoa học máy tính - sắp xếp (phần 2), công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Khoa học máy tính - Sắp xếp (Phần 2) S p x p (ph n 2) Lê S VinhB môn Khoa H c Máy Tính – Khoa CNTT i H c Công Ngh - HQGHN Email: vinhbio@gmail.com Bài toán s p x pInput: i tư ng A = (a0,…,an) Danh sách cácProblem: thu ư c m t danh sách m i, trong ó các i ch các ph n t 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 - 1Ví d : A = (1 , 5, 0, 3) → (0, 1, 3, 5) A = (‘Vinh’, ‘Tuan’, ‘Anh’) → (‘Anh’, ‘Vinh’, ‘Tuan) S p 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” Quick sortVoid 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 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 h p ph n chưa ư c phân chia, cho n khi ph n chưa ư c phân chia b ng r ng. 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: N u 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í Ví dS p x p dãy s sau b ng quick sort• 314592687Trư ng h p t t nh t T(n) = O(n logn)Trư ng h p t i nh t T(n) = O(n2) 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 Bucket sort 1, c 3, a 3, b 7, d 7, g 7, eB∅ ∅ ∅∅∅ ∅∅ 0123456789