Thuật toán sắp xếp nhanh

Bài 2: M t s ph ng pháp s p x p ộ ố ươ ế ắ

ắ

I. Thu t toán s p x p nhanh - Quick Sort ế Ý t ưở

ố

Gi i thu t QuickSort làm vi c nh sau: ậ ả

ư làm biên: th ng ch n là ph n t ậ ng: Có dãy s : a1, a2, ..., an ệ ầ ử Ch n ọ x là m t ph n t ộ ườ ầ ử ở ọ

gi a dãy s . ố ữ

Phân ho c dãy thành 3 dãy con ạ

ớ

1. ak <= x , v i k = 1..i 2. ak = x , v i k = i..j ớ 3. ak > =x , v i k = j..N ớ

Ak<=x Ak=x Ak>=x

ầ ử

N u s ph n t phân ho ch dãy 1, 3 theo ph ế ụ trong dãy con 1, 3 l n h n 1 thì ta ti p t c ớ i thì: d ng. ng pháp trên. ơ c l Ng ượ ạ ế ố ạ ươ ừ

i thu t phân ho ch dãy am, am+1, ., an thành 2 dãy con: ậ ạ

Gi B c 1 : Ch n tùy ý m t ph n t a[k] trong dãy là giá tr biên, ả ướ ầ ử ọ ộ ị

a[i], a[j] n m sai m<= k <=n: x = a[k]; i = m; j = n; ệ ệ ầ ử ặ ỉ ằ

B c 2 : Phát hi n và hi u ch nh c p ph n t ướ v trí: ị

B c 2a : Trong khi (a[i]x) j--; B c 2c : N u i<= j ướ ướ ướ ế

ứ

// a[i]>= x; a[j]<=x mà a[j] đ ng sau a[i] Hoán v (a[i],a[j]); ị

i++; j--;

ướ

i B c 2.//ch a xét h t m ng ặ ạ ướ ư ế ả

B c 3 : N u i <= j: ế i: c l Ng ượ ạ L p l D ngừ

i thu t s p x p QuickSort m t cách đ ể ả ậ ắ ế ộ ệ

Có th phát bi u gi ể qui nh sau : ư

B c 1 : Phân ho ch dãy a

m … an thành các dãy con :

ướ ạ

- Dãy con 1 : am.. aj <= x - Dãy con 2 : aj+1.. ai-1 = x - Dãy con 1 : ai.. an >= x

ướ

ề ầ ử ơ B c 2 : ế

// dãy con 1 có nhi u h n 1 ph n t m.. aj // dãy con 3 có nhi u h n 1 ph n t ế ề ầ ơ ử

i.. ar

N u ( m < j ) Phân ho ch dãy a ạ N u ( i < n ) Phân ho ch dãy a ạ

Ví d : ụ Cho dãy s a: ố 2 12 6 5 4 15

8 1 ạ l =1, r = 8: x = A[4] =5 Phân ho ch đo n ạ

hân ho ch P đo n l =1, r = 3: x = A[2] = 2 ạ ạ

hân ho ch P đo n l = 5, r = 8: x = A[6] = 6 ạ ạ

hân ho ch đo n l = 7, r = 8: x = A[7] = 6 ạ ạ

D ng. ừ Cài đ t ặ

Ðánh giá gi

ậ ả ệ ủ ụ ộ i thu t QuickSort ph thu c

ạ

ườ ượ ầ ử ớ

ằ còn l ế l n h n (hay b ng) n a s ử ố ạ

, và nh h n (hay b ng) n a s ph n t ầ ử ằ ằ

i thu t ậ Hi u q a th c hi n c a gi ự ệ Tr ch n đ ọ ph n t ầ ử m c, khi đó dãy đ ố log2(n) b ế ắ

đ c phân ho ch ph n t ạ

cướ phân ho ch thì s p x p xong. Nh ng n u m i b ế ư ị ự ạ ầ ử ượ ẽ ị ố

, ph n còn l ầ ầ ỉ

ầ ử ệ

ả ủ ệ vào vi c ch n giá tr m c. ọ ị ố ng h p t ề t nh t x y ra n u m i l n phân ho ch đ u ợ ố ỗ ầ ấ ả c ph n t ử ố median (ph n t ầ ử ơ i) làm ỏ ơ c phân chia thành 2 ph n b ng nhau và c n ầ ầ ượ ạ c ch n có ỗ ướ ọ giá tr c c đ i (hay c c ti u) là m c, dãy s b phân chia thành 2 ể ự i g m ph n không đ u: m t ph n ch có 1 ph n t ạ ồ ề ầ ử ầ ộ ớ ắ c phân ho ch m i s p , do v y c n th c hi n n b (n-1) ph n t ạ ướ ậ ầ x p xong. Ta có b ng t ng k t ổ ả ế ự ế

Tr ng h p ườ ợ Ð ph c t p ộ ứ ạ

T t nh t ấ ố

X u nh t n*log(n) n2 ấ ấ

II. Radix sort

Ý t ưở

ớ ậ ướ

ế ế ng: Khác v i các thu t toán tr ậ ộ ư

ậ ộ ướ ơ ở ể ắ

ạ ắ

t r ng, đ đ a m t kh i l ố ượ

c, Radix sort là m t thu t toán ng hoàn toàn khác. N u nh trong các ti p c n theo m t h ị ủ thu t toán khác, c s đ s p x p luôn là vi c so sánh giá tr c a ệ ế ậ thì Radix sort l 2 ph n t ư i d a trên nguyên t c phân lo i th ạ ự ầ ử c a b u đi n. ệ ủ ư Ta bi ế ằ i nh n ng t ng th l n đ n tay ổ ư ớ ệ ế ườ ư ề

ườ ứ ộ ng khác nhau, b u đi n th ư

c tiên, các th đ n cùng m t t nh, thành ph s đ Tr ậ ở ộ ệ ố ướ ố ẽ ượ c ấ ộ ỉ

ng ng. s p chung vào m t lô đ g i đ n t nh thành t ắ ộ

ể ư nhi u đ a ph ng ươ ị ch c m t h th ng phân lo i th phân c p: ạ ư ế ể ử ế ỉ B u đi n các t nh thành này l ỉ ư ự ạ

ệ ư ế ế ộ

ứ ậ

ử ế c trao đ n tay ng ế

ươ ứ i th c hi n công vi c t ệ . Các th đ n cùng m t qu n, huy n s đ t ẽ ượ ệ ự ậ m t lô và g i đ n qu n, huy n t ệ ươ ộ th s đ ư ẽ ượ ườ công vi c s p x p th không quá n ng nh c. ư ệ ằ ệ ươ ng c x p vào chung ứ ng ng. C nh v y, các b c ứ ư ậ i nh n m t cách có h thông mà ậ ệ ặ ộ ọ ế

i qui trình trên, đ s p x p dãy a1, a2, ..., an, Mô ph ng l ế ạ ỏ

gi ể ắ i thu t Radix Sort th c hi n nh sau: ả ư ự

ệ c tiên, ta có th gi Tr ai trong dãy: a1, ậ ướ

s m i ph n t ầ ử ể ả ử ỗ i đa m ch s . ữ ố ố l n l ầ ử ầ ượ ng t ự ệ ơ t theo các ch s hàng đ n ữ ố vi c phân lo i th theo t nh ỉ ư ạ

a2, ..., an là m t s nguyên có t ộ ố Ta phân lo i các ph n t ạ v , hàng ch c, hàng trăm, . t ụ ị thành, qu n huy n, ph ươ ng xã, .. ườ ệ ậ

c th c hi n thu t toán nh sau: ậ ự ư ệ

// k cho bi t ch s dùng đ phân lo i hi n hành Các b ướ B c 1 : ướ ế ữ ố ể ạ

k = 0; ơ ệ ụ

B c 2 : //T o các lô ch a các lo i ph n t // k = 0: hàng đ n v ; k = 1:hàng ch c; ị khác nhau ầ ử ướ ứ ạ

Kh i t o 10 lô B0, B1, ., B9 r ng; ạ ở ạ ỗ

B c 3 : ướ

Ð t ai vào lô Bt v i t = ch s th k c a ai; For i = 1 .. n do ặ ữ ố ứ ủ ớ

ướ

N i B0, B1, ., B9 l i (theo đúng trình t ) thành a. ạ ự

B c 4 : ố B c 5 : ướ

c 2. i b ở ạ ướ

k = k+1; N u k < m thì tr l ế i: D ng c l Ng ừ ượ ạ

Ví d ụ Cho dãy s a: ố 701 1725 999 9170 3252 4518 7009 1424 428 1239 8425 7013 Phân lô theo hàng đ n v : ơ ị

0701 12

1725 11

0999 10

9170 9

3252 8

4518 7

7009 6

1424 5

0428 4

1239 3 0999

8425 2 4518 7009 1725

1 0428 1239 7013 9170 0701 3252 7013 1424 8425

CS A 0 1 2 3 4 5 6 7 8 9

Các lô B dùng đ phân lo i ể ạ

Phân lô theo hàng ch c: ụ

0999 12

7009 11

1239 10

4518 9

0428 8

1725 7

8425 6

1424 5

0428 7013 4

1725 3252 3

0701 7009 4518 8425 2

9170 0701 7013 1424 1239 3252 9170 0999 1

CS A 0 1 2 3 4 5 6 7 8 9

Phân lô theo hàng trăm:

12 0999

11 9170

10 3252

9 1239

8 0428

7 1725

6 8425

5 1424

4 4518

3 7013 0428

2 7009 7013 3252 8425 1725

0701 1 0701 7009 9170 1239 1424 4518 0999

CS A 0 1 2 3 4 5 6 7 8 9

Phân lô theo hàng ngàn:

12 0999

11 1725

10 0701

9 4518

8 0428

7 8425

6 1424

5 3252

4 1239

3 9170 0999 1725

2 7013 0701 1424 7013

1 7009 0428 1239 3252 4518 7009 8425 9170

CS A 0 1 2 3 4 5 6 7 8 9

L y các ph n t t các lô B0, B1, ., B9 n i l i thành a: ầ ử ừ ấ ố ạ

12 9170

11 8425

10 7013

9 7009

8 4518

7 3252

6 1725

5 1424

4 1239

3 0999

2 0701

1 0428

CS A 0 1 2 3 4 5 6 7 8 9

Ðánh giá gi i thu t ậ

V i m t dãy n s , m i s có t ả ộ ố ố ậ ỗ ố

ầ ự ớ ệ

ch đ

ể ệ ự

ố ọ ợ ấ ấ ườ

ớ ắ ư t nh t. M i dãy ố ế

ng h p x u nh t và t ấ c s p v i chi phí nh nhau n u chúng có cùng s .

ậ ệ ế ắ ớ

ả ư ụ ự ố

ậ ơ ữ ố ủ ừ

ố ượ ố ậ ề

ự ế ỗ ổ

ể

ả

ễ ể ể ấ ợ ễ ấ

, thu t toán Radix sort i đa m ch s , thu t toán ữ ố th c hi n m l n các thao tác phân lô và ghép lô. Trong thao tác c xét đúng m t l n, khi ghép cũng phân lô, m i ph n t ộ ầ ầ ử ỉ ượ ỗ v y. Nh v y, chi phí cho vi c th c hi n thu t toán hi n nhiên ậ ệ ư ậ ậ là O(2mn) = O(n). NH N XÉT Ậ Thu t toán không có tr ậ s đ u đ ượ ố ề ph n tầ ử và các khóa có cùng chi u dài ề Thu t toán cài đ t thu n ti n v i các m ng có khóa s p x p là ặ hay s ) h n là khóa s nh trong ví d do tránh chu i (ký t ố ỗ đ c chi phí l y các ch s c a t ng s . ố ấ ượ ng lô nhi u (10 khi dùng s th p phân, 26 Tuy nhiên, s l ướ ủ ti ng anh, ...) nh ng t ng kích th c c a khi dùng chu i ký t ư t c các lô ch b ng dãy ban đ u nên ta không th dùng m ng t ả ấ ả ầ ỉ ằ ữ ệ đ bi u di n B (B0->B9). Nh v y, ph i dùng c u trúc d li u ư ậ ể ể đ ng đ bi u di n B => Radix sort r t thích h p cho s p x p ế ắ ộ trên danh sách liên k t.ế ắ ầ ử ề ậ

Khi s p các dãy không nhi u ph n t s m t u th so v i các thu t toán khác. ẽ ấ ư ế ậ ớ

III. S p x p cây - Heap sort ế ắ

1.Ý t

c i, ph ng: ậ

ưở Nh n xét: Khi tìm ph n t ự ế ọ b ng pháp ươ ấ ở ướ c các thông tin đã có ượ

c do các phép so sánh nh nh t ầ ử ỏ s p x p ch n tr c ti p không t n d ng đ ậ ụ ế ắ c i-1. b đ ở ướ ượ

ự ậ ộ

ể i ta tìm cách xây d ng m t thu t toán s p ắ ượ ể

ắ M u chôt đ gi Vì lý do trên ng ườ x p có th kh c ph c nh ụ ế ể ả ề ừ ả

c đi m này. ấ ế c m t c u trúc d li u cho phép tích lũy các thông tin v s i quy t v n đ v a nêu là ph i tìm ra ề ự

trong qua trình s p x p. ấ đ ộ ấ ượ so sánh giá tr các ph n t ị ữ ệ ầ ử ế

Gi ượ ố c b

ế trí theo quan h so sánh và t o thành s đ d ng cây nh sau : s d li u c n s p x p là dãy s : ả ử ữ ệ ầ ắ ơ ồ ạ ạ ệ ắ ố 5 2 6 4 8 1 đ ư

Trong đó m t ph n t m c i chính là ph n t ầ ử ở ứ

ầ ử l n trong ớ ố ủ m c 0 (nút g c c a ở ứ ầ ử ở ứ i+1, do đó ph n tầ ử

ộ m c ầ ử ớ

c p ph n t ặ cây) luôn là ph n t N u lo i b ph n t ạ ỏ

ế ấ ề ư ỉ ả ậ

ạ ỏ ế

ể ử ụ ế ế ượ ả

c k ti p có th s d ng l i. b ở ướ

l n nh t c a dãy. ấ ủ g c ra kh i cây (nghĩa là đ a ph n t ầ ử ỏ ầ ử ố l n nh t v đúng v trí), thì vi c c p nh t cây ch x y ra trên ậ ị ệ ớ m i lo i b , còn các nhánh nh ng nhánh liên quan đ n ph n t ầ ử ớ ữ ạ i khác đ c b o toàn, nghĩa là b ướ các k t qu so sánh c hi n t ế ệ ạ ả Trong ví d trên ta có : ụ

ế ị ể ỗ ố

Lo i b 8 ra kh i cây và th vào các ch tr ng giá tr -∞ đ ạ ỏ ti n vi c c p nh t l ệ ậ ỏ i cây : ậ ạ ệ

Ti n hành nhi u l n vi c lo i b ph n t ề ầ ầ ử ố ủ ạ ỏ

t c các ph n t ầ ử ủ ế

ề ẽ ế ắ

ế đ n khi t ế ph n t ầ ử đây là ý t i thu t s p x p cây. g c c a cây cho ệ c a cây đ u là -∞, khi đó x p các ấ ả lo i b trên cây s có dãy đã s p x p. Trên theo th t ứ ự ạ ỏ ng c a gi ả ủ ưở ậ ắ ế

ữ ệ ể 2. C u trúc d li u Heap ặ ệ ộ

ch c m t c u trúc l u tr ữ ữ ệ ả

ấ Tuy nhiên, đ cài đ t thu t toán này m t cách hi u qu , ả ể d li u có kh năng th trong cây v i n ô nh thay vì ậ ư ộ ấ c quan h c a các ph n t ầ ử ớ ớ

c n ph i t ả ổ ứ ầ hi n đ ệ ủ ượ ệ 2n-1 nh trong ví d . ụ ư

ệ ng pháp s p x p Heapsort do ế ắ

c các khó khăn trên. Khái ni m heap và ph ấ J.Williams đ xu t đã gi ề ươ i quy t đ ế ượ ả

ị

s xét tr Gi ng h p s p x p tăng d n, khi đó Heap đ Ð nh nghĩa Heap: ả ử ườ ợ ắ ế ầ

ầ ử ap, a2 ,... , aq tho các quan h ả c ượ ệ

đ nh nghĩa là m t dãy các ph n t ộ ị sau v i m i i thu c [p, q]: ộ ọ ớ

1/. ai >= a2i

2/. liên ặ ầ ử

ai >= a2i+1 {(ai , a2i), (ai ,a2i+1) là các c p ph n t đ i } ớ

Heap có các tính ch t sau : ấ

ế ộ

Tính ch t 1 : N u ap , a2 ,... , aq là m t heap thì khi c t b hai đ u c a heap, dãy con còn l ắ ỏ ộ i v n là m t ầ ủ ạ ẫ ộ ố

ấ m t s ph n t ầ ử ở heap.

Tính ch t 2 : N u ap , a2 ,... , aq là m t heap thì ph n t ầ ử a1 ộ

ấ (đ u heap) luôn là ph n t l n nh t trong heap. ầ ấ

Tính ch t 3 : M i dãy ap , a2 ,... , aq, dãy con aj, aj+1,…, ar

ế ầ ử ớ ọ ớ ấ ộ t o thành m t heap v i j=(q div 2 +1). ạ

ả ả i thu t Heapsort : i thu t Heapsort tr i qua 2 giai đo n : ả

ạ ầ

ệ ế ắ Ð a ph n t cu i dãy: Gi Gi Giai đo n 1 :Hi u ch nh dãy s ban đ u thành heap; ỉ Giai đo n 2: S p x p dãy s d a trên heap: ấ ề ị ậ ậ ạ ạ B c 1: ướ ầ ử l n nh t v v trí đúng ố ố ự ớ ư ở ố

r = n; Hoánv (a1 , ar );

Lo i b ph n t

i c a dãy t ị ầ ử ớ ạ ủ l n nh t ra kh i heap: r = r-1; ỏ ấ ừ a1 , a2 ... ar thành m tộ ạ ỏ ầ

B c 2: ướ Hi u ch nh ph n còn l ỉ ệ heap.

B c 3: ướ ầ ử ): L p l ặ ạ i B c 2 ướ

ế c l Ng ượ ạ N u r>1 (heap còn ph n t i : D ng ừ

ạ ấ ệ ể ự

ặ

an/2, an/2-1, ., a1 ta s nhân đ ượ ẽ

ằ D a trên tính ch t 3, ta có th th c hi n giai đo n 1 b ng ự heap m c nhiên an/2+1 , an/2+2 ... an, sau đó cách b t đ u t ắ ầ ừ c heap thêm d n các ph n t ầ ử ầ theo mong mu n. ố Ví d ụ Cho dãy s a:ố 12 2 8 5 1 6 4 15 Giai đo n 1: hi u ch nh dãy ban đ u thành heap ệ ạ ầ ỉ

Giai đo n 2: S p x p dãy s d a trên heap : ố ự ế ạ ắ

th c hi n t ng t cho r=5,4,3,2 ta đ c: ự ệ ươ ự ượ

Cài đ t ặ

Ðánh giá gi i thu t ả ậ

ự ắ ỗ c m i

b ướ ầ ạ ấ ề ổ

Trong giai đo n s p x p ta c n th c hi n n-1 b ướ ệ ầ ế (n-1), log2 (n-2), … 1 phép đ i ch i. ỗ 2 Nh v y đ ph c t p thu t toán Heap sort O(nlog2n) ậ c c n nhi u nh t là log ộ ứ ạ ư ậ