Chương 2 TÌM KIẾM & SẮP XẾP

ươ TÌM KI M & S P X P

2 ng Ắ

Ch Ế

Ế

2.1. Các gi

ậ

ả

ế

i thu t tìm ki m 2.1.1. Bài toán tìm ki mế i thu t tìm ki m tuy n tính 2.1.2. Gi ế i thu t Tìm ki m nh phân 2.1.3. Gi ế

ế ị

ậ ậ

2.2. Các gi

ả

ế

ọ

ả ả i thu t s p x p ậ ắ 2.2.1. Bài toán s p x p 3.2.1 Gi 3.2.2 Gi 3.2.3 Gi 3.2.4 Gi 3.2.5 Gi

i thu t đ i ch tr c ti p –Interchange Sort ổ ự ế i thu t ch n tr c ti p-Selection Sort ự ế i thu t chèn tr c ti p-Insert Sort ế ự i thu t n i b t – Bubble Sort i thu t nhanh – Quick Sort

ế ắ ậ ổ ậ ậ ậ ổ ọ ậ

ả ả ả ả ả

2.3. Bài t pậ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

2.1 Các Gi

i Thu t Tìm Ki m

ả

ế

ậ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

2.1.1. Bài toán tìm ki mế i thu t tìm ki m tuy n tính 2.1.2. Gi ế i thu t Tìm ki m nh phân 2.1.3. Gi ế ậ ậ ả ả ế ị

2.1.1 Bài Toán Tìm Ki mế

, khi thao tác, khai thác d li u h u nh ư ữ ệ ầ

lúc nào cũng ph i th c hi n thao tác tìm ki m. Trong th c t ự ế ả ự ệ ế

ể ệ ấ

ế ho c tìm th y. ả ủ ấ

K t qu c a vi c tìm ki m có th là không tìm th y ế ặ N u k t qu là tìm th y thì nhi u khi còn ph i xác ế ả

đâu? ế đ nh xem v trí c a ph n t ị ả ủ ầ ử ị ề ấ tìm th y là ở ấ

Vi c tìm ki m nhanh hay ch m tùy thu c vào tr ng ệ ậ ạ ộ

thái và tr t t c a d li u trên đó. ữ ệ ế ậ ự ủ

Có 2 thu t toán chính: Tìm ki m tuy n tính & Tìm ế ế ậ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

ki m nh phân ế ị

s chúng ta có m t m ng M g m N ph n t . ầ ử ả ộ ả ử ồ

có giá tr b ng ấ ầ ử ị ằ

có giá tr b ng X là ph n t ị ằ ử ế ầ ầ ử th ứ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

 Gi  V n đ đ t ra là có hay không ph n t ề ặ X trong m ng M? ả  N u có thì ph n t m y trong m ng M? ấ ả

2.1.2. Gi

ả

i Thu t Tìm Ki m Tuy n Tính ế

ế

ậ

ng: ưở

ủ ứ ấ

ầ ử ứ c ph n t ượ ớ ặ ầ

 Ý T th nh t, th hai…c a Ti n hành so sánh x v i ph n t ế có khóa c n tìm, m ng A cho đ n khi g p đ ầ ử ế ả ho c đã tìm h t m ng mà không th y x. ấ ả ế ặ

ể ậ

Ư ể Thu t toán này có th cho ta th c hi n tìm ki m khi các ph n t ệ ự c s p x p. ượ trong m ng ch a đ ả u đi m: ế ầ ử ư ế ắ

ượ c đi m: ể S m t r t nhi u th i gian n u nh ư ấ ấ ế ề ờ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Nh không có ph n t chúng ta c n tìm. ẽ ầ ử ầ

VD:Tìm x = 14

Tìm th y ấ i v trí th t ứ ạ ị

Ch a ư h t ế m ngả

 Minh H aọ

14

5 12 3

0 10 2

7 1 14 9 14

ế

VD:Tìm x = 30

H t m ng ả Ch a ư h t ế không tìm m ngả th yấ

30

5 12 3

7 1 14 9

0 10 2

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

 Gi i thu t: ả ậ

: B c 1 ướ

i = 1; // B t đ u t ph n t đ u tiên c a dãy ắ ầ ừ ầ ử ầ ủ

: So sánh a[i] v i x, có 2 kh năng. B c 2 ướ ả ớ

ấ

• a[i] = x ; // Tìm th y.D ng ừ • a[i] != x ; // Th c hi n b c 3. ướ ự ệ

: B c 3 ướ

k ti p trong m ng. ả

• i = i+1; // xét ph n t ầ ử ế ế • N u i > N // H t m ng.Không tìm th y.D ng ừ ế ế ấ ả

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Ng i: L p l i b c 2. c l ượ ạ ặ ạ ướ

 Cài Đ tặ

Int Timtuyentinh (int a[] , int N , int x) {

int i = 0; while((i < N) && (a[i] != x)) i++; if( i == N)

return -1 ; // tìm h t m ng nh ng không có x ế ả ư

else

return i ; //a[i] là ph n t có khóa x. ầ ử

}

ả i thu t ậ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Đ ph c t p tính toán c p n: T(n)=O(n)  Đánh giá gi ộ ứ ậ ấ

2.1.3 Gi

i Thu t Tìm Ki m Nh Phân

ả

ế

ậ

ị

 Ý T ng: ưở

ầ ủ ầ ử ầ

ố ế ế

đ ng ị ị ở ữ ầ ầ ử ớ đ u tiên c a dãy cu i cùng c a dãy (Last = N). ủ gi a ầ ử ứ

ế ạ

ủ ầ

ế ạ ắ

ủ

ặ ạ

ế ặ ạ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

- L n tìm ki m ban đ u là ph n t (First = 1) đ n ph n t - So sánh giá tr X v i giá tr ph n t c a dãy M là M[Mid]. ủ - N u X = M[Mid]: Tìm th y ế ấ - N u X < M[Mid]: Rút ng n ph m vi tìm ki m ắ ế v n a đ u c a dãy M (Last = Mid–1) ề ử - N u X > M[Mid]: Rút ng n ph m vi tìm ki m ế v n a sau c a dãy M (First = Mid+1) ề ử i quá trình này cho đ n khi tìm th y ph n t - L p l ầ ử ấ ế có giá tr X ho c ph m vi tìm ki m không còn n a ữ ị (First > Last).

ẽ ậ ắ ị

Ư ể Thu t toán tìm nh phân s rút ng n đáng u đi m: k th i gian tìm ki m. ể ờ ế

c đi m: ượ ể Ch th c hi n đ ỉ ự ệ ượ c trên dãy đã có th ứ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Nh .ự t

Minh H aọ

Mid = 5 M[mid]= 46

Tìm giá tr X = 85 (Tìm th y) ấ ị

85

90 1 7

12 12

23 23

34 34

46 46

59 59

69 69

77 77

X > M[mid]

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Minh H aọ

Mid = 8 M[mid] = 77

Tìm giá tr X = 85 (Tìm th y) ấ ị

7

12

23

34

46

85

90 59 59

69 69

77 77

X > M[mid]

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Minh H aọ

Mid = 9 M[mid] = 85

Tìm giá tr X = 85 (Tìm th y) ấ ị

7

12

23

34

46

59

69

77

85

90 Đã tìm th y t i ấ ạ v trí 9 ị

X = M[mid]

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

có khóa nh sau (N = 10). s dãy M g m 10 ph n t ồ ầ ử ư

Minh H aọ Gi ả ử 2 3 4 5 8 15 17 22 25 30

First Last

Mid M[Mid]

First>L ast

X= M[Mid]

X< M[Mid]

X> M[Mid]

L n ầ l pặ

False

True

False

B.đ uầ

False

True

False

True

False

True

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Tìm ki m ph n t có giá tr X = 5 (tìm th y): ầ ử ế ấ ị

 Minh H aọ ả ử s dãy M g m 10 ph n t ồ có khóa nh sau (N=10). ư ầ ử

Gi 1 3 4 5 8 15 17 22 25 30

First Last

Mid M[Mid]

First> Last

X= M[Mid]

X< M[Mid]

X> M[Mid]

L n ầ l pặ

False

True

False

B.đ uầ

False

True

False

True

False

True

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Tìm ki m ph n t có giá tr X = 7 (không tìm th y) ầ ử ế ấ ị

B1: First = 1 B2: Last = N B3: IF (First > Last)

B3.1: Không tìm th yấ B3.2: Th c hi n Bkt ự

ệ

B4: Mid = (First + Last)/ 2 B5: IF (X = M[Mid])

i v trí Mid

ệ

B5.1: Tìm th y t ấ ạ ị B5.2: Th c hi n Bkt ự B6: IF (X < M[Mid])

i B3

B6.1: Last = Mid – 1 B6.2: L p l ặ ạ B7: IF (X > M[Mid])

i B3

B7.1: First = Mid + 1 B7.2: L p l ặ ạ

Bkt: K t thúc ế

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

 Gi i thu t: ả ậ

int Timnhiphan(int M[ ], int N, int X){

int First = 1; int Last = N; while (First <= Last){

int Mid = (First + Last)/2; if (X == M[Mid])

return Mid;

if (X < M[Mid])

Last = Mid – 1;

else

First = Mid + 1;

}

return -1;

 Cài Đ tặ

ả i thu t ậ

}  Đánh giá gi ộ

2n)

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Đ ph c t p tính toán c p n: T(n)=O(Log ứ ậ ấ

2.2 Các gi

ả

i thu t s p x p ậ ắ

ế

ọ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

2.2.1. Bài toán s p x p 2.2.2. Gi 2.2.3. Gi 2.2.4. Gi 2.2.5. Gi 2.2.6. Gi i thu t đ i ch tr c ti p –Interchange Sort ổ ự ế i thu t ch n tr c ti p-Selection Sort ự ế i thu t chèn tr c ti p-Insert Sort ế ự i thu t n i b t – Bubble Sort i thu t nhanh – Quick Sort ắ ậ ổ ậ ậ ậ ổ ọ ậ ả ả ả ả ả

2.2.1. Bài Toán S p X p

ế

ắ

ả ậ ệ ờ

ệ ế

ữ ệ ặ

 Đ thu n ti n và gi m thi u th i gian thao tác mà ể ể t là đ tìm ki m. Do v y s p x p d li u là m t đ c bi ộ ế ắ ậ ể ặ trong nh ng thao tác c n thi ng g p trong quá t và th ườ ế ữ trình l u tr , qu n lý d li u. ầ ữ ệ ữ ư ả

ế ử

ầ ử ộ tăng ho c gi m d a trên ả ự ặ ộ

 S p x p là quá trình x lý m t danh sách các ph n t ắ đ đ t chúng theo m t th t ứ ự ể ặ n i dung l u tr trên m i ph n t ữ ộ . ầ ử ư ỗ

ề ế ắ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

 Có r t nhi u thu t toán s p x p song chúng ta ch ỉ ậ ấ i thu t s p x p th quan tâm đ n 5 gi ng s d ng. ử ụ ậ ắ ườ ế ế ả

. . . . . . . . . .

an-1

Khái ni m v ngh ch th : ế ề ệ ị

ả ử ả tăng d n, n u ầ ế iaj

Gi s m ng có th t ngh ch th thì g i là ị ọ ứ ự ế

ụ ế ằ ử ắ ị

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

M c tiêu c a s p x p là kh các ngh ch th (b ng ủ ế cách hoán v các ph n t ) ầ ử ị

i Thu t Đ i Ch Tr c Ti p-Interchange

ả

ậ ổ

ổ ự

ế

2.2.2. Gi Sort

 Ý t ng: ưở

đ u dãy, tìm t t c ngh ch th ch a ừ ầ ấ ứ ế ả ị

này.  Xu t phát t ấ ph n t ầ ử

 Tri t tiêu chúng b ng cách đ i ch ph n t ằ ổ ỗ này v i ớ

t ệ ph n t ầ ử ươ ầ ử ng ng trong c p ngh ch th . ế ặ ứ ị

ti p theo trong ạ ử i x lý trên v i các ph n t ớ ầ ử ế

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

 L p l ặ dãy.

 Minh H aọ

2

8

5

1

6

4

12

2

8

5

1

6

4

12

i=1

i=2 j=2

i=3 j=3

i=4 j=4

i=5 j=5

i=6 j=6

i=7 j=7

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ng ĐH KTKT B.D ng

ườ

ươ

 Gi i thu t: ả ậ

B c ướ 1 :

i = 1; // b t đ u t đ u dãy ắ ầ ừ ầ

B c 2 : ướ

a[j] < a[i], j>i ầ ử

B c 3 ướ

ự ệ

j = i+1;//tìm các ph n t : Trong khi j < N th c hi n N u a[j]

j = j+1; B c 4 : ướ

i B c 2.

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

i = i+1; N u i < n: L p l ế Ng ặ ạ ướ i: D ng. ừ c l ượ ạ

 Cài Đ tặ

void InterchangeSort(int a[], int N ) int i, j,tam; { for (i = 0 ; i

for (j =i+1; j < N ; j++)

if(a[j ]< a[i])

{ tam=a[i]; a[i]=a[j]; a[j]=tam; }

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

}

 Đánh giá gi i thu t: ả ậ

i thu t đ i ch tr c ti p, s l ả ỗ ự

ậ ổ ả ố ượ ộ ế ụ

ủ ạ ầ

ố ng phép hoán v th c hi n tùy thu c ị ự ệ ộ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

 Ð i v i gi ng các ố ớ phép so sánh x y ra không ph thu c vào tình tr ng c a dãy s ban đ u  Nh ng s l ố ượ ư vào k t q a so sánh ế ủ

ự

ọ

ế

ậ

i Thu t Ch n Tr c Ti p –Selection Sort 2.2.3 Gi ả  Ý T ng: ưở

 Đ u tiên dãy có N ph n t ầ ử ầ ử nh ỏ

, ta ch n ph n t ọ đ u tiên. nh t trong dãy đ i ch cho ph n t ổ ầ ử ầ ầ ấ

ổ  Ti p theo, tìm ph n t ấ ủ

ế còn l i trong dãy đ i ch cho ph n t nh nh t c a dãy n-1 ph n ầ ử th 2 c a ổ ầ ử ứ ỏ ổ ầ ủ ạ

t ử dãy.

ự ả

còn 1 ph n t  Quá trình trên th c hiên đ n khi nào trong m ng ch ỉ ế i. ạ thi d ng l ừ ầ ử

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

 K t qu đ ả ượ ế c m ng đã s p x p tăng. ắ ế ả

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

Min

16 11 45 28 73 61 7 23

I=1

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

16 11 45 28 73 61 7 23

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

Min

16 11 45 28 73 61 7 23

I=2

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

7 11 45 28 73 61 16 23

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

Min

16 11 45 28 73 61 7 23

I=3

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

7 11 45 28 73 61 16 23

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

Min

16 11 45 28 73 61 7 23

I=4

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

7 11 16 28 73 61 45 23

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

16 11 45 28 73 61 7 23

Min

I=5

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

7 11 16 23 73 61 45 28

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

Min

16 11 45 28 73 61 7 23

I=6

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

73 7 11 16 23 28 61 45

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

Min

16 11 45 28 73 61 7 23

I=7

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

73 7 11 16 23 28 45 61

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

K t thúc vì m ng ả ch còn 1 ph n t ầ ử

ế ỉ

16 11 45 28 73 61 7 23

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

73 7 11 16 23 28 45 61

Ban đ uầ

L n 1ầ

16 11 45 28 73 61 7 23

L n 2ầ

7 11 45 28 73 61 16 23

L n 3ầ

7 11 16 28 73 61 45 23

L n 4ầ

7 11 16 23 73 61 45 28

L n 5ầ

7 11 16 23 28 61 45 73

L n 6ầ

L n 7ầ

7 11 16 23 28 45 61 73

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

7 11 16 23 28 45 61 73

 Gi i thu t: ả ậ

B c 1: ướ

I = 1

B c 2: ướ

ấ ỏ

Tìm ph n t hành t nh nh t a[min] trong dãy ầ ử a[i] đ n a[n] ế ừ

Đ i ch cho a[min] và a[i] ổ

hi n ệ B c 3 : ướ ổ B c 4 : ướ

i b c 2

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

I = I + 1 N u I < N thì l p l ế Ng i thì d ng. c l ượ ạ ậ ạ ướ ừ

Cài Đ tặ

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

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

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

a[min] =a[j];

tam=a[i]; a[i]=a[min]; a[min]=tam ; }

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

}

 Đánh giá gi i thu t: ả ậ

ậ ự ể ấ ằ

ầ

ả t th i, bao gi ử ầ ị ờ nh nh t hi n hành. S l ệ ấ ỏ

ố ượ ạ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Ð i v i gi i thu t ch n tr c ti p, có th th y r ng ố ớ ế ọ l cũng c n (n-i) l n so sánh đ ở ượ ứ ể ầ ng xác đ nh ph n t phép so sánh này không ph thu c vào tình tr ng c a dãy s ban đ u, do vây k t lu n: ầ ủ ụ ế ộ ậ ố

i Thu t Chèn Tr c Ti p –Insert Sort

ự

ế

ậ

ả ng:

2.2.4. Gi  Ý T ưở

ể c s p x p, có đo n g m 1 ph n t ồ ượ ế ắ ạ  Cho dãy ban đ u ầ a1, a2, …, an, ta có th xem nh đã ầ ử a1 đã đ

ẽ c ượ  Sau đó thêm a2 vào đo n ạ a1 s có đo n ạ a1 a2 đ

s p x p. ắ ế

ể a3 vào đo n ạ a1 a2 đ có đo n ạ a1 a2 a3

 Ti p t c thêm c s p x p. đ ế ụ ắ ượ ế

an vào đo n ạ a1 a2 …

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

c s p x p ế ụ ẽ ượ ế  Ti p t c cho đ n thêm khi xong ế a1 a2 ..an đ ắ an-1 s có dãy

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

13

7

9

4

11

3

17

15

13

7

9

4

11

3

17

15 1 2 3 4 5 6 7 8

i=2

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

13

7

9

4

11

3

17

15

7

13

9

4

11

3

17

15 1 2 3 4 5 6 7 8

i=3

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

13

7

9

4

11

3

17

15

7

9

13

4

11

3

17

15 1 2 3 4 5 6 7 8

i=4

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

13

7

9

4

11

3

17

15

4

7

9

13

11

3

17

15 1 2 3 4 5 6 7 8

i=5

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

13

7

9

4

11

3

17

15

4

7

9

11

13

3

17

15 1 2 3 4 5 6 7 8

i=6

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

13

7

9

4

11

3

17

15

3

4

7

9

11

13

17

15 1 2 3 4 5 6 7 8

i=7

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

9

L n 7ầ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

 Gi i thu t: ả ậ

B c 1:

ướ

c s p x p

ắ

ế

ượ

pos thích h p trong đo n a[1] đ n a[i-1]

ế

ạ

ợ

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

ả

ộ

ế

ử ỗ

i=2; // a[1] đã đ B c 2: ướ x=a[i]; Tìm v trí ị đ chèn a[i] vào ể B c 3: ướ D i ch ph n t ầ ỗ ờ v trí đ dành ch cho a[i] ể ị B c 4: ướ a[pos]=x //đo n a[1] đ n a[i] đã đ

ế

ạ

ượ

c s p ắ

B c 5:

ướ

i b

c 2

i=i+1; N u i

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Cài Đ tặ

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

int pos, x; for(int i=1 ; i

ị

x=a[i]; pos=i-1; // tìm v trí chèn x while((pos >=0 )&&(a[pos]>=x) {

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

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

}

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

 Đánh giá gi i thu t: ả ậ

ả ặ

ợ ị

ầ ỗ ợ

 Các phép so sánh x y ra trong vòng l p while tìm v trí thích h p pos, và m i l n xác đ nh v trí đang ị ỗ ầ ị xét không thích h p, s d i ch ph n t a[pos] ử ẽ ờ t ươ ng ng. ứ

ệ ấ ả ặ

ờ

ủ ố

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

ỗ ầ ng h p sau: ạ ng trong t ng tr  Gi i thu t th c hi n t t c n – 1 vòng l p while, ự ậ ả ng phép so sánh và d i ch này ph do s l ụ ố ượ thu c vào tình tr ng c a dãy s ban đ u, nên ch ộ ỉ c l có ướ ượ ườ ừ ợ

2.2.5. Gi i Thu t N i B t –Bubble Sort ả ổ ọ ậ

 Ý T

ừ cu i dãy ,đ i ch các c p ph n t ổ ặ

ngưở :  Xu t phát t ấ ể ư k ầ ử ế đó v v trí đ ng đ u dãy hi n ệ ố ầ ử ổ ề ị ứ ầ

c n đ đ a ph n t ậ hành

ế ế

b ở ướ ị ứ ẽ ầ ph n ầ

ử ế . c s p x p i x lý trên cho đ n khi k hông còn ph n t  Sau đó s không xét đ n nó  Do v y đ ử ượ  L p l ặ ế ầ ử

Khoa KTCN Tr

11

3

7

5

11

5

9

3

7

5

11

7

2

9

3

7

11

9

15

2

9

11

1

15

Ban đ uầ

B c 1 ướ

B c 2 ướ

B c 3 ướ

B c 4 ướ

B c 5 ướ

B c 6 ướ

B c 7 ướ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

 Gi i thu t: ả ậ

B c 1: ướ

B c 2 ướ

i=1; : j=N; Trong khi (j>i) th c hi n: ự ệ

ị

N u a[j]

B c 3: ướ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

i=i+1; N u i>N-1: H t dãy, d ng ừ ế ế i B c 2 i: L p l Ng ặ ạ ướ c l ượ ạ

Cài Đ tặ

void bubblesort(t M[],int N) {

for ( int i=0 ; i

for(int j=N-1 ; j>i ; j--) if(M[j]

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

}

 Đánh giá gi i thu t: ả ậ

ậ ả ố ượ

i thu t n i b t, s l ổ ọ ụ ủ ộ

 Ð i v i gi ng các phép so ố ớ sánh x y ra không ph thu c vào tình tr ng c a ạ ả dãy s ban đ u ầ

ng phép hoán v th c hi n tùy thu c ị ự ệ ộ ố ượ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

ố  Nh ng s l ư vào k t q a so sánh ế ủ

2.2.6.Gi i Thu t S p X p Nhanh – Quick Sort ả ế ậ ắ

 Ý T ng: ưở

ạ

 Phân ho ch dãy M thành 2 dãy con th a mãn đi u ề nh h n ỏ ơ ứ ử ầ

ki n: ệ các ph n t ỏ “1/2 Dãy bên trái ch a các ph n t c a 1/2 Dãy bên ph i” ầ ử ủ ả

 N u dãy con có nhi u h n 1 ph n t ầ ử thì th c hi n ự ệ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

ơ ế s p x p dãy con (Đ qui). ắ ề ệ ế

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

i=1; j=8

L

R

X=3

10

5

7

3

9

2

15

1

i

j

L=1 R=8

Đo n 1ạ

Đo n 2ạ

L=1 R=3

ng ĐH KTKT B.D ng

L=4 R=8 Khoa KTCN Tr

ườ

ươ

Đo n ạ c n s p ắ ầ x pế ươ

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

i=4; j=8

L

R

X=5

1

2

3

9

5

15

10

7

i

j

L=4 R=8

Đo n 2ạ

Đo n 1ạ

L=1 R=3

L=4 R=5

L=5 R=8

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Đo n ạ c n s p ắ ầ x pế ươ

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

i=5; j=8

L

R

X=7

1

2

3

5

7

15

10

9 L=5 R=8

i

j

L=4 R=5

Đo n 2ạ

L=1 R=3

L=6 R=8

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Đo n ạ c n s p ắ ầ x pế ươ

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

i=6; j=8

R

L

X=15

1

2

3

5

7

15

10

9 L=6 R=8

i

j

L=4 R=5

Đo n 1ạ

L=1 R=3

L=6 R=7

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Đo n ạ c n s p ắ ầ x pế ươ

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

i=6; j=7

X=15

L

R

1

2

3

5

7

10

15

9 L=6 R=7

i

j

L=4 R=5

L=1 R=3

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Đo n ạ c n s p ắ ầ x pế ươ

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

i=4; j=5

X=5

L

R

1

2

3

9

10

15

5

7

i

j

L=4 R=5

L=1 R=3

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Đo n ạ c n s p ắ ầ x pế ươ

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

i=1; j=3

X=2

L

R

2

1

3

5

7

9

10

15

i

j

L=1 R=3

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Đo n ạ c n s p ắ ầ x pế ươ

 Minh H aọ

Cho dãy có 8 ph n t S p x p theo vi trí tăng d n ầ ử ắ ế ầ

1

2

3

5

7

9

10

15 Không còn đo n nào c n ầ ạ s p x p

ế

ắ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Đo n ạ c n s p ắ ầ x pế ươ

10

5

7

15

1

2

3

9 Đo n [1- ạ 8]

5

7

9

15

10 Đo n [4- ạ 8]

7

9

15

10 Đo n [5- ạ 8]

9

10

15 Đo n [6- ạ 8]

9

10 Đo n [6- ạ 7]

5

7 Đo n [4- ạ 5]

1

2

3 Đo n [1- ạ 3]

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

 Gi i thu t: ả ậ

B c 1: ướ

B c 2 ướ

i=1; : j=N; Trong khi (j>i) th c hi n: ự ệ

ị

N u a[j]

B c 3: ướ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

i=i+1; N u i>N-1: H t dãy, d ng ừ ế ế i B c 2 i: L p l Ng ặ ạ ướ c l ượ ạ

Cài Đ tặ

void QuickSort(int M[], int First, int Last) {

j = Last;

i++; j--;

int i, j, tam, x; x = M[(First+Last)/2]; i = First; do { while (M[i] X) if (i <= j) {

tam=M[i]; M[i]=M[j]; M[j]=tam; i++;

j--;

} }while (i<= i); QuickSort(M, First, j); QuickSort (M, i, Last);

}

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

i thu t: ả

 Đánh giá gi + Tr tăng: ườ t nh t, khi m ng M có th t ả ứ ự ấ

ị

ng h p x u nh t, khi ph n t X đ c ch n ậ ng h p t ợ ố ố ố ố ợ ượ ườ ọ

ấ gi a dãy con là giá tr l n nh t: S phép gán: Gmin = N-1 S phép so sánh: Smin = N×Log2(N)/2 S phép hoán v : Hmin = 0 ầ ử ấ ị ớ ấ

S phép gán: Gmax = N×(N-1)/2 S phép so sánh: Smax = (N-1)×(N-1) S phép hoán v : Hmax = N×(N-1)/2 + Tr ở ữ ố ố ố ị

+ Trung bình:

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

S phép gán: Gavg = (N-1)×(N+2)/4 S phép so sánh: Savg = N×[Log2(N)+2N–2]/4 S phép hoán v : Havg = N×(N-1)/4 ố ố ố ị

Chi phí trung bình O(n*log2n) Chi phí cho tr ng h p x u nh t O(n ấ ườ ấ

tr c: ợ Chi phí này ph thu c vào cách ch n ph n t ộ ụ ọ ầ ử ụ

c ph n t có giá tr trung bình ta ọ ế ị

- N u ch n đ ượ s chia thành 2 dãy b ng nhau ẽ ầ ử ằ

- N u ch n nh m ph n t nh nh t (hay l n ầ ử ế ằ ọ ấ ớ ỏ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

nh t) ấ  O(n2)

2.3 Bài T p ậ

1. Trình bày t ng và minh h a gi i thu t tìm ki m t ư ưở ọ ả ế ậ

tuy n tính, tìm ki m nh phân ế ế ị

2. Cài đ t thu t toán tìm tuy n tính b ng cách: ế ậ ặ ằ

- S d ng vòng l p for ử ụ ặ

- S d ng vòng l p while ử ụ ặ

3. Trong tr ng h p các ph n t c a dãy đã có th t ườ ầ ử ủ ứ ự ợ

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

tăng (ho c gi m) hãy cài đ t l i thu t toán tìm nh phân ặ ạ ả ặ ậ ị

1. Trình bày t ng và minh h a 5 gi t ư ưở ọ ả i thu t s p x p ậ ắ ế

2. Cài đ t 5 gi ặ ả i thu t s p x p theo các tr ế ậ ắ ườ ng h p và ợ

đi n k t qu s l n th c hi n các phép toán vào b ng ệ ả ố ầ ự ề ế ả

Khoa KTCN Tr

ng ĐH KTKT B.D ng

ườ

ươ

Chương 2 TÌM KIẾM & SẮP XẾP

Đây là bước các SEOer quan tâm nhiều nhất. Sau khi website của bạn đã được index trong data center của Google. Nó sẽ được đánh giá và xếp hạng để hiển thị ra ngoài trang kết quả tìm kiếm (SERP) thông qua thuật toán của

ươ TÌM KI M & S P X P

2 ng Ắ

Ch Ế

Ế

2.1. Các gi

ậ

ả

ế

i thu t tìm ki m 2.1.1. Bài toán tìm ki mế i thu t tìm ki m tuy n tính 2.1.2. Gi ế i thu t Tìm ki m nh phân 2.1.3. Gi ế

2.2. Các gi

ả

ả ả i thu t s p x p ậ ắ 2.2.1. Bài toán s p x p 3.2.1 Gi 3.2.2 Gi 3.2.3 Gi 3.2.4 Gi 3.2.5 Gi

ế ắ ậ ổ ậ ậ ậ ổ ọ ậ

2.3. Bài t pậ

2.1 Các Gi

i Thu t Tìm Ki m

ả

ế

ậ

2.1.1 Bài Toán Tìm Ki mế

2.1.2. Gi

ả

i Thu t Tìm Ki m Tuy n Tính ế

ế

ậ

14

5

12 3

0 10 2

7

1 14 9 14

30

5

12 3

7

1 14 9

0 10 2

2.1.3 Gi

i Thu t Tìm Ki m Nh Phân

ả

ế

ậ

ị

85

90

1 7

12 12

23 23

34 34

46 46

59 59

69 69

77 77

7

12

23

34

46

85

90

59 59

69 69

77 77

7

12

23

34

46

59

69

77

85

90

Đã tìm th y t i ấ ạ v trí 9 ị

2.2 Các gi

ả

i thu t s p x p ậ ắ

ế