C U TRÚC D LI U VÀ Ấ Ữ Ệ
GI I THU TẢ Ậ
Ch ng 9: B ngươ ả
Ch ng 9: B ngươ ả
2
Ma tr n 2 chi u vs. 1 chi uậ ề ề
A[i, j]
B[ max_row*i + j] C[i + max_col*j]
Ch ng 9: B ngươ ả
3
B ng và ch m cả ỉ ụ
Ch ng 9: B ngươ ả
4
Radix sort
r a t
m o p
c a t
m a p
c a r
t o p
c o t
t a r
r a p
B c 1ướ
r a t
m o p
c a t
m a p
c a r
t o p
c o t
t a r
r a p
r a t
m o p
c a t
m a p
c a r
t o p
c o t
t a r
r a p
r a t
m o p
c a t
m a p
c a r
t o p
c o t
t a r
r a p
B c 2ướ B c 3ướ
Ch ng 9: B ngươ ả
5
Đánh giá Radix sort
S l n so sánh là ố ầ Θ(n k), n là s ph n t và ố ầ ử k là s ký t trên ố ự
khóa
So sánh v i các ph ng pháp khác là ớ ươ n lg n:
N u ếk l n và ớn là nh thì radix sort ch mỏ ậ
N u ếk nh và ỏn là l n thì radix sort nhanh h nớ ơ
B t ti n:ấ ệ
Vi c tách thành 27 danh sách con và ghép l i lúc sau trên ệ ạ
DS liên t c gây ra vi c di chuy n nhi u ph n tụ ệ ể ề ầ ử
Khóa so sánh là chu i nh phân thì không t tỗ ị ố