tailieunhanh - Bài giảng Sắp xếp (Phần 1)
Bài giảng Sắp xếp (Phần 1) nêu lên bài toán sắp xếp, sắp xếp nổi bọt, sắp xếp hòa nhập (Merge sort). Mời các bạn tham khảo bài giảng để bổ sung thêm kiến thức về lĩnh vực này. Với các bạn chuyên ngành Công nghệ thông tin thì đây là tài liệu hữu ích. | S p x p (sorting) Lê S Vinh B môn Khoa H c Máy Tính – Khoa CNTT i H c Công Ngh - HQGHN Email: vinhioi@ 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 px pn ib t Thu t toán: L n lư t duy t qua danh sách, n u hai ph n t li n k ng không úng th t thì i ch . L p l i quá trình trên cho n khi danh sách ư c s p x p. Ví d : S p tăng d n dãy s A = (9, 7, 6, 2) (9, 7, 6, 2) → (9, 7, 2, 6) → (9, 2, 7, 6) → (2, 9, 7, 6) (2, 9, 7, 6) → (2, 9, 6, 7) → (2, 6, 9, 7) (2, 6, 9, 7) → (2, 6, 7, 9) Ví d 2, 3, 5: Chương trình ph c t p: O(n2) S p x p hòa nh p (Merge sort) Chia 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 nh ng bài toán nh sau ó g p l i ư c l i gi i cho bài toán l n. Ý tư ng merge sort: s p x p m t m ng A[start end], ta chia m ng A thành 2 m ng con A1 và A2. S p x p A1 và A2, sau ó hòa nh p chúng thành m t ư c mang A ã s p x p. Mô t thu t toán: Bư c 1: – Mid = (start + end) / 2 – 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 ư c th c hi n b ng cách g i quy th t c s p x p hòa nh p Bư c 2: Hòa nh p hai n a m ng A[start mid] và A[(mid + 1) end] trong ó các ph n t ã ư c s p x p. Ví d : A = (7, 3, 9, 1) S p x p hai n a m ng: A = (3, 7, 1, 9) Hòa nh p hai n a m ng: A = (1, 3, 7, 9) thu ư c m ng A Image taken from Skiena’s lecture note at Stony .
đang nạp các trang xem trước
