Khoa học máy tính - Sắp xếp (Phần 2)

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

Thêm vào BST

Báo xấu

173
lượt xem 21
download

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

Tham khảo tài liệu 'khoa học máy tính - sắp xếp (phần 2)', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

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 (Phần 2)

S p x p (ph n 2) Lê S Vinh B môn Khoa H c Máy Tính – Khoa CNTT i H c Công Ngh - HQGHN Email: vinhbio@gmail.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 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
Bucket sort 1, c 3, a 3, b 7, d 7, g 7, e B∅ ∅ ∅∅∅ ∅∅ 0123456789