Bài giảng Cấu trúc dữ liệu - Bài 2: Tìm kiếm và sắp xếp

Tìm kiếm và sắp xếp Tìm kiếm và sắp xếp

Nội dung trình bày

 Tìm ki mế  S p x p ắ

ế

C u trúc d li u - Khoa CNTT 2 ữ ệ ấ

2.1 Tìm kiếm

ng xuyên

& th

thao tác quan tr ngọ

ườ

 Tìm ki m là ế trong tin h c. ọ - Tìm ki m m t nhân viên trong danh sách nhân viên. ộ - Tìm m t sinh viên trong danh sách sinh viên c a m t ủ

ế ộ

ộ

l p…ớ

- Tìm ki m m t tên sách trong th vi n.

ư ệ

ế

ộ

C u trúc d li u - Khoa CNTT 3 ữ ệ ấ

2.1 Tìm kiếm

 Tìm ki m là

quá trình xác đ nh m t đ i t

ị

ế

ố ượ

ả ả ề ỉ ố

ố ượ

ượ

ế

ặ

ng trong t p đó.

ng nào ộ ố ượ . K t qu tr v là ế c (n u có) ho c m t ch s (n u ộ ậ ủ

ế ố ượ

ị

đó trong m t t p các đ i t ộ ậ đ i t ng tìm đ có) xác đ nh v trí c a đ i t ị  Vi c tìm ki m d a theo m t tr

ộ ườ

ng, tr

khóa (key) c a vi c tìm ki m.

ng nào đó c a đ i ố ủ

ủ ế

ệ t ượ

 VD: đ i t

ng sinh viên có các d li u {

ự ế ng này là ườ ố ượ

ế ng ch n là ọ

ườ

ệ ữ ệ MaSV, HoTen, DiaChi,…}. Khi đó tìm ki m trên danh sách sinh viên thì khóa th MaSV ho c ặ HoTen.

C u trúc d li u - Khoa CNTT 4 ữ ệ ấ

2.1 Tìm kiếm

c mô t

nh sau: ư

- T p d li u đ

 Bài toán đ ậ ọ

ể ư

ả s a1, a2,..,an. Gi c l u tr là dãy ả ử ữ ượ ư ch n c u trúc d li u m ng đ l u tr dãy s này ố ả ữ ệ trong b nh chính, có khai báo:

ớ

ữ int a[n]; int x;

x, có ki u nguyên:

ượ ữ ệ ấ ộ - Khóa c n tìm là ầ

ể Tìm kiếm

Tìm kiếm tuyến tính

Tìm kiếm nhị phân

Tập dữ liệu đã được sắp xếp

Tập dữ liệu bất kỳ

C u trúc d li u - Khoa CNTT 5 ữ ệ ấ

2.1.1 Tìm kiếm tuyến tính

 Ý t

ng chính:

ệ

ừ

ầ ự t duy t tu n t ế

ph n t đ u tiên, ầ ử ầ ng ng t so sánh khóa tìm ki m v i khoá t ứ ươ ớ trong danh sách. Cho đ n khi g p ế

ầ ử

ệ ế

 Các b

ưở l n l ầ ượ c a các ph n t ủ ph n t ầ ử ầ ế ướ

ặ ư

ặ c n tìm ho c đ n khi duy t h t danh sách. ế : c ti n hành nh sau

: i = 1; : So sánh a[i] v i x, có hai kh năng

- B c 1 ướ - B c 2 ướ

ả

ớ D ngừ

c 3

// xét ph n t

k ti p trong m ng

ả

D ngừ

c 2

 A[i] = x: Tìm th y. ấ (cid:222)  A[i] „ x: Sang b ướ : i = i + 1 - B c 3 ướ ầ ử ế ế ấ (cid:222)  N u i > N: H t m ng, không tìm th y. ả ế ế i b N: Quay l  N u i ế ạ ướ

C u trúc d li u - Khoa CNTT 6 ữ ệ ấ

2.1.1 Tìm kiếm tuyến tính

ụ

ị

 Ví d : Cho dãy s a, giá tr tìm x = 8: ố 2

Minh h a tìm ki m tuy n tính

ế

ọ

X = 8X = 8

Tìm được Tìm được

1212

22

55

88

11

66

44

C u trúc d li u - Khoa CNTT 7 ữ ệ ấ

2.1.1 Tìm kiếm tuyến tính

ậ

ế

 Thu t toán tìm ki m tuy n tính int Search(int a[], int n, int key) {

int i =0; while (i

i++; if (i >= n)

return -1;

// tìm không th yấ

else

return i;

// tìm th y t

i v trí i

ấ ạ ị

}

C u trúc d li u - Khoa CNTT 8 ữ ệ ấ

2.1.1 Tìm kiếm tuyến tính

ậ

ả ế

ế

 Thu t toán tìm ki m tuy n tính c i ti n ế int Search(int a[], int n, int key) {

// thêm ph n t

th n+1

ầ ử ứ

int i =0; a[n] =key; while (key != a[i])

i++; if (i == n)

return -1;

// tìm h t m ng nh ng không có x

ế

ả

else

return i;

// tìm th y x t

i v trí i

ấ

ạ ị

}

C u trúc d li u - Khoa CNTT 9 ữ ệ ấ

2.1.1 Tìm kiếm tuyến tính

ế

ụ trong m ng, do v y đây là ph

ộ ng pháp

không ph thu c vào th t i thu t tìm ki m tuy n tính ế ươ ậ

ứ ự c a ủ t ng quát ổ

ả

 Nh n xét ậ - Gi ậ ả ầ ử ể

các ph n t nh tấ đ tìm ki m trên m t dãy b t kỳ

ế

ộ

ậ

ể ượ ưở

ặ ả

ậ

ẽ

ậ

nhi u cách khác nhau, - M t thu t toán có th đ ộ ệ . Ví d ụ k thu t cài đ t nh h ề ỹ nh thu t toán Search c i ti n s ch y nhanh h n thu t toán tr

ấ c cài đ t theo ề ặ ng nhi u đ n t c đ th c hi n ộ ự ế ố ậ ơ ạ ả ế c do vòng l p while ch so sánh m t đi u ki n... ộ ỉ

ư ướ

ề

ệ

ặ

C u trúc d li u - Khoa CNTT 10 ữ ệ ấ

5.1.2 Tìm kiếm nhị phân

dãy khóa

ượ

c áp d ng trên ụ k[n].

... £

Phép tìm ki m nh phân đ ị ế k[2] £ đã có th tứ ự: k[1] £

C u trúc d li u - Khoa CNTT 11 ữ ệ ấ

5.1.2 Tìm kiếm nhị phân

 Ý t

ạ

ớ

c h t ta xét ph n t

ngưở - Gi ả ử ế

ế

s ta c n tìm trong đo n a[left,..,right] v i khóa tìm gi a là a[mid], v i ớ

ử ữ

ầ

ạ

ế tìm ki m t

ầ ki m là x, tr ướ mid=[left+right]/2.  N u ế a[mid] < x thì có nghĩa là đo n a[left] đ n ừ

ứ

ế

a[right] ch ch a khóa < x, ta ti n hành ỉ a[mid+1] đ n a[right]. ế

ế tìm ki m t

 N u ế a[mid] > x thì có nghĩa là đo n a[m] đ n ừ

ứ

ế

ạ a[right] ch ch a khoá > x, ta ti n hành ỉ a[left] đ n a[mid-1].

ế

 N u ế a[mid] = x thì vi c tìm ki m thành công. ệ ế . - Quá trình tìm ki m ế th t b i n u left > right ấ ạ ế

C u trúc d li u - Khoa CNTT 12 ữ ệ ấ

2.1.2 Tìm kiếm nhị phân

 Các b

ế

ướ

t c ph n t

ấ ả

ầ ử

c ti n hành - B1: left =1, right = n - B2: mid = (left + right)/2

// tìm ki m trên t ế // l y m c so sánh ố

ấ

ả D ngừ

// tìm ti p trong dãy a[left]...a[mid-1]

 A[mid] < x:

// tìm ti p trong dãy a[mid+1]...a[right]

So sánh a[mid] v i x, có 3 kh năng ớ  a[mid] = x: Tìm th y ấ (cid:222)  a[mid] > x: ế right = mid -1; ế

left = mid +1

- B3:

L p B2

ặ

 N u left ế c l  Ng ượ ạ

tìm ti p ế (cid:222) ầ ử (cid:222) right // còn ph n t // đã xét h t các ph n t i: D ng ầ ử ế ừ

C u trúc d li u - Khoa CNTT 13 ữ ệ ấ

2.1.2 Tìm kiếm nhị phân

ướ

Ví d :ụ cho dãy s g m 8 ph n t ầ ử 6

ố ồ 4

bên d 8

i và x = 8: 15

X = 8X = 8

22

44

66

88 1212

1515

11 Left = 1

55 Mid = 4

Right = 8

Đoạn tìm kiếm

X = 8X = 8 ==

11

22

44

55 1212

88 Mid = 6

1515 Right = 8

66 Left = 5

Đoạn tìm kiếm

C u trúc d li u - Khoa CNTT 14 ữ ệ ấ

2.1.2 Tìm kiếm nhị phân

 Thu t toán tìm ki m NP BinarySearch ế

ậ

int BinarySearch(int key){

int left = 0, right = n-1, mid; while (left <= right){

mid = (left + right)/ 2; if (a[mid] == key)

// l y đi m gi a ữ ể c // n u tìm đ ượ

ấ ế

return mid;

// tìm đo n bên ph i mid

if (a[mid] < key)

ả

ạ

left = mid+1;

else

right = mid-1;

// tìm đo n bên trái mid

ạ

} return -1;

// không tìm đ

cượ

}

C u trúc d li u - Khoa CNTT 15 ữ ệ ấ

2.1.2 Tìm kiếm nhị phân

i nh phân d a vào

 Nh n xét ậ - Thu t gi ả

ậ

ệ

ầ ử ng trong quá trình tìm ki m, do v y ch ỉ ậ

quan h giá tr c a các ph n t ị ủ ế

ự ướ

ớ dãy đã có th t

.ứ ự

ế

ơ ị

ả

ị trong m ngả đ đ nh h ể ị c v i áp d ng đ ượ ụ i nh phân - Thu t gi ị ả ậ - Tuy nhiên khi áp d ng thu t gi ế

ậ ắ

i nh phân thì c n ph i quan ầ c s p ắ ả

ả . Vì khi m ng đ

ả ượ

tìm ki m nhanh h n tìm ki m tuy n tính. ụ tâm đ n ế chi phí cho vi c s p x p m ng r i thì m i tìm ki m nh phân. th t

ứ ự ồ

ệ ế

ớ

ị

C u trúc d li u - Khoa CNTT 16 ữ ệ ấ

2.2 Sắp xếp

ạ

i các ph n t ố ng theo m t th t

ố ượ

ầ ử ứ ự

ộ

S p x p là quá trình b trí l ế ắ c a m t t p đ i t ộ ậ ủ nh t đ nh. ấ ị

 Ví d : ụ

ươ

{1, 2, 5, 7, 9, 12}, {14, 12, 7, 5, 2, 1} {“An” “Binh” “D ng” “H ng”} ươ ộ ệ

ế

ắ

ọ i, s p x p k t xu t cho các

- Do các yêu c u tìm ki m thu n l

 Vi c s p x p là m t bài toán ph bi n trong tin h c. ế

ổ ế ậ ợ

ế

ầ

ấ

ắ

b ng bi u...

ể

ả

C u trúc d li u - Khoa CNTT 17 ữ ệ ấ

2.2 Sắp xếp

ng đ

ườ

c t ượ ổ

ch c thành m ng các m u ả

ứ

ẫ

 D li u th ữ ệ tin d li u

ng d li u

ỗ

ườ

ng có m t s các tr ộ ố

ườ

ữ ệ

ữ ệ  M i m u tin th ẫ khác nhau.

 Tr

ng tham gia quá trình tìm ki m g i là khoá

ế

ọ

 Vi c s p x p s đ

ườ (key). ệ

ẽ ượ

ế

ắ

c ti n hành d a vào giá tr ị ự

ế

khoá này.

C u trúc d li u - Khoa CNTT 18 ữ ệ ấ

2.2 Sắp xếp

 Các ph

ng pháp s p x p

ế

ắ

ươ 1. Selection Sort (*) Insertion Sort (*) 3. Bubble Sort (*) Interchange Sort

5. Shell sort 6. Quick sort 7. Radix...

C u trúc d li u - Khoa CNTT 19 ữ ệ ấ

2.2 Sắp xếp

Đ ti n cho vi c minh h a các thu t toán

ọ

ậ

ể ệ

bài toán: ả ả ế

ộ

ệ : bài toán nh sau ầ ử e, m i ph n t

ầ ử

ả

 Mô t s p x p ta mô t ư ắ - Cho m t m ng các ph n t ả ộ

ỗ ế

ắ ị

trong m ng có m t thu c tính khóa. Hãy s p x p tăng ho c gi m các ả ặ ộ ph n t ầ ử - Do m i ph n t ỗ

ọ k[1..n] là m ng ả

trong m ng theo giá tr khóa này ả có giá tr khoá nên ta g i ị trong ầ ử - Yêu c u: s p x p các giá tr này sao cho m ng ị

k có th ứ

ả

ầ

ầ ử các khóa c a các ph n t ủ ắ tăng ho c gi m. ặ

ế ả

t ự

C u trúc d li u - Khoa CNTT 20 ữ ệ ấ

2.2.1 Selection Sort

 Ý t - L

ứ

ấ

ng chính t th nh t, ch n trong dãy khoá k[1..n] ra khoá nh ỏ k[1] s tr thành khoá

ọ ị ớ

ẽ ở

ổ

- L

nh t và đ i giá tr v i k[1], khi đó nh nh t. ấ ứ

t th hai, ch n trong dãy khoá k[2..n] ra khóa nh ỏ

ưở ượ ấ ỏ ượ ấ

iớ k[2].

ọ nh t và đ i giá tr v ị ổ ... - L

ượ

ị

t n-1, ch n giá tr nh nh t trong k[n-1] và k[n] ra ỏ ấ ị ớ k[n-1]. khoá nh nh t và đ i giá tr v i

ọ ấ

ỏ

ổ

C u trúc d li u - Khoa CNTT 21 ữ ệ ấ

2.2.1 Selection Sort

 Các b

c th c hi n

ệ

ự

a[min] nh nh t trong dãy hi n hành t

ệ

ấ

ừ

ầ ử

ỏ

L p B2

ặ

ướ - B1: i = 1 - B2: Tìm ph n t a[i] đ n a[n] ế - B3: Hoán v a[i] và a[min] ị - B4: N u i < n -1 thì i= i+1 ượ ạ (cid:222) i c l  Ví d : cho dãy s nh sau:

ế Ng ụ 12 Minh h a ph

ọ

ươ

D ng ừ ư ố 8 6 ng pháp ch n nh sau ọ

(cid:222)

C u trúc d li u - Khoa CNTT 22 ữ ệ ấ

2.2.1 Selection Sort

1515

1212

min=5min=5

i=1i=1

1212

1515

i=2i=2

1212

1515

i=3i=3

min=7min=7

C u trúc d li u - Khoa CNTT 23 ữ ệ ấ

2.2.1 Selection Sort

1212

1515

i=4i=4

1212

1515

i=5i=5

min=6min=6

1212

1515

i=7i=7

1212

1515

C u trúc d li u - Khoa CNTT 24 ữ ệ ấ

2.2.1 Selection Sort

ặ

 Cài đ t Selection Sort void SelectionSort(int a[], int n) {

ầ ử

// l u ch s ph n t ỉ ố // duy t qua n-1 ph n t

nh nh t ấ ỏ ầ ử

ệ

int min; for(int i = 0; i < n-1; i++) {

min = i; for(int j = i+1; j < n; j++) if (a[j] < a[min]) min = j;

Swap(a[min], a[i]);

}

C u trúc d li u - Khoa CNTT 25 ữ ệ ấ

2.2.2 Bubble Sort

 Ý t

ng chính

đ i ch các c p ph n t

k c n

ỗ

ầ ử ế ậ đ đ a

ể ư

ặ

ưở - Xu t phát t ấ ph n t ầ ử - Sau đó

c ti p theo không xét ph n t

đó n a. Do v y

ầ ử

ữ

ậ

cu i dãy, ổ ố ừ nh h n v đ u. ề ầ ỏ ơ b ế ở ướ l n ầ x lý th i s có v trí đ u dãy là i.

ứ ẽ

ầ

ị

i x lý trên cho đ n khi không còn c p ph n t

nào đ

ử ặ ạ ử

ầ ử

ế

ặ

ượ

- L p l xét.

C u trúc d li u - Khoa CNTT 26 ữ ệ ấ

2.2.2 Bubble Sort

 Các b

ế

ầ

ướ - B1: i=1; - B2: j=n; // duy t t

ử ố

ượ

c v v trí i ề ị

Trong khi (j>i) th c hi n:

c ti n hành // l n x lý đ u tiên ầ cu i dãy ng ệ ừ ệ ự

ổ

N u a[j] < a[j-1]: Hoán đ i a[j] và a[j-1] ế j = j -1;

ế ế

ầ

ử N u i > n-1: H t dãy

// l n x lý k ti p ế

D ngừ

c l ượ ạ

ố

i: quay l ạ ắ ọ

- B3: i = i+1; ế Ng ụ 12

 Ví d : Minh h a s p x p dãy s sau: 8

i B2 ế 5

(cid:222)

C u trúc d li u - Khoa CNTT 27 ữ ệ ấ

2.2.2 Bubble Sort

1212

22

88

55

11

66

44 1515

j=7j=7 i=1i=1

1212

22

88

55

44

66 1515

11

j=5j=5 i=1i=1

1212

22

88

11

55

44

66 1515

i=1i=1 j=4j=4

C u trúc d li u - Khoa CNTT 28 ữ ệ ấ

2.2.2 Bubble Sort

22

88 1212

11

55

44

66 1515

j=3j=3 i=1i=1

1212

11

22

88

55

44

66 1515

i=1i=1 j=2j=2

1212

22

88

55

44

66 1515

11

i=2i=2 j=6j=6

C u trúc d li u - Khoa CNTT 29 ữ ệ ấ

2.2.2 Bubble Sort

22

88 1212

55

66 1515

44

11

j=5j=5 i=2i=2

1212

22

44

88

55

66 1515

11

i=2i=2 j=3j=3

1212

44

88

55

66 1515

11

22

i=3i=3 j=6j=6

C u trúc d li u - Khoa CNTT 30 ữ ệ ấ

2.2.2 Bubble Sort

1212

44

55

88

66 1515

11

22

i=3i=3 j=4j=4

1212

55

88

66 1515

11

22

44

i=4i=4 j=7j=7

1212

55

66

88 1515

11

22

44

i=4i=4 j=5j=5

C u trúc d li u - Khoa CNTT 31 ữ ệ ấ

2.2.2 Bubble Sort

1212

66

88 1515

11

22

44

55

i=5i=5 j=6j=6

88 1515

1212

11

22

44

55

66

i=6i=6 j=7j=7

1515

11

22

44

55

66

88 1212

i=7i=7

11

22

44

55

66

88 1212 1515

C u trúc d li u - Khoa CNTT 32 ữ ệ ấ

2.2.2 Bubble Sort

 Cài đ t Bubble sort

ặ

void BubbleSort(int a[], int n) {

int i, j; for(i =0; i < n-1; i++) for(j=n-1; j >i; j--)

if (a[j] < a[j-1])

Swap(a[j], a[j-1]);

}

C u trúc d li u - Khoa CNTT 33 ữ ệ ấ

2.2.3 Insertion Sort

 Ý t

ng chính

ưở

- Cho dãy ban đ u a[1], a[2],.., a[n], ta có th xem dãy

ể

ầ

ồ

ộ

ầ ử a[1] đã đ

c s p. ắ

ượ

con g m m t ph n t Sau đó thêm a[2] vào đo n ạ a[1] sao cho a[1] a[2] đ

- Ti p t c thêm a[3] vào đ có a[1] a[2] a[3] đ

ể

ượ

c s p. ắ ượ ế ụ s p.... ắ

ế ạ

- Cho đ n khi thêm xong a[n] vào đo n a[1] a[2]...a[n-1] (cid:222) đ

đo n ạ a[1] a[2]...a[n-1] a[n] ượ

c s p. ắ

C u trúc d li u - Khoa CNTT 34 ữ ệ ấ

2.2.3 Insertion Sort

 Các b

s có đo n a[1] đã đ ạ

c ti n hành ả ử

ượ

c s p ắ

ị

a[pos]

(cid:222)

pos a[i-1] sang ph i m t

ế ướ - B1: i = 2;//gi - B2: x= a[i]; c v trí c n chèn x vào là ầ ượ - B3: D i ch các ph n t ầ ử ừ ỗ

ả

ộ

t v trí đ dành ch cho a[i]. ị

Tìm đ ờ ể

ạ

ượ

c s p. ắ

ỗ - B4: a[pos] = x; // có đo n a[1]...a[i] đ - B5: i = i +1;

n: L p l

i B2

c l ượ ạ

ượ

c s p ắ

ặ ạ i: D ng ừ  Ví d : minh h a ph ọ

N u i ế Ng ụ

ươ

ớ

Dãy đã đ ng pháp chèn v i dãy: 5

(cid:222)

C u trúc d li u - Khoa CNTT 35 ữ ệ ấ

2.2.3 Insertion Sort

1212

88

55

11

66

44 1515

22

i=2i=2

22

55

88

11

66

44 1515

1212

i=3i=3

22 1212

55

11

66

44 1515

88

i=4i=4

C u trúc d li u - Khoa CNTT 36 ữ ệ ấ

2.2.3 Insertion Sort

22

88 1212

11

66

44 1515

55

i=4i=4

Tương tự Tương tự

11

22

44

55

66

88 1212

1515

C u trúc d li u - Khoa CNTT 37 ữ ệ ấ

2.2.3 Insertion Sort

 Cài đ t Insertion sort

ặ

void InsertionSort(int a[], int n) {

// x l u ph n t

a[i]

ầ ử

int pos, i, x; for(i=1; i < n; i++) {

x = a[i]; pos = i-1; while ((pos ≥ 0) && (a[pos] > x)) { // k t h p d i ch các ph n t ầ ử ứ ỗ

ế ợ

ờ

đ ng sau x trong dãy m i ớ

a[pos+1] = a[pos];

pos--; } a[pos+1] = x; // chèn x vào dãy m iớ

}

C u trúc d li u - Khoa CNTT 38 ữ ệ ấ

2.2.4 Interchange Sort

 Ý t

còn l

ngưở - Xu t phát t ấ

ừ ầ

ầ ượ

ầ ử

t tìm nh ng ph n t ữ đang xét. V i m i ph n t ớ

ầ ử

ả ứ ự ớ

c mà ko tho th t

đ u dãy, l n l v i ph n t ầ ử ả ứ ự

i ạ tìm . Th c hi n hoán v đ tho th ả ứ

ỗ ị ể

ự

ệ

i t

ng t

v i các ph n t

ti p theo

ko tho th t đ ượ .ự t - L p l ặ ạ ươ

ự ớ

ầ ử ế

C u trúc d li u - Khoa CNTT 39 ữ ệ ấ

2.2.4 Interchange Sort

ế

c ti n hành ầ

// đ u dãy // duy t qua các ph n t

ầ ử

ệ

 Các b ướ  B1: i = 1;  B2: j = i +1;  B3: while j ≤ n do

if a[j] < a[i] then Swap(a[i], a[j]); j = j +1;

 B4: i = i +1;

if i < n then B2; else (cid:222)

K t thúc!

ế

C u trúc d li u - Khoa CNTT 40 ữ ệ ấ

2.2.4 Interchange Sort

1010

77

66

22

55

44 1616

33

C u trúc d li u - Khoa CNTT 41 ữ ệ ấ

2.2.5 PP ShellSort

 Ý t

ưở

- Thu t toán insertion sort có h n ch là luôn chèn 1 ph n

ng chính ậ

ế

ạ

ầ

t ử

- ShellSort c i ti n b ng cách chia làm nhi u dãy con và

vào đ u dãy! ầ ả ế

ề

ằ

th c hi n pp chèn trên t ng dãy con

ừ

ự

ệ

C u trúc d li u - Khoa CNTT 42 ữ ệ ấ

2.2.5 PP ShellSort

 Xét m t dãy a[1]...a[n], cho m t s nguyên h (1

ộ

n), chia dãy thành h dãy con nh sau:

ộ ố ư

- Dãy con 1: a[1], a[1+h], a[1+2h]... - Dãy con 2: a[2], a[2+h], a[2+2h]... - Dãy con 3: a[3], a[3+h], a[3+2h]...

...

- Dãy con h: a[h], a[2h], a[3h]...

C u trúc d li u - Khoa CNTT 43 ữ ệ ấ

2.2.5 PP ShellSort

 VD: cho dãy n = 8, h = 3 22 77

1010 33

1616

Dãy chính

3

7

2

5

10

6

4

16

Dãy con 1

10

6

4

Dãy con 2

3

2

16

Dãy con 3

7

5

C u trúc d li u - Khoa CNTT 44 ữ ệ ấ

2.2.5 PP ShellSort

 V i m i b

ỗ ướ

ớ

ụ

c h, áp d ng Insertion Sort trên t ng ừ trong

ầ ử

ị

ể

ộ ậ

ầ

ng t

c h div 2... cho

đ i v i b ự ố ớ ướ

ươ

dãy con đ c l p đ làm m n d n các ph n t dãy chính.  Ti p t c làm t ụ đ n h = 1.

ế ế

 Khi h =1 th c hi n Insertion Sort trên 1 dãy duy nh t

ệ

ấ

 K t qu đ

c dãy ph n t

ự là dãy chính ả ượ

ế

ầ ử ượ

c s p. ắ

C u trúc d li u - Khoa CNTT 45 ữ ệ ấ

2.2.5 PP ShellSort

 Các b

ế

c ti n hành chính ướ ọ

ả

- B1: ch n k kho ng cách h[1], h[2],..,h[k], và i = 1; - B2: Chia dãy ban đ u thành các dãy con có b ướ

ầ

c nh y là ả

h[i]. Th c hi n s p x p t ng dãy con b ng Insertion sort.

ế ừ

ự

ệ

ắ

ằ

- B3: i = i+1

N u i > k: ế ượ ạ (cid:222) i: c l Ng

D ngừ B c 2. ướ

(cid:222)

C u trúc d li u - Khoa CNTT 46 ữ ệ ấ

2.2.5 PP ShellSort

 Cho dãy bên d 10

i v i n = 8, h = {5, 3, 1}. ướ ớ 2 7

hh11 = 5 = 5

Dãy 1

55 1010

Dãy 2

44

33

Dãy 3

77 1616

Dãy 4

66

Dãy 5

22

C u trúc d li u - Khoa CNTT 47 ữ ệ ấ

2.2.5 PP ShellSort

77

22 1010

1616

55

66

44

33 hh22 = 3 = 3

Dãy 1

55

44

66

Dãy 2

1616

22

33

Dãy 3

1010

77

44

55

33 1010

66 1616

22

C u trúc d li u - Khoa CNTT 48 ữ ệ ấ

2.2.5 PP ShellSort

hh33 = 1 = 1

Dãy 1

44

77

55

33 1010

66 1616

22

Sắp xếp chèn Sắp xếp chèn

22

44

55

66

77 1010

1616

33

C u trúc d li u - Khoa CNTT 49 ữ ệ ấ

2.2.5 PP ShellSort

void ShellSort(int a[], int n, int h[], int k){ // h[] ch a các b

c nh y

ả

ướ h là k

// s ph n t

ứ ầ ử

ố

int step, i, j; int x, len; for(step = 0; step < k; step++) {

ướ

c nh y ả c nh y ả

ừ ủ

ệ ề ệ

ố ể ợ ị c a[i] trong cùng dãy con

ứ

// duy t qua t ng b // chi u dài c a b ướ // duy t các dãy con cu i đ tìm v trí thích h p trong dãy con ướ

len = h[step]; for(i = len; i < n; i++) { x = a[i]; // l u ph n t ầ ử j = i – len; // a[j] đ ng tr while ((x < a[j]) && (j ≥ 0)) { // pp chèn

// d i v sau theo dãy con ờ ề // qua ph n t

c trong dãy con

a[j+len] = a[j]; j = j – len;

ầ ử ướ

// đ a x vào v trí thích h p trong dãy con

ợ

ị

} a[j+len] = x; // end for i } } // end for step }

C u trúc d li u - Khoa CNTT 50 ữ ệ ấ

2.2.6 PP QuickSort

 Thu t toán do Hoare đ xu t ấ

ề

ậ ố

ộ

ậ

- T c đ trung bình nhanh h n thu t toán khác - Do đó Hoare dùng “quick” đ đ t tên

ơ ể ặ

 Ý t

ưở

- QS phân ho ch dãy ban đ u thành hai ph n d a vào

ng chính ạ

ự

ầ

ị

ộ

a[i] ko l n h n x ớ a[i] ko nh h n x

m t giá tr x  Dãy 1: g m các ph n t ồ  Dãy 2: g m các ph n t ồ

ầ ử ầ ử

ơ ỏ ơ

C u trúc d li u - Khoa CNTT 51 ữ ệ ấ

2.2.6 PP QuickSort

 Sau khi phân ho ch thì dãy ban đ u đ

c phân

ầ

ạ

ượ

thành ba ph n:ầ  a[k] < x, v i k = 1...i  a[k] = x, v i k = i..j  a[k] > x, v i k = j..n

ớ ớ ớ

a[k] < x

a[k] = x

a[k] > x

C u trúc d li u - Khoa CNTT 52 ữ ệ ấ

2.2.6 PP QuickSort

 GT phân ho ch dãy a[left], a[left+1],...,a[right] thành hai dãy

ạ

con:

 B1: Ch n tùy ý m t ph n t

a[k] trong dãy là giá tr m c, left

ầ ử

ộ

ị ố

ọ right,

 B2: Tìm và hoán v c p ph n t

a[i] và a[j] không đúng th t

k £ - Cho x = a[k], i = left, j = right. ầ ử

ị ặ

ứ ự

i++; j--;

đang s p.ắ - B2-1: Trong khi a[i] < x (cid:222) - B2-2: Trong khi a[j] > x (cid:222) - B2-3: N u i < j

ế

Swap(a[i], a[j]) // a[i], a[j] sai th tứ ự

 B3:

(cid:222)

- N u i < j: ế j: (cid:222) - N u i ế

B c 2; ướ D ng.ừ

‡

C u trúc d li u - Khoa CNTT 53 ữ ệ ấ

2.2.6 PP QuickSort

: đ

ế

c ượ

phát bi u theo cách đ quy nh sau:

 GT đ s p x p dãy a[left], a[left+1],...,a[right] ệ

ể ắ ể

 B1: Phân ho ch dãy a[left]...a[right] thành các dãy

ạ

con: - Dãy con 1: a[left]...a[j] < x - Dãy con 2: a[j+1]...a[i-1] = x - Dãy con 3: a[i]...a[right] > x

- N u (left < j)

// dãy con 1 có nhi u h n 1 ph n t

 B2: ế

ầ ử

ề

Phân ho ch dãy a[left]...a[j]

ạ

- N u (i < right)

// dãy con 3 có nhi u h n 1 ph n t

ế

ầ ử

ề

Phân ho ch dãy a[i]...a[right]

ạ

C u trúc d li u - Khoa CNTT 54 ữ ệ ấ

2.2.6 PP QuickSort

void QuickSort(int a[], int left, int right) {

i, j, x;

// ch n ph n t

ầ ử ữ

gi a làm g c ố

ọ

j = right;

int x = a[(left+right)/2]; i = left; do {

// l p đ n khi a[i] >= x

ặ

ế

while (a[i] < x) i++; while (a[j] > x) j--;// l p đ n khi a[i] <= x ặ if ( i <= j) { Swap(a[i], a[j]); i++; j--;

// qua ph n t // qua ph n t

k ti p đ ng tr

ầ ử ế ế ầ ử ứ

c ướ

} } while (i

// ph đo n bên trái ạ

QuickSort(a, left, j);

if (right > i)

// ph đo n bên ph i ả

ạ

QuickSort(a, i, right);

}

C u trúc d li u - Khoa CNTT 55 ữ ệ ấ

2.2.7 PP RadixSort

 Không quan tâm đ n vi c so sánh giá tr các ph n ệ

ế

ầ

ị

tử

 S d ng cách th c phân lo i các con s và th t

ử ụ

ứ ự

ứ

phân lo i các con s này đ t o ra th t ố

ạ

ạ ể ạ

ố ứ ự

 Còn g i là ph

ng pháp phân lô

ọ

ươ

C u trúc d li u - Khoa CNTT 56 ữ ệ ấ

2.2.7 PP RadixSort

493 812 715 710 195 437 582 340 385

S hàng đv

Dãy con

ố

Phân lô hàng đv Phân lô hàng đv

710 340

812 582

493 715 195 385

437 Sau khi phân lô theo hàng đơn vị

710 340 812 582 493 715 195 385 437 C u trúc d li u - Khoa CNTT ấ

57 ữ ệ

2.2.7 PP RadixSort

710 340 812 582 493 715 195 385 437 Dãy con

S hàng ch c

ụ

ố

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

710 812 715

437

340 582 385

Sau khi phân lô theo hàng chục

493 195

710 812 715 437 340 582 385 493 195

C u trúc d li u - Khoa CNTT 58 ữ ệ ấ

2.2.7 PP RadixSort

710 812 715 437 340 582 385 493 195 Dãy con

S hàng ch c

ụ

ố

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

195 340 385

437 493

582 710 715

812 Sau khi phân lô theo hàng trăm

195 340 385 437 493 582 710 715 812

C u trúc d li u - Khoa CNTT 59 ữ ệ ấ

2.2.7 PP RadixSort

ệ

a[i] trong dãy a[1]...a[n] là m t s ộ ố

ữ ố

 L n l

 GT RadixSort th c hi n nh sau: ự  Xem m i ph n t ầ ử ỗ i đa m ch s ố ạ

nguyên có t ầ ượ

ị

danh

ạ

hàng ch c, hàng trăm... - T i m i b ạ

t phân lo i các ch s theo hàng đ n v , ữ ố ụ ỗ ướ

ừ

sách đã phân lo i theo th t

- Sau khi phân lo i xong

ẽ

ấ

ạ ạ c danh sách các ph n t

c phân lo i ta s n i các dãy con t ẽ ố ứ ự ﬁ 0 hàng th m cao nh t ta s thu ở ầ ử ượ

9. ứ c s p. ắ

ượ

C u trúc d li u - Khoa CNTT 60 ữ ệ ấ

2.2.7 PP RadixSort

 B1: k = 0; // k th hi n ch s phân lo i, k =0 hàng đ n v , k=1

ể ệ

ữ ố

ạ

ị

hàng ch c...ụ

phân lo i B[0]...B[9]

ạ

 B2: ứ  Kh i t o B[0]...B[9] r ng, B[i] s ch a các ph n t

có ch s th k

// T o các dãy ch a ph n t ầ ử ẽ

ầ ử

ở ạ

ứ

ỗ

ữ ố ứ

là i.  B3:

- N i B[0], B[1],..., B[9] l

For i=1 to n do Đ t a[i] vào dãy B[j] v i j là ch s th k c a a[i]. ữ ố ứ

 B4:

i theo đúng trình t ủ thành a. ặ ố ớ ạ ự

(cid:222) // m là s l ng ch s t ố ượ ữ ố ố i đa c a các s ủ ố

k = k +1 - N u k < m: ế ượ ạ (cid:222) c l i: - Ng B c 2. ướ D ng.ừ

C u trúc d li u - Khoa CNTT 61 ữ ệ ấ

2.2.7 PP RadixSort

ể ấ

hàng đ n v ị phân lô

ề

ứ c c a t ng m ng B[i]

ướ ủ ừ

ả

void RadixSort(long a[], int n){ int i, j, d, digit, num; // bi n đ l y các con s , b t đ u t int h = 10; ế ố ắ ầ ừ // m ng hai chi u ch a các ph n t long B[10][MAX]; ầ ử ả int Len[10]; // kích th for(d = 0; d < MAXDIGIT; d++) {

for( i = 0; i < 10; i++) // kh i t o kích th

c các dãy B[i] là 0

ở ạ

ướ

Len[i] = 0;

for(i = 0; i < n; i++) { // duy t qua t

c a m ng

ệ

ấ ả

ả

t c các ph n t ầ ử ủ // l y con s theo hàng h ố ấ

digit = (a[i] % h) / (h / 10); B[digit][Len[digit]++] = a[i];