Khoa học máy tính - Sắp xếp (Sorting)

Trong khoa học máy tính và trong toán học, một thuật toán sắp xếp là một thuật toán sắp xếp các phần tử của một danh sách (hoặc một mảng theo thứ tự (tăng hoặc giảm)). Người ta thường xét trường hợp các phần tử cần sắp xếp là các số.
Nội dung trích xuất từ tài liệu:
Khoa học máy tính - Sắp xếp (Sorting) S p x p (sorting) Lê S VinhB môn Khoa H c Máy Tính – Khoa CNTT i H c Công Ngh - HQGHN Email: vinhioi@yahoo.com Bài toán s p x pInput: i tư ng A = (a0,…,an) Danh sách cácProblem: thu ư c m t danh sách m i, trong ó các i ch các ph n t 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 - 1Ví d : A = (1 , 5, 0, 3) → (0, 1, 3, 5) A = (‘Vinh’, ‘Tuan’, ‘Anh’) → (‘Anh’, ‘Vinh’, ‘Tuan) S px pn ib tThu 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 ư c l i gi i cho bài toán l n. nh ng bài toán nh sau ó g p l iÝ 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 ư c mang A ã s p x p. và A2. S p x p A1 và A2, sau ó hòa nh p chúng thành m tMô 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] thu ư c m ng A 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)Image taken from Skiena’s lecture note at Stony brook Ví d• 7 2 9 43 8 6 1• C D A B G H I J K AB F E S p x p hòa nh p (Merge sort)void MergeSort( Item A[ ], int start, int end) { if (start < end) { int mid = (start + end)/2; MergeSort ( A, start, mid ); MergeSort ( A, mid+1, end); Merge ( A, start, mid, end); }} Hòa nh p hai m ng tăng d n↓ ↓3 7 1 9 1↓ ↓3 7 1 9 1 3 ↓ ↓3 7 1 9 1 3 7 ↓ ↓3 7 1 9 1 3 7 9 S p x p hòa nh pThu t toán merge: Xem chương trình ph c t p thu t toán s p x p hòa nh p: O(n logn)