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

S p x p (ph n 2)<br /> Lê S Vinh<br /> B môn Khoa H c Máy Tính – Khoa CNTT<br /> i H c Công Ngh - HQGHN<br /> Email: vinhbio@gmail.com<br /> <br /> Bài toán s p x p<br /> Input:<br /> Danh sách các<br /> Problem:<br /> <br /> i tư ng A = (a0,…,an)<br /> <br /> i ch các ph n t<br /> thu ư c m t danh sách m i, trong ó các<br /> ph n t ư c s p x p theo m t th t nào ó<br /> <br /> Output:<br /> A’ = (a’0,…,a’n) | a’i < a’i+1, i = 0…n - 1<br /> Ví d :<br /> A = (1 , 5, 0, 3) → (0, 1, 3, 5)<br /> A = (‘Vinh’, ‘Tuan’, ‘Anh’) → (‘Anh’, ‘Vinh’, ‘Tuan)<br /> <br /> S p x p nhanh (Quick sort)<br /> 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<br /> hai ph n “ph n bên trái” và “ph n bên ph i” sao cho các ph n t<br /> ph n<br /> bên trái nh hơn ho c b ng các ph n t<br /> ph n bên ph i. Sau khi phân chia,<br /> ti p t c th c hi n “quick sort trên hai ph n d li u trên.<br /> C th hơn, g i “pivot” là ph n t trung tâm c a danh sách, các ph n t<br /> 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<br /> ho c b ng “pivot” thì n m bên ph i “pivot”<br /> <br /> Quick sort<br /> Void quickSort (Item A[], int start, int end) {<br /> if (start < end) {<br /> pivotLocation = partition (A, start, end, A[start]);<br /> quickSort (A, start, pivotLocation – 1);<br /> quickSort (A, pivotLocation + 1, end)<br /> }<br /> }<br /> <br />