Sắp xếp (sorting)

Chia sẻ: Le Quang Duan Duan | Ngày: | Loại File: PDF | Số trang:20

Thêm vào BST

Báo xấu

101
lượt xem 11
download

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

Tài liệu tham khảo về sắp xếp - môn Khoa học máy tính

Chủ đề:

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

Lưu

Nội dung Text: 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: Danh sách các ñ i tư ng A = (a0,…,an) Problem: ð 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) 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] ñ 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
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)
Ví d 0
Ví d S p tăng dãy s 1. 9 8 7 6 5 4 3 2 1 2. C D A B G H I J K AB F E
S p x p nhanh (Quick sort) 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 hai ph n “ph n bên trái” và “ph n bên ph i” sao cho các ph n t ph n bên trái nh hơn ho c b ng các ph n t ph n bên ph i. Sau khi phân chia, ti p t c th c hi n “quick sort trên hai ph n d li u trên. C th hơn, g i “pivot” là ph n t trung tâm c a danh sách, các ph n t 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 ho c b ng “pivot” thì n m bên ph i “pivot”
Quick sort Void quickSort (Item A[], int start, int end) { if (start < end) { pivotLocation = partition (A, start, end); quickSort (A, start, pivotLocation – 1); quickSort (A, pivotLocation + 1, end) } }
Partition (A, start, end) Tư tư ng phân chia: Danh sách g m ba ph n: – Ph n bên trái (các giá tr nh hơn pivot) – Ph n bên ph i (các giá tr l n hơn pivot) – Ph n gi a chưa ñư c phân chia Duy t trên danh sách ñ m r ng d n ph n bên trái và ph n bên ph i, ñ ng th i thu h p ph n chưa ñư c phân chia, cho ñ n khi ph n chưa ñư c phân chia b ng r ng.
Partition (A, start, end) Kh i t o: Ph n bên trái và ph n bên b ng r ng. Ph n chưa ñư c phân chia t v trí start → end. Xác ñ nh pivot = A[start] Bư c 1: Duy t t trái sang ph i c a ph n chưa ñư c phân chia, n u ph n t hi n t i nh hơn ho c b ng pivot thì m r ng ph n bên trái và thu h p ph n chưa ñư c phân chia, n u không d ng l i. Bư c 2: Duy t t ph i sang tr i c a ph n chưa ñư c phân chia, n u ph n t hi n t i l n hơn ho c b ng pivot thì m r ng ph n bên ph i và thu h p ph n chưa ñư c phân chia, n u không d ng l i. Bư c 3: ð i ch ph n t bên trái nh t và ph n t bên ph i nh t c a ph n chưa ñư c phân chia. M r ng ph n bên trái và ph n bên ph i, ñ ng th i thu h p hai ñ u c a ph n chưa ñư c phân chia. Bư c 4: N u ph n chưa ñư c phân chia khác r ng thì quay l i Bư c 1. Bư c 5: Chuy n pivot vào ñúng v trí
Ví d S p x p dãy s sau b ng quick sort • 314592687
Trư ng h p t t nh t T(n) = O(n logn)
Trư ng h p t i nh t T(n) = O(n2)
Nh n xét v quick sort - Th i gian trung bình: O(n log n) - Là m t thu t toán s p x p nhanh nh t trong th c t
T ñ c • Heap sort