Bài giảng Sắp xếp (Phần 2) đưa ra bài toán sắp xếp, sắp xếp nhanh (Quick sort), Bucket sort. Bài giảng phục vụ cho các bạn chuyên ngành Công nghệ thông tin và những bạn quan tâm tới lĩnh vực này. Mời các bạn tham khảo. | S p x p (ph n 2) Lê S Vinh B môn Khoa H c Máy Tính – Khoa CNTT i H c Công Ngh - HQGHN Email: vinhbio@ Bài toán s p x p Input: Danh sách các Problem: i tư ng A = (a0, ,an) 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) 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 sort Void quickSort (Item A[], int start, int end) { if (start < end) { pivotLocation = partition (A, start, end, A[start]); quickSort (A, start, pivotLocation – 1); quickSort (A, pivotLocation + 1, .
