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

Chia sẻ: Nguyen Van Dai | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

162
lượt xem 26
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ố.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Khoa học máy tính - Sắp xếp (Sorting)

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@yahoo.com
Bài toán s p x p Input: i tư ng A = (a0,…,an) Danh sách các Problem: 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 - 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 ư 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 t 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] 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 p Thu 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)