S p x p d a trên phân ho chắ ế ự ạ
quicksort
Quicksort- ý t ngưở
•Ð s p x p dãyể ắ ế a1, a2, ..., an gi i thu t QuickSort d a ả ậ ự
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 ồ ầ ử a1.. ai có giá tr không ị
l n h n ớ ơ x
• Dãy con 2: G m các ph n t ồ ầ ử ai .. an có giá tr không ị
nh h n ỏ ơ x
•v i ớx là giá tr c a m t ph n t tùy ý trong dãy ban đ u. ị ủ ộ ầ ử ầ
Sau khi th c hi n phân ho ch, dãy ban đ u đ c phân ự ệ ạ ầ ượ
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ưở
•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 , khi đó dãy ban đ u đã đ c s p. ứ ự ầ ượ ắ
•Ng c l i, n u các dãy con 1 và 3 có nhi u h n 1 ượ ạ ế ề ơ
ph n t thì dãy ban đ u ch có th t khi các dãy ầ ử ầ ỉ ứ ự
con 1, 3 đ c s p. ượ ắ
•Ð s p x p dãy con 1 và 3, ta l n l t ti n hành vi c ể ắ ế ầ ượ ế ệ
phân ho ch t ng dãy con theo cùng ph ng pháp ạ ừ ươ
phân ho ch dãy ban đ u v a trình bày . ạ ầ ừ
ak<x ak=x ak>x
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 ả ậ ạ
con:
•B c 1ướ : Ch n tùy ý m t ph n t a[k] trong dãy là giá tr ọ ộ ầ ử ị
m c, l ố≤ k ≤ r:
x = a[k]; i = l; j = r;
•B c 2ướ : Phát hi n và hi u ch nh c p ph n t a[i], a[j] ệ ệ ỉ ặ ầ ử
n m sai ch : ằ ỗ
•B c 2aướ : Trong khi (a[i]<x) i++;
•B c 2bướ : Trong khi (a[j]>x) j--;
•B c 2cướ : N u i< j ế// a[i] ≥ x ≥ a[j] mà a[j] đ ng sau a[i]ứ
Hoán v (a[i],a[j]); ị
•B c 3ướ :
N u i < j:ếL p l i B c 2ặ ạ ướ .//ch a xét h t m ngư ế ả
N u i ế≥ j: D ngừ
Quicksort- nh n xé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 i ư ể ơ ả ễ ễ ạ ả
thu t, ph n t có v trí gi a th ng đ c ch n, khi đó k ậ ầ ử ị ữ ườ ượ ọ
= (l +r)/ 2
• Giá tr m c x đ c ch n s có tác đ ng đ n hi u qu ị ố ượ ọ ẽ ộ ế ệ ả
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 đ c ạ ố ầ ạ ẽ ấ ế ượ
x là ph n t median c a dãy. Tuy nhiên do chi phí xác ầ ử ủ
đ nh ph n t median quá cao nên trong th c t ng i ta ị ầ ử ự ế ườ
không ch n ph n t này mà ch n ph n t n m chính ọ ầ ử ọ ầ ử ằ
gi a dãy làm m c v i hy v ng nó có th g n v i giá tr ữ ố ớ ọ ể ầ ớ ị
median