Đ t v n đặ ấ ề
•S p x p là m t quá trình t ch c l i m t dãy ắ ế ộ ổ ứ ạ ộ
các d li u theo m t tr t t nh t đ nhữ ệ ộ ậ ự ấ ị
•M c đích c a s p x p là nh m giúp cho vi c ụ ủ ắ ế ằ ệ
tìm ki m d li u đ c d dàng nhanh chóngế ữ ệ ượ ễ
•Ví d :ụ
Cho tr c m t dãy n s nguyên đ c s p th ướ ộ ố ượ ắ ứ
t tăng d nự ầ
Vi c tìm ki m m t ph n t ệ ế ộ ầ ử x nào đó đ c ượ
th c hi n b ng cách chia đôi dãy ban đ uự ệ ằ ầ
Ch c n ỉ ầ k b c ta xác đ nh đ c ph n t c n ướ ị ượ ầ ử ầ
tìm
Tr ng h p x u nh tườ ợ ấ ấ
V y v i n = 1000ậ ớ ≈ 210 i.e ch c n 10 b c là ta ỉ ầ ướ
xác đ nh đ c ph n t c n tìm trong dãy 1000 ị ượ ầ ử ầ
ph n tầ ử
n = 1.000.000 ≈ 220
n = 1 t ỷ≈ 230
Rõ ràng s p x p là m t vi c làm h t s c c b n ắ ế ộ ệ ế ứ ơ ả
và đ c áp d ng r ng rãi trong các k thu t l p ượ ụ ộ ỹ ậ ậ
trình nh m x lý thông tin.ằ ử
Đ t v n đặ ấ ề
Sorting
N i dungộ
–Đ nh nghĩaị
–Gi thi tả ế
–S p x p t i chắ ế ạ ỗ
–Chi n l c s p x pế ượ ắ ế
–T ng quan v th i gian th c hi nổ ề ờ ự ệ
Sorting
Đ nh nghĩaị
•S p x p là m t ti n trìnhắ ế ộ ế :
–Tìm m t b hoán v trên t p h p các đ i t ng cho ộ ộ ị ậ ợ ố ượ
tr c ướ a1, a2, ..., an (ví d là các s nguyên), vàụ ố
–Tr v m t th t khác ả ề ộ ứ ự (a'1, a'2, ..., a'n) sao cho
a'1 ≤ a'2 ≤ · · · ≤ a'n
•Ít khi ta s p x p các giá tr đ n l . ắ ế ị ơ ẻ
•Thông th ng chúng ta s p x p m t s các m u tin ườ ắ ế ộ ố ẫ
ch a m t s các tr ng trên c s tr ng khóaứ ộ ố ườ ơ ở ườ
19991532 Stevenson Monica 3 Glendridge Ave.
19990253 Redpath Ruth 53 Belton Blvd.
19985832 Kilji Islam 37 Masterson Ave.
20003541 Groskurth Ken 12 Marsdale Ave.
19989932 Carol Ann 81 Oakridge Ave.
20003287 Redpath David 5 Glendale Ave.
19989932 Carol Ann 81 Oakridge Ave.
19985832 Kilji Islam 37 Masterson Ave.
19990253 Redpath Ruth 53 Belton Blvd.
19991532 Stevenson Monica 3 Glendridge Ave.
20003287 Redpath David 5 Glendale Ave.
20003541 Groskurth Ken 12 Marsdale Ave.
19989932 Carol Ann 81 Oakridge Ave.
20003541 Groskurth Ken 12 Marsdale Ave.
19985832 Kilji Islam 37 Masterson Ave.
20003287 Redpath David 5 Glendale Ave.
19990253 Redpath Ruth 53 Belton Blvd.
19991532 Stevenson Monica 3 Glendridge Ave.
Theo ID number
Theo th t h tênứ ự ọ
Sorting
Đ nh nghĩaị