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

S p x p (sorting)<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: vinhioi@yahoo.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 px pn ib t<br /> Thu t toán:<br /> L n lư t duy t qua danh sách, n u hai ph n t li n k<br /> ng không úng th t<br /> thì i ch . L p l i quá trình trên cho n khi danh sách ư c s p x p.<br /> Ví d : S p tăng d n dãy s A = (9, 7, 6, 2)<br /> (9, 7, 6, 2) → (9, 7, 2, 6) → (9, 2, 7, 6) → (2, 9, 7, 6)<br /> (2, 9, 7, 6) → (2, 9, 6, 7) → (2, 6, 9, 7)<br /> (2, 6, 9, 7) → (2, 6, 7, 9)<br /> Ví d 2, 3, 5:<br /> Chương trình<br /> ph c t p: O(n2)<br /> <br /> S p x p hòa nh p (Merge sort)<br /> Chia<br /> tr (Divide and conquer): Chia bài toán l n thành nh ng bài toán nh hơn. Gi i quy t<br /> nh ng bài toán nh sau ó g p l i<br /> ư c l i gi i cho bài toán l n.<br /> Ý tư ng merge sort:<br /> s p x p m t m ng A[start…end], ta chia m ng A thành 2 m ng con A1<br /> và A2. S p x p A1 và A2, sau ó hòa nh p chúng thành m t<br /> ư c mang A ã s p x p.<br /> Mô t thu t toán:<br /> Bư c 1:<br /> – Mid = (start + end) / 2<br /> – S p x p hai n a m ng A[start…mid] và A[(mid + 1)…end]. Vi c s p x p hai n a m ng<br /> ư c th c hi n b ng cách g i quy th t c s p x p hòa nh p<br /> Bư c 2: Hòa nh p hai n a m ng A[start…mid] và A[(mid + 1)…end]<br /> trong ó các ph n t ã ư c s p x p.<br /> Ví d :<br /> A = (7, 3, 9, 1)<br /> S p x p hai n a m ng: A = (3, 7, 1, 9)<br /> Hòa nh p hai n a m ng: A = (1, 3, 7, 9)<br /> <br /> thu ư c m ng A<br /> <br /> Image taken from Skiena’s lecture note at Stony brook<br /> <br />