Bài giảng Sắp xếp (Phần 2)

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.
Nội dung trích xuất từ tài liệu:
Bài giảng 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 CNTTi H c Công Ngh - HQGHNEmail: vinhbio@gmail.comBài toán s p x pInput:Danh sách cácProblem:i tư ng A = (a0,…,an)i ch các ph n tthu ư c m t danh sách m i, trong ó cácph 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ànhhai ph n “ph n bên trái” và “ph n bên ph i” sao cho các ph n tph nbên trái nh hơn ho c b ng các ph n tph 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 tnh hơn ho c b ng “pivot” thi n m bên trái “pivot”, các ph n t l n hơnho 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, A[start]);quickSort (A, start, pivotLocation – 1);quickSort (A, pivotLocation + 1, end)}}