Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 2: Tìm kiếm và sắp xếp

Chương 2 TÌM KiẾM & SẮP XẾ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 2.1.3. Giải thuật Tìm kiếm nhị phân

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ải thuật ñổi chổ trực tiếp –Interchange Sort 3.2.2 Giải thuật chọn trực tiếp-Selection Sort 3.2.3 Giải thuật chèn trực tiếp-Insert Sort 3.2.4 Giải thuật nổi bọt – Bubble Sort 3.2.5 Giải thuật nhanh – Quick Sort

2.3. Bài tập

Khoa CNTT Trường Cð CNTT TP.HCM

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 2.1.3. Giải thuật Tìm kiếm nhị phân

Khoa CNTT Trường Cð CNTT TP.HCM

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

(cid:1) Trong thực tế, 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. (cid:1) Kết quả của việc tìm kiếm có thể là không tìm thấy hoặc tìm thấy. (cid:1) Nếu kết quả là tìm thấy thì nhiều khi còn phải xác ñịnh xem vị trí của phần tử tìm thấy là ở ñâu? (cid:1) 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 ñó. (cid:1) Có 2 thuật toán chính: Tìm kiếm tuyến tính & Tìm kiếm nhị phân

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:1) Giả sử chúng ta có một mảng M gồm N phần tử. (cid:1) Vấn ñề ñặt ra là có hay không phần tử có giá trị bằng X trong mảng M? (cid:1) Nếu có thì phần tử có giá trị bằng X là phần tử thứ mấy trong mảng M?

Khoa CNTT Trường Cð CNTT TP.HCM

2.1.2. Giải Thuật Tìm Kiếm Tuyến Tính

(cid:2) Ý Tưởng: Tiến hành so sánh x với phần tử thứ nhất, thứ hai…của mảng A cho ñến khi gặp ñược phần tử có khóa cần tìm, hoặc ñã tìm hết mảng mà không thấy x.

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

Nhược ñiểm: Sẽ mất rất nhiều thời gian nếu như không có phần tử chúng ta cần tìm.

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2) Minh Họa

VD:Tìm x = 14

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

Chưa hết mảng

14

5 12 3

14 1 14 9

0 10 2

7

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 CNTT Trường Cð CNTT TP.HCM

(cid:2) Giải thuật:

Bước 1 :

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

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

• a[i] = x ; // Tìm thấy.Dừng

• a[i] != x ; // Thực hiện bước 3.

Bước 3 :

• i = i+1; // xét phần tử kế tiếp trong mảng.

• Nếu i > N // Hết mảng.Không tìm thấy.Dừng

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

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2) 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.

}

(cid:2) ðánh giá giải thuật

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

Khoa CNTT Trường Cð CNTT TP.HCM

2.1.3 Giải Thuật Tìm Kiếm Nhị Phân

(cid:2) Ý Tưởng:

- Lần tìm kiếm ban ñầu là phần tử ñầu tiên của dãy (First = 1) ñến phần tử cuối cùng của dãy (Last = N). - So sánh giá trị X với giá trị phần tử ñứng ở giữa 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) - Lặp lại quá trình này cho ñến khi tìm thấy phần tử có giá trị X hoặc phạm vi tìm kiếm không còn nữa (First > Last).

Khoa CNTT Trường Cð CNTT TP.HCM

85

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

X = M[mid]

Khoa CNTT Trường Cð CNTT TP.HCM

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

2 3 4 5 8 15 17 22 25 30

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

First Last Mid M[Mid] Lần lặp First>L ast X= M[Mid] X< M[Mid] X> M[Mid]

B.ñầu False 5 1 10 True False False 8

1 False 2 1 4 False False True 3

2 False 3 3 4 False False True 4

Khoa CNTT Trường Cð CNTT TP.HCM

3 False 4 4 4 True 5

(cid:2) Minh Họa

Giả sử dãy M gồm 10 phần tử có khóa như sau (N=10). 1 3 4 5 8 15 17 22 25 30

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

First Last Mid M[Mid] Lần lặp First> Last X= M[Mid] X< M[Mid] X> M[Mid]

B.ñầu False 1 10 False True False 5 8

1 False 1 4 False False True 2 3

2 False 3 4 False False True 3 4

3 False 4 4 False False True 4 5

Khoa CNTT Trường Cð CNTT TP.HCM

4 True 5 4

(cid:2) Giải thuật:

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])

B5.1: Tìm thấy tại vị trí Mid B5.2: Thực hiện Bkt

B6: IF (X < M[Mid])

B6.1: Last = Mid – 1 B6.2: Lặp lại B3

B7: IF (X > M[Mid])

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

Khoa CNTT Trường Cð CNTT TP.HCM

Bkt: Kết thúc

(cid:2) Cài ðặ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;

(cid:2) ðánh giá giải thuật

ðộ phức tập tính toán cấp n: T(n)=O(Log2n)

Khoa CNTT Trường Cð CNTT TP.HCM

}

2.2 Các giải thuật sắp xếp

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

Khoa CNTT Trường Cð CNTT TP.HCM

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

(cid:1) ðể thuận tiện và giảm thiểu thời gian thao tác mà ñặc biệt là ñể tìm kiếm. Do vậy sắp xếp dữ liệu là một trong những thao tác cần thiết và thường gặp trong quá trình lưu trữ, quản lý dữ liệu. (cid:1) 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ự tăng hoặc giảm dựa trên nội dung lưu trữ trên mỗi phần tử. (cid:1) Có rất nhiều thuật toán sắp xếp song chúng ta chỉ quan tâm ñến 5 giải thuật sắp xếp thường sử dụng.

Khoa CNTT Trường Cð CNTT TP.HCM

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

. . . . . . . . . .

an-1

Giả sử mảng có thứ tự tăng dần, nếu iaj thì gọi là nghịch thế

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ử)

Khoa CNTT Trường Cð CNTT TP.HCM

2.2.2. Giải Thuật ðổi Chổ Trực Tiếp-Interchange Sort

(cid:2) Ý tưởng:

(cid:3) Xuất phát từ ñầu dãy, tìm tất cả nghịch thế chứa

phần tử này.

(cid:3) Triệt tiêu chúng bằng cách ñổi chỗ phần tử này với

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

(cid:3) Lặp lại xử lý trên với các phần tử tiếp theo trong dãy.

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2) Minh Họa

2 8 5 1 6 4 12

Khoa CNTT Trường Cð CNTT TP.HCM

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

12 2 8 5 1 6 4 Ban ñầu

1 12 8 5 2 6 4 Lần 1

1 2 12 8 5 6 4 Lần 2

2 4 12 8 6 5 1 Lần 3

2 4 5 12 8 6 1 Lần 4

2 4 5 6 8 12 1 Lần 5

Khoa CNTT Trường Cð CNTT TP.HCM

2 4 5 6 8 12 1 Lần 6

(cid:2) Giải thuật:

Bước 1 :

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

Bước 2 :

j = i+1;//tìm các phần tử a[j] < a[i], j>i

Bước 3 :

Trong khi j < N thực hiện Nếu a[j]

Bước 4 :

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

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2) Cài ðặt

void InterchangeSort(int a[], int N ) i, j,tam; { int 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 CNTT Trường Cð CNTT TP.HCM

(cid:2) ðánh giá giải thuật:

(cid:3) Ðối với giải thuật ñổi chỗ trực tiếp, số lượ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 (cid:3) Nhưng số lượng phép hoán vị thực hiện tùy thuộc vào kết qủa so sánh

Khoa CNTT Trường Cð CNTT TP.HCM

2.2.3 Giải Thuật Chọn Trực Tiếp –Selection Sort

(cid:2) Ý Tưởng:

(cid:3) ðầu tiên dãy có N phần tử, ta chọn phần tử nhỏ nhất

trong dãy ñổi chổ cho phần tử ñầu tiên.

(cid:3) Tiếp theo, tìm phần tử nhỏ nhất của dãy n-1 phần tử còn lại trong dãy ñổi chổ cho phần tử thứ 2 của dãy. (cid:3) Quá trình trên thực hiên ñến khi nào trong mảng chỉ

còn 1 phần tử thi dừng lại.

(cid:3) Kết quả ñược mảng ñã sắp xếp tăng.

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2) 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

16

11

45

28

73

61

7

23

Khoa CNTT Trường Cð CNTT TP.HCM

I=1

(cid:2) 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

7

11

45

28

73

61

16

23

Khoa CNTT Trường Cð CNTT TP.HCM

I=2

(cid:2) 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

7

11

45

28

73

61

16

23

Khoa CNTT Trường Cð CNTT TP.HCM

I=3

(cid:2) 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

7

11

16

28

73

61

45

23

Khoa CNTT Trường Cð CNTT TP.HCM

I=4

(cid:2) 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

7

11

16

23

73

61

45

28

Khoa CNTT Trường Cð CNTT TP.HCM

I=5

(cid:2) 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

73

7

11 16 23

28

61

45

Khoa CNTT Trường Cð CNTT TP.HCM

I=6

(cid:2) 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

73

7

11 16 23

28

45

61

Khoa CNTT Trường Cð CNTT TP.HCM

I=7

(cid:2) 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

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

73

7

11 16 23

28

45

61

Khoa CNTT Trường Cð CNTT TP.HCM

16 11 45 28 73 61

7 23

Ban ñầu

7 11 45 28 73 61 16 23

Lần 1

7 11 45 28 73 61 16 23

Lần 2

7 11 16 28 73 61 45 23

Lần 3

7 11 16 23 73 61 45 28

Lần 4

7 11 16 23 28 61 45 73

Lần 5

7 11 16 23 28 45 61 73

Lần 6

7 11 16 23 28 45 61 73

Khoa CNTT Trường Cð CNTT TP.HCM

Lần 7

(cid:2) Giải thuật:

Bước 1:

I = 1

Bước 2:

Tìm phần tử nhỏ nhất a[min] trong dãy

hiện hành từ a[i] ñến a[min] Bước 3 :

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

Bước 4 :

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

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2)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 CNTT Trường Cð CNTT TP.HCM

(cid:2) ðánh giá giải thuật:

(cid:3)Ðối với giải thuật chọn trực tiếp, có thể thấy rằng ở lượt thứ i, bao giờ cũng cần (n-i) lần so sánh ñể xác ñịnh phần tử nhỏ nhất hiện hành. Số lượng 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:

Khoa CNTT Trường Cð CNTT TP.HCM

2.2.4. Giải Thuật Chèn Trực Tiếp –Insert Sort

(cid:2) Ý Tưởng:

(cid:3) Cho dãy ban ñầu a1, a2, …, an, ta có thể xem như ñã

có ñoạn gồm 1 phần tử a1 ñã ñược sắp xếp,

(cid:3) Sau ñó thêm a2 vào ñoạn a1 sẽ có ñoạn a1 a2 ñược

sắp xếp.

(cid:3) Tiếp tục thêm a3 vào ñoạn a1 a2 ñể có ñoạn a1 a2 a3

ñược sắp xếp.

(cid:3) Tiếp tục cho ñến thêm khi xong an vào ñoạn a1 a2

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2) 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

Kết thúc

3 4 7 9 11 13 17 15

1 2 3 4 5 6 7 8

i=8

Khoa CNTT Trường Cð CNTT TP.HCM

13 7 9 3 11 17 15 4 Ban ñầu

7 13 9 3 11 17 15 4 Lần 1

7 9 13 3 11 17 15 4 Lần 2

4 7 9 3 13 11 17 15 Lần 3

4 7 9 3 11 13 17 15 Lần 4

3 4 7 11 13 17 15 9 Lần 5

3 4 7 11 13 17 15 9 Lần 6

Khoa CNTT Trường Cð CNTT TP.HCM

3 4 7 11 13 15 17 9 Lần 7

(cid:2) Giải thuật:

Bước 1:

i=2; // a[1] ñã ñược sắp xếp

Bước 2:

x=a[i]; Tìm vị trí pos thích hợp trong ñoạn a[1] ñến a[i-1] ñể chèn a[i] vào

Bước 3:

Dời chỗ phần tử a[pos] ñến a[i-1] sang phải mộ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=i+1; Nếu i

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2)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 CNTT Trường Cð CNTT TP.HCM

(cid:2) ðánh giá giải thuật:

(cid:3) 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. (cid:3) Giải thuật thực hiện tất cả n – 1 vòng lặp while, do số lượng phép so sánh và dời chỗ này phụ thuộc vào tình trạng của dãy số ban ñầu, nên chỉ có ước lượng trong từng trường hợp sau:

Khoa CNTT Trường Cð CNTT TP.HCM

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

(cid:2) Ý Tưởng:

(cid:3) Xuất phát từ cuối dãy ,ñổi chổ các cặp phần tử kế cận ñể ñưa phần tử ñó về vị trí ñứng ñầu dãy hiện hành

(cid:3) Sau ñó sẽ không xét ñến nó ở bước tiếp theo (cid:3) Do vậy ở lần xử lý thứ i sẽ có vị trí dầu dãy là i phần

tử ñược sắp xếp.

(cid:3) Lặp lại xử lý trên cho ñến khi không còn phần tử nào

ñể xét.

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2) Minh Họa

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

Ban ñầu

11 11 i

5 5

7 7

3 3

9 9

2 2

15 15

Khoa CNTT Trường Cð CNTT TP.HCM

1 1 j

(cid:2) Minh Họa

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

1 i

Khoa CNTT Trường Cð CNTT TP.HCM

15 j

(cid:2) Minh Họa

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

2 i

Khoa CNTT Trường Cð CNTT TP.HCM

15 j

(cid:2) Minh Họa

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

3 i

Khoa CNTT Trường Cð CNTT TP.HCM

15 j

(cid:2) Minh Họa

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

5 i

Khoa CNTT Trường Cð CNTT TP.HCM

15 j

(cid:2) Minh Họa

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

7 i

Khoa CNTT Trường Cð CNTT TP.HCM

15 j

(cid:2) Minh Họa

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

9 i

11 Kết thúc

Khoa CNTT Trường Cð CNTT TP.HCM

15 j

(cid:2) Minh Họa

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

11 1 1 1 1 1 1 1

5 11 2 2 2 2 2 2

7 5 11 3 3 3 3 3

3 7 5 11 5 5 5 5

9 3 7 5 11 7 7 7

2 9 3 7 7 11 9 9

15 2 9 9 9 9 11 11

Ban ñầu Bước 1

Bước 2 Bước 3

Bước 4

Bước 5 Bước 6 Bước 7

Khoa CNTT Trường Cð CNTT TP.HCM

1 15 15 15 15 15 15 15

(cid:2) Giải thuật:

Bước 1:

i=1;

Bước 2:

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

Nếu a[j]

Bước 3:

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

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2)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 CNTT Trường Cð CNTT TP.HCM

(cid:2) ðánh giá giải thuật:

(cid:3) Ðối với giải thuật nổi bọt, số lượ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 (cid:3) Nhưng số lượng phép hoán vị thực hiện tùy thuộc vào kết qủa so sánh

Khoa CNTT Trường Cð CNTT TP.HCM

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

(cid:2) Ý Tưởng:

(cid:3) Phân hoạch dãy M thành 2 dãy con thỏa mãn ñiều kiện: “1/2 Dãy bên trái chứa các phần tử nhỏ hơn các phần tử của 1/2 Dãy bên phải”

(cid:3) Nếu dãy con có nhiều hơn 1 phần tử thì thực hiện

sắp xếp dãy con (ðệ qui).

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2) 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

ðoạn cần sắp xếp

L=1 R=3

L=4 R=8

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2) 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

ðoạn cần sắp xếp

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2) 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

ðoạn cần sắp xếp

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2) 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

ðoạn cần sắp xếp

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2) 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

ðoạn cần sắp xếp

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2) 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

ðoạn cần sắp xếp

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2) 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

L

R

X=2

2 1 3 5 7 9 10 15

i

j

L=1 R=3

ðoạn cần sắp xếp

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2) 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

ðoạn cần sắp xếp

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2) Minh Họa

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

10 5 7 3 7 9 10 15

1 2 3 5 7 9 10 15

ðoạn cần sắp xếp

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2) Giải thuật:

Bước 1:

i=1;

Bước 2:

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

Nếu a[j]

Bước 3:

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

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:2)Cài ðặt

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

j = Last;

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

i++; j--;

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 CNTT Trường Cð CNTT TP.HCM

}

(cid:2) ðánh giá giải thuật:

+ Trường hợp tốt nhất, khi mảng M có thứ tự tăng:

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

+ Trường hợp xấu nhất, khi phần tử X ñược chọn ở giữa dãy con là giá trị lớn nhất:

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

+ Trung bình:

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

Khoa CNTT Trường Cð CNTT TP.HCM

(cid:1)Chi phí trung bình O(n*log2n) (cid:1)Chi phí cho trường hợp xấu nhất O(n2) (cid:1)Chi phí này phụ thuộc vào cách chọn phần tử trục:

- Nếu chọn ñược phần tử có giá trị trung bình ta 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 nhất) (cid:4) O(n2)

Khoa CNTT Trường Cð CNTT TP.HCM

2.3 Bài Tập

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

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ự

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

Khoa CNTT Trường Cð CNTT TP.HCM

1. Trình bày tư tưởng và minh họa 5 giả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 CNTT Trường Cð CNTT TP.HCM