i m t dãy ắ ộ
ế ữ ệ
ề ch c l ứ ạ nh t đ nh ấ ị ằ
ụ
ắ tìm ki m d li u đ
Đ t v n đ ặ ấ • S p x p là m t quá trình t ổ ộ các d li u theo m t tr t t ộ ậ ự • M c đích c a s p x p là nh m giúp cho vi c ế ủ ệ c d dàng nhanh chóng ượ ữ ệ
ễ
ố
ộ
ượ
ắ
c s p th ứ
t
Cho tr ự
c m t dãy n s nguyên đ ầ
ầ ử x nào đó đ
ộ
c n
ướ tăng d n Vi c tìm ki m m t ph n t ệ ế ằ ệ ự ỉ ầ k b Ch c n ướ
c ượ th c hi n b ng cách chia đôi dãy ban đ u ầ c ph n t c ta xác đ nh đ ầ ử ầ
ượ
ị
tìm
ế • Ví d :ụ
Đ t v n đ ặ ấ
ề
Tr
210 i.e ch c n 10 b
c là ta
ậ
ỉ ầ
ướ
c n tìm trong dãy 1000
ượ
ườ ấ
220
ng h p x u nh t ấ ợ » V y v i n = 1000 ớ c ph n t xác đ nh đ ầ ử ầ ị ph n tầ ử
ệ
n = 1.000.000 » ỷ » 230 n = 1 t ế ắ và đ ụ trình nh m x lý thông tin. ử
Rõ ràng s p x p là m t vi c làm h t s c c b n ộ c áp d ng r ng rãi trong các k thu t l p ằ
ế ứ ơ ả ậ ậ ượ ộ ỹ
Sorting N i dung ộ
– Đ nh nghĩa ị – Gi t thi ế ả – 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
ị
ng cho
ộ ế ế
ợ
ố ượ
tr
ố
khác
ứ ự
c ướ a1, a2, ..., an (ví d là các s nguyên), và ụ (a'1, a'2, ..., a'n) sao cho – Tr v m t th t ả ề ộ
• 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 ị
a'1 ≤ a'2 ≤ · · · ≤ a'n
Sorting Đ nh nghĩa
ị
.
ế
ng chúng ta s p x p m t s các m u tin
ẫ ng khóa
• • Thông th ứ
Ít khi ta s p x p các giá tr đ n l ị ơ ẻ ế ộ ố ắ ng trên c s tr ơ ở ườ
ắ ườ ch a m t s các tr ộ ố
ườ
19991532
Stevenson
Monica
3 Glendridge Ave.
19990253
Redpath
53 Belton Blvd.
Ruth
19985832
Kilji
Islam
37 Masterson Ave.
20003541
Groskurth
Ken
12 Marsdale Ave.
19989932
Carol
Ann
81 Oakridge Ave.
20003287
Redpath
David
5 Glendale Ave.
Theo ID number
19989932
Carol
81 Oakridge Ave.
Ann
Theo th t
h tên
ứ ự ọ
19985832
Kilji
37 Masterson Ave.
Islam
19989932
Carol
Ann
81 Oakridge Ave.
Ruth
19990253
Redpath
53 Belton Blvd.
20003541
Groskurth
Ken
12 Marsdale Ave.
19991532
Stevenson
Monica
3 Glendridge Ave.
19985832
Kilji
Islam
37 Masterson Ave.
20003287
Redpath
David
5 Glendale Ave.
20003287
Redpath
David
5 Glendale Ave.
Groskurth
Ken
19990253
Redpath
Ruth
53 Belton Blvd.
20003541
12 Marsdale Ave.
19991532
Stevenson
Monica
3 Glendridge Ave.
Sorting Đ nh nghĩa
ị
i m i tr
ng h p
ử ụ ế
ể ạ
ọ ườ
ợ
ầ
ế
ở ố ượ i.e., các đ i t
• Trong ph n này, ta gi ầ – M ng đ ựợ ả – T p trung s p x p tr ậ t ng quát ổ – Các đ i t
ố ượ
ấ i s th a đi u sau: ế ạ ẽ ỏ
ề
a'1 < a'2 < · · · < a'n
ả ử ằ : s r ng c s d ng cho c input và output ả ng khóa và đ l ườ ắ ph n cài đ t,và ặ ng s p x p là duy nh t, ắ ng đã s p x p l ắ
S p t
i ch (in-place)
ắ ạ
Sorting ỗ
• Gi i thu t đ ả ỗ
ệ ộ ố ế c s p t ắ ạ ỉ ậ ượ ớ ụ
i ch nghĩa là vi c xin c p ấ phát vùng nh ch dành cho m t s bi n c c b ộ mà thôi.
ậ ả
• M t s gi ộ ố ả ứ i thu t khác c n c p phát m ng ph ụ ấ c v i m ng ban đ u ớ ầ ướ ả ầ
th hai có cùng kích th (c n ầ O(n) b nh b sung) ộ ớ ổ
Sorting Phân lo iạ i thu t s p x p ch đ ế các thao tác th c hi n: ệ
c phân lo i qua ả • Nhi u gi ề ỉ ượ ạ
ậ ắ ự
Chèn
Hoán đ iổ
Ch nọ
Tr nộ
Phân ph iố
Sorting Run-time
• Th i gian th c hi n gi i thu t r i vào 3 nhóm ự ệ ả ậ ơ
ờ chính:
O(n) O(n ln(n)) O(n2)
ng h p x u nh t, trung bình và ấ
t nh t cho m i gi • Ta kh o sát tr ả ấ ườ ỗ t ố ả
ấ ợ i thu t ậ • Th i gian th c hi n thay đ i d a vào s phân b ố ổ ự ự ờ ự
ủ ầ ệ . ban đ u c a dãy
Sorting Run-time
• Ta s kh o sát m t s gi ộ ố ả i thu t c đi n có đ ộ ậ ổ ể
ả ứ ạ O(n2) :
ẽ ph c t p – insertion sort, bubble sort
• M t s gi i thu t ch y nhanh h n ậ ạ ơ O(n ln(n)) :
ộ ố ả – heap sort, quick sort, và merge sort
Sorting C n d ậ
i ướ
• B t kỳ m t gi ả i thu t s p x p nào cũng ph i ả ậ ắ
ộ kh o sát t ng ph n t ừ ấ ả ầ ử ế ít nh t 1 l n ấ ầ
W
(n)
i là • K t lu n, m i gi ậ ế ọ ả i thu t ph i có c n d ả ậ ậ ướ
Sorting Đ nh nghĩa v ngh ch th ề
ị
ị
ế
1 16 12 26 25 35 33 58 45 42 56 67 83 75 74 86 81 88 99 95
• Xét 3 dãy sau:
1 17 21 42 24 27 32 35 45 47 57 23 66 69 70 76 87
85 95 99 22 20 81 38 95 84 99 12 79 44 26 87 96 10 48 80 1 31 16 92
• 3 dãy này ch a đ c s p x p ư ượ ế ở ứ m c đ nào ? ộ ắ
Sorting Đ nh nghĩa v ngh ch th ề
ị
ị
ế
• Dãy đ u tiên ch c n m t ít s hóan đ i là đ đ ủ ể ộ ầ s p x p l ế ạ ắ
ự ổ
1 16 12 26 25 35 33 58 45 42 56 67 83 75 74 86 81 88 99 95
1 12 16 25 26 33 35 42 45 56 58 67 74 75 81 83 86 88 95 99
ỉ ầ . i dãy này
Sorting Đ nh nghĩa v ngh ch th ề
ị
ị
ế
1 17 21 42 24 27 32 35 45 47 57 23 66 69 70 76 87 85 95 99
1 17 21 23 24 27 32 35 42 45 47 57 66 69 70 76 85 87 95 99
• Dãy th hai có hai ph n t n m r t xa v trí đúng ầ ử ằ ứ ấ ị
• Tuy nhiên có 13 ph n t đã đúng v trí ầ ử ị
Sorting Đ nh nghĩa v ngh ch th ề
ị
ị
ế
ế ề ầ ị
22 20 81 38 95 84 99 12 79 44 26 87 96 10 48 80 1 31 16 92
1 10 12 16 20 22 26 31 38 44 48 79 80 81 84 87 92 95 96 99
Dãy th ba, h u h t các v trí đ u không đúng v trí ị ứ c a nó ủ
Sorting Đ nh nghĩa v ngh ch th ề
ị
ị
ế
• Cho tr c m t dãy b t kỳ có n ph n t , ta có ướ ầ ử ấ ộ
)1
(cid:246) (cid:230) -
=(cid:247)
n 2
nn ( c p sặ 2
(cid:247) (cid:231) ố (cid:231)
ł Ł
(1, 3) (1, 5)
• Ví d , dãy 1, 3, 5, 4, 2, 6 ch a 15 c p s sau ụ ố ứ
ặ (1, 6) (1, 4) (1, 2) (3, 5) (3, 4) (3, 2) (3, 6) (5, 6) (5, 4) (5, 2) (4, 2) (4, 6) (2, 6)
Sorting Đ nh nghĩa v ngh ch th ề
ị
ị
ế
• L u ý r ng 11 c p trong s các c p này đã có ặ ặ ằ ố
ư :ứ ự th t
(1, 3) (1, 5) (1, 4) (1, 2) (1, 6) (3, 5) (3, 4) (3, 2) (3, 6) (5, 6) (5, 4) (5, 2) (4, 2) (4, 6) (2, 6)
Sorting Đ nh nghĩa v ngh ch th ề
ị
ị
ế
c ặ
• Trong khi 4 c p còn l (1, 3) (1, 5)
ng i có th t ượ ứ ự ạ (1, 6) (1, 4) (1, 2) (3, 5) (3, 4) (3, 2) (3, 6) (5, 4) (5, 2) (5, 6) (4, 2) (4, 6) (2, 6)
Sorting Đ nh nghĩa v ngh ch th ề
ị
ị
ế
ậ ầ ử S
• Xét t p các ph n t • M t hoán v c a ị ủ S là s tái s p x p các ph n t ắ ầ ử ự ế
ộ trong S
• Ví d : ụ S = {0, 1, 2, 3}, có 4! = 24 phép hoán v ị
nh sau: ư
0 1 2 3 0 1 3 2 0 2 1 3 0 2 3 1 0 3 1 2 0 3 2 1 1 0 2 3 1 0 3 2 1 2 0 3 1 2 3 0 0 3 1 2 0 3 2 1 2 0 1 3 2 0 3 1 2 1 0 3 2 1 3 0 2 3 0 1 2 3 1 0 3 0 1 2 3 0 2 1 3 1 0 2 3 1 2 0 3 2 0 1 3 2 1 0
Sorting Đ nh nghĩa v ngh ch th ề
ị
ị
ế
• Do đó , phép hoán v sau
ị 1, 3, 5, 4, 2, 6
ch a 4 ngh ch th :
ứ
ế
ị (3, 2) (5, 4) (5, 2) (4, 2)
Sorting Đ nh nghĩa v ngh ch th ề
ị
ị
ế
: k nhau ho c là
• Hoán đ i 2 ph n t ổ ặ
ộ
1 3 5 2 4 6
ế
ị
ầ ử ề – Xóa m t ngh ch th ế ị 1 3 5 4 2 6
xóa ngh ch th (4, 2)
– T o ra m t ngh ch th m i, ví d c p (5, 3) ụ ặ ạ ộ ị
1 5 3 4 2 6
ế ớ 1 3 5 4 2 6
ố
ế
n
Sorting S các ngh ch th ị ) 1
• Có c p s trong m t t p b t kỳ có n
( nn 2
(cid:246) (cid:230) - (cid:247) (cid:231) (cid:231) ộ ậ ấ ố ặ ł Ł
ở
trong đúng, ho c là ặ c ng ượ
s có phân n a ử
=(cid:247) 2 . ph n t ầ ử • M i c p ho c là ặ ỗ ặ – T p có th t ứ ự ậ – T p có th t ậ ứ ự • Đ i v i dãy ng u nhiên, ta gi ố ớ ặ
ng ượ ả ử c ho c ặ
(cid:246) (cid:230) -
) 1
(cid:247) (cid:231) ngh ch th ị ế
O=
2n
)
(
=(cid:247)
(cid:231)
ẫ các c p có th t ứ ự n 1 22
( nn 4
ł Ł
Sorting S các ngh ch th ị
ố
ế
261 548 3 923 195 973 289 237 57 299 594 928 515 55 507 351 262 797 788 442 97 798 227 127 474 825 7 182 929 852 504 485 45 98 538 476 175 374 523 800 19 901 349 947 613 265 844 811 636 859 81 270 697 563 976 539
• Ví d , dãy ch a đ c s p sau có 56 ph n t ụ ư ượ ầ ử ắ
ng ứ ự ượ c và 885 c p có th t ặ ứ ự
có 655 c p có th t ặ đúng.
• Công th c d báo là 770 ngh ch th ự ứ ị ế
Sorting S các ngh ch th ị
ố
ế
• Hãy xem s các ngh ch th trong 3 dãy ban đ u có 20 ế ầ ố ị
1 16 12 26 25 35 33 58 45 42 56 67 83 75 74 86 81 88 99 95 1 17 21 42 24 27 32 35 45 47 57 23 66 69 70 76 87 85 95 99 22 20 81 38 95 84 99 12 79 44 26 87 96 10 48 80 1 31 16 92
ph n tầ ử :
• Do đó:
– có 19·20/2 = 190 c pặ – Trung bình, 190/2 = 95 ngh ch th ị ế
Sorting S ngh ch th ị
ố
ế
1 16 12 26 25 35 33 58 45 42 56 67 83 75 74 86 81 88 99 95
• Dãy đ u tiên ầ
ị ế:
có 13 ngh ch th (16, 12) (26, 25) (35, 33) (58, 45) (58, 42) (58, 56) (45, 42) (83, 75) (83, 74) (83, 81) (75, 74) (86, 81) (99, 95)
ấ ấ
• S này r t th p so v i s mong đ i c a ta là (95) ớ ố ố – Do đó,đây không ph i là dãy ng u nhiên ả ợ ủ ẫ
Sorting S ngh ch th ị
ố
ế
1 17 21 42 24 27 32 35 45 47 57 23 66 69 70 76 87 85 95 99
• Dãy th hai ứ
ặ ượ : c
cũng có 13 c p ng (42, 24) (42, 27) (42, 32) (42, 35) (42, 23) (24, 23) (27, 23) (32, 23) (35, 23) (45, 23) (47, 23) (57, 23) (87, 85)
• Vì th cũng không ph i là dãy ng u nhiên ế ẫ ả
Sorting S ngh ch th ị
ố
ế
• Dãy th 3 :ứ
22 20 81 38 95 84 99 12 79 44 26 87 96 10 48 80 1 31 16 92 có 100 c p ng
(22, 20) (22, 12) (22, 10) (22, 1) (22, 16) (20, 12) (20, 10) (20, 1) (20, 16) (81, 38) (81, 12) (81, 79) (81, 44) (81, 26) (81, 10) (81, 48) (81, 80) (81, 1) (81, 16) (81, 31) (38, 12) (38, 26) (38, 10) (38, 1) (38, 16) (38, 31) (95, 84) (95, 12) (95, 79) (95, 44) (95, 26) (95, 87) (95, 10) (95, 48) (95, 80) (95, 1) (95, 16) (95, 31) (95, 92) (84, 12) (84, 79) (84, 44) (84, 26) (84, 10) (84, 48) (84, 80) (84, 1) (84, 16) (84, 31) (99, 12) (99, 79) (99, 44) (99, 26) (99, 87) (99, 96) (99, 10) (99, 48) (99, 80) (99, 1) (99, 16) (99, 31) (99, 92) (12, 10) (12, 1) (79, 44) (79, 26) (79, 10) (79, 48) (79, 1) (79, 16) (79, 31) (44, 26) (44, 10) (44, 1) (44, 16) (44, 31) (26, 10) (26, 1) (26, 16) (87, 10) (87, 48) (87, 80) (87, 1) (87, 16) (87, 31) (96, 10) (96, 48) (96, 80) (96, 1) (96, 16) (96, 31) (96, 92) (10, 1) (48, 1) (48, 16) (48, 31) (80, 1) (80, 16) (80, 31) (31, 16)
c: ượ ặ
Sorting T ng k t ế ổ
• Gi ớ ế
ỗ ầ O(1) b nh b sung ộ ớ ổ
i thi u v s p x p: ề ắ ệ – Các gi t thi ế ả – S p x p t i ch c n ế ạ ắ – Các k thu t s p x p ế ậ ắ ỹ
• insertion, exchanging, selection, merging, distribution ự
– Phân lo i th i gian th c hi n: ệ O(n) O(n ln(n)) ạ ờ
• Kh o sát phép ch ng minh t ng quát c a m t ộ ứ
W gi i là ủ (n ln(n)) O(n2) ả i thu t s p x p có c n d ế ả ậ ắ ậ ổ ướ
