S p x p b ng c sắ ế ằ ơ ố
Radix sort
S p x p theo ph ng pháp c ắ ế ươ ơ
số
Radix sort l i d a trên nguyên t c phân lo i ạ ự ắ ạ
th c a b u đi n. ư ủ ư ệ
Vì lý do đó nó còn có tên là Postman’s sort.
Nó không h quan tâm đ n vi c so sánh giá ề ế ệ
tr c a ph n t ị ủ ầ ử
Vi c phân lo i và trình t phân lo i s t o ra ệ ạ ự ạ ẽ ạ
th t cho các ph n t . ứ ự ầ ử
To: Lê Văn An
h th ng phân lo i th phân c p ệ ố ạ ư ấ
N c ướ t nh, thành phỉ ố qu n, huy nậ ệ ph ng ườ
xã đ ngườ s nhàố
Thu t toán phân lo i d a theo th t hàng ậ ạ ự ứ ự
c a sủ ố
tỉtri uệngàntram ch cụ đ n vơ ị
Mô ph ng l i qui trình trên, đ s p x p dãyỏ ạ ể ắ ế a1,
a2, ..., an, gi i thu t Radix Sort th c hi n nh sau: ả ậ ự ệ ư
? Tr c tiên, ta có th gi s m i ph n t ướ ể ả ử ỗ ầ ử ai
trong dãy a1, a2, ..., an là m t s nguyên có t i đa ộ ố ố
m ch s . ữ ố
? Ta phân lo i các ph n t l n l t theo các ạ ầ ử ầ ượ
ch s hàng đ n v , hàng ch c, hàng trăm, . Qua ữ ố ơ ị ụ
m i b c phân lo i ta có đ c các ph n t có th ỗ ướ ạ ượ ầ ử ứ
t theo hàng c a nó. ự ủ
Khi ta phân lo i đ n s h ng th m thì t t c các ạ ế ố ạ ứ ấ ả
ph n t đã đ c s p x pầ ử ượ ắ ế