Xem mẫu
- 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
nguon tai.lieu . vn
