S P X PẮ Ế
Nguy n Văn Linhễ
M c tiêuụ
Sau khi hoàn t t bài h c này b n c n ph i:ấ ọ ạ ầ ả
Hi u các gi i thu t s p x p.ể ả ậ ắ ế
V n d ng đ c gi i thu t đ minh h a vi c s p ậ ụ ượ ả ậ ể ọ ệ ắ
x p.ế
Hi u các l u đ c a các gi i thu t s p x p.ể ư ồ ủ ả ậ ắ ế
Hi u các ch ng trình s p x p. ể ươ ắ ế
Hi u đ c vi c đánh giá các gi i thu t. ể ượ ệ ả ậ
T m quan tr ng c a bài toán s p x pầ ọ ủ ắ ế
S p x p m t danh sách các đ i t ng theo m t ắ ế ộ ố ượ ộ
th t nào đó là m t bài toán th ng đ c v n ứ ự ộ ườ ượ ậ
d ng trong các ng d ng tin h c.ụ ứ ụ ọ
S p x p là m t yêu c u không th thi u trong ắ ế ộ ầ ể ế
khi thi t k các ph n m m. ế ế ầ ề
Do đó vi c nghiên c u các ph ng pháp s p ệ ứ ươ ắ
x p là r t c n thi t đ v n d ng trong khi l p ế ấ ầ ế ể ậ ụ ậ
trình.
S p x p trong và s p x p ngoàiắ ế ắ ế
S p x p trongắ ế là s s p x p ự ắ ế d li u đ c t ch c trong b nh ữ ệ ượ ổ ứ ộ ớ
trong c a máy tính.ủ
Các đ i t ng c n đ c s p x p là các m u tin g m m t ho c nhi u ố ượ ầ ượ ắ ế ẩ ồ ộ ặ ề
tr ng. M t trong các tr ng đ c g i là khóa (key), ki u c a nó là m t ườ ộ ườ ượ ọ ể ủ ộ
ki u có quan h th t (nh các ki u s nguyên, s th c, chu i ký t ...). ể ệ ứ ự ư ể ố ố ự ỗ ự
Danh sách các đ i t ng c n s p x p s là m t m ng c a các m u tin ố ượ ầ ắ ế ẽ ộ ả ủ ẩ
v a nói trên. ừ ở
M c đích c a vi c s p x p là t ch c l i các m u tin sao cho các khóa ụ ủ ệ ắ ế ổ ứ ạ ẩ
c a chúng đ c s p th t t ng ng v i quy lu t s p x p. ủ ượ ắ ứ ự ươ ứ ớ ậ ắ ế
M t cách m c nhiên, quy lu t s p x p là th t không gi m. Khi c n s p ộ ặ ậ ắ ế ứ ự ả ầ ắ
x p theo th t không tăng thì ph i nói rõ.ế ứ ự ả
S p x p ngoàiắ ế là s s p x p đ c s d ng khi s l ng đ i t ng c n ự ắ ế ượ ử ụ ố ượ ố ượ ầ
s p x p l n không th l u tr trong b nh trong mà ph i l u tr trên ắ ế ớ ể ư ữ ộ ớ ả ư ữ b ộ
nh ngoàiớ.
T ch c d li u và ngôn ng cài đ tổ ứ ữ ệ ữ ặ
Ð trình bày các ví d minh h a chúng ta s dùng C ể ụ ọ ẽ
(Turbo C++, Version 3.0) làm ngôn ng th hi n và ữ ể ệ
s d ng khai báo sau. ử ụ
const int n = 10;
typedef int keytype;
typedef float othertype;
typedef struct recordtype {
keytype key;
othertype otherfields;
};
recordtype a[n]; /* khai bao mang a co n phan tu */