S p x p d a trên phân ho ch
ự
ế
ắ
ạ
quicksort
Quicksort- ý t
ngưở
i thu t QuickSort d a
ả
ự
ậ
ể ắ
ế
• Ð s p x p dãy ệ
a1, a2, ..., an gi ầ
ạ
ầ
•
ầ ử a1.. ai có giá tr không
ị
ơ x
•
ầ ử ai .. an có giá tr không
ị
trên vi c phân ho ch dãy ban đ u thành hai ph n : Dãy con 1: G m các ph n t ồ l n h n ớ Dãy con 2: G m các ph n t ồ nh h n
ỏ ơ x
• v i ớ x là giá tr c a m t ph n t
ộ
ầ
tùy ý trong dãy ban đ u. c phân
ị ủ ệ
ầ ử ạ
ượ
ầ
ự
Sau khi th c hi n phân ho ch, dãy ban đ u đ thành 3 ph n: ầ
• • •
1. ak < x , v i k = 1..i 2. ak = x , v i k = i..j 3. ak > x , v i k = j..N
ớ ớ ớ
Quicksort-ý t
ngưở
ak
trong đó dãy con th 2 đã có th t
ứ ự
ứ
• • n u các dãy con 1 và 3 ch có 1 ph n t
thì chúng
ế
ỉ
cũng đã có th t
ứ ự
ượ
, ầ ử ầ
• Ng
ế
c s p. , khi đó dãy ban đ u đã đ ắ i, n u các dãy con 1 và 3 có nhi u h n 1 ơ ề khi các dãy
thì dãy ban đ u ch có th t ầ
ứ ự
ỉ
c s p. ắ • Ð s p x p dãy con 1 và 3, ta l n l
ệ
t ti n hành vi c ng pháp
ừ
ầ ượ ế ươ
phân ho ch t ng dãy con theo cùng ph phân ho ch dãy ban đ u v a trình bày .
c l ượ ạ ph n t ầ ử con 1, 3 đ ượ ế ể ắ ạ ạ
ừ
ầ
1 I j N
Quicksort- gi
ả
i thu t ậ
Gi
i thu t phân ho ch dãy al, al+1, ., ar thành 2 dãy
ậ
ạ
ầ ử
ộ
a[k] trong dãy là giá tr ị
: Ch n tùy ý m t ph n t ọ ≤ k ≤ r:
ả con: • B c 1 ướ m c, l ố
x = a[k]; i = l; j = r;
a[i], a[j]
: Phát hi n và hi u ch nh c p ph n t ệ
ầ ử
ệ
ặ
ỉ
n m sai ch :
ỗ
: Trong khi (a[i]
// a[i] ≥ x ≥ a[j] mà a[j] đ ng sau a[i]
• B c 2 ướ ằ • B c 2a ướ • B c 2b ướ • B c 2c ướ
ứ
ế Hoán v (a[i],a[j]);
ị
i B c 2
ặ ạ ướ
ả .//ch a xét h t m ng
ư
ế
• B c 3 : ướ N u i < j: ế ≥ j: N u i ế
L p l D ngừ
Quicksort- nh n xét
ậ
ắ
ể
ề
ộ ạ
ầ ử i ả
c ch n, khi đó k
ị ố ả ng đ
ọ
ườ
ư ị
ầ ử
ễ ễ ượ
•
ượ
c ch n s có tác đ ng đ n hi u qu ả ộ
ẽ
ệ
ọ
ế ố ầ
ế ị
ấ ế
ự ạ
ẽ
ạ
ủ
i ta
ị
ọ
c ượ median c a dãy. Tuy nhiên do chi phí xác median quá cao nên trong th c t ầ ử ằ ể ầ
này mà ch n ph n t ầ ử ớ ố
ữ
• V nguyên t c, có th ch n giá tr m c x là m t ph n t ọ tùy ý trong dãy, nh ng đ đ n gi n, d di n đ t gi ể ơ thu t, ph n t có v trí gi a th ữ ậ = (l +r)/ 2 Giá tr m c x đ ị ố th c hi n thu t toán vì nó quy t đ nh s l n phân ậ ệ ho ch. S l n phân ho ch s ít nh t n u ta chon đ ố ầ x là ph n t ầ ử ng đ nh ph n t ườ ự ế ầ ử n m chính không ch n ph n t ọ gi a dãy làm m c v i hy v ng nó có th g n v i giá tr ị ớ ọ median
Quicksort
i thu t phân ho ch dãy s p x p dãy al, al+1, .,
ế
ắ
ậ
ạ
•
i thu t s p x p QuickSort m t
ể
ể
ậ ắ
ế
ộ
• Gi ả ar: Có th phát bi u gi ả cách đ qui nh sau :
ư
ạ
- Dãy con 1 : al.. aj ≤ x - Dãy con 2 : aj+1.. ai-1 = x - Dãy con 3 : ai.. ar ≥ x
:
// dãy con 1 có nhi u h n 1 ph n t
ề
ơ
ầ ử
// dãy con 3 có nhi u h n 1 ph n t
ế
ề
ơ
ầ ử
ệ • B c 1 : Phân ho ch dãy al . ar thành các dãy con : ướ • • • • B c 2 ướ • N u ( l < j ) ế • Phân ho ch dãy al.. aj ạ • N u ( i < r ) Phân ho ch dãy ai.. ar ạ
Quicksort –ví dụ
ắ
ế
ộ ữ ệ
• S p x p b d li u • 1,5,3,6,7,12,4,10,2,9
1 5 3 6 7 12 4 10 2 9
7 Phân ho ch đo n r=0 r=9, x=a[4]=7 ạ ạ
0 1 2 3 4 5 6 7 8 9
Quicksort –ví dụ
7 Phân ho ch đo n r=0 r=9, x=a[4]=7 ạ ạ
1 5 3 6 12 4 10 9 7 2
i
j
L=0 R=9
1 5 3 6 12 4 10 2 7 9
0 1 2 3 5 6 7 4 8 9
Quicksort –ví dụ
Phân ho ch đo n r=0 r=9, x=a[4]=7 ạ ạ 7
1 5 3 6 10 7 9 2 4 12
i
j
L=0 R=9
Phân ho ch đo n r=0 r=9, x=a[4]=7 ạ ạ
j
i
2 4 1 5 3 6 12 10 7 9
4 5 0 1 2 3 6 7 8 9
Quicksort –ví dụ
1 5 3 6 2 4 12 10 7 9
Phân ho ch đo n r=0 r=5, x=a[2]=3 ạ ạ
R=9 L=0 R=5 L=6
J=i
j i
3 1 2 6 5 4 9 7 10 12
2 0 1 3 4 5 6 7 8 9
Quicksort –ví dụ
1 2 3 6 5 4 9 7 10 12
…
1 2 3 4 5 6 7 9 10 12
Quicksort –cài đ t thu t toán
ặ
ậ
c cài đ t đ qui nh sau : ể ượ ặ ệ ư ậ
Thu t toán QuickSort có th đ void QuickSort( int l, int r) { int i,j; int x;
// ch n ph n t gi a làm giá tr m c ầ ử ữ ị ố ọ
x = a[(l+r)/2]; i =l; j = r; do {
while(a[i] < x) i++; while(a[j] > x) j--; if(i <= j) {
Hoanvi(a[i],a[j]); i++ ; j--;
} }while(i < j); if(l < j) QuickSort(l,j); if(i < r) QuickSort(i,r);
}
• Class Cmang{ • Int []Tappt; • Int spt;
• Public void Qsort(){ • Quicksort(0,spt-1); • } • Main() • Cmang a; • A.Qsort();
• }
Quicksort-đánh giá thu t toán
ậ
i thu t QuickSort ph thu c
ộ
ậ
ệ
ụ
ế
ạ
ủ ị ố ấ ả ầ ử
• Tr ườ ề ằ
ỗ ầ median (ph n t ỏ ơ
t nh t x y ra n u m i l n phân ho ch c ph n t ầ ử
ầ ử
l n h n (hay ơ ầ ử ớ , và nh h n (hay b ng) n a s ố ử ằ c phân chia ượ ố ạ ầ
i) làm m c, khi đó dãy đ ằ
ầ
ắ
i ch n nh m ph n t ằ
ư
ạ
ọ
ẽ ị
ự
ố
ầ
ầ ỉ , do v y c n phân
ầ
ầ
ậ
Đánh giá thu t toán ậ • Hi u q a th c hi n c a gi ả ệ ự ủ vào vi c ch n giá tr m c. ọ ệ ng h p t ợ ố đ u ch n đ ọ ượ b ng) n a s ph n t ố ử còn l ph n t ạ thành 2 ph n b ng nhau và c n log2(n) l n phân ho ch ầ thì s p x p xong. ế • Nh ng n u m i l n phân ho ch l ỗ ầ ế ầ ử ạ có giá tr c c đ i (hay c c ti u) là m c, dãy s b phân ạ ị ự ể chia thành 2 ph n không đ u: m t ph n ch có 1 ph n ộ ầ ề i g m (n-1) ph n t t ạ ồ ầ ử ử ho ch n l n m i s p x p xong. ế ớ ắ
, ph n còn l ạ
ầ
