Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2.2

Chương 2.2. Giải thuật sắp xếp

ầ

Tr n Minh Thái Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn

Mục tiêu

 Nắm vững, minh họa và tính toán được

các phép so sánh, phép gán/ hoán vị của

các giải thuật sắp xếp cơ bản trên mảng

một chiều

 Cài đặt được các giải thuật bằng ngôn

ngữ C#

Các khái niệm

 Để truy xuất thông tin nhanh chóng và chính xác  thông tin phải được sắp xếp theo một trật tự hợp lý nào đó

 Một số CTDL đã định nghĩa trước trật tự của các phần tử, khi đó mỗi phần tử khi thêm vào phải đảm bảo trật tự này

 Sắp xếp là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin) để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu giữ tại mỗi phần tử

Các khái niệm

 Khái niệm nghịch thế

a1 a2 a3

a4 … … aN-

aN- 1

Giả sử xét mảng có thứ tự tăng dần, nếu có

iaj thì ta 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 khái niệm

 Tương tự như các giải thuật tìm kiếm, khối lượng công việc phải thực hiện có liên quan chặt chẽ với số lần so sánh các khóa

 Ngoài ra, các giải thuật sắp xếp còn phải di

chuyển các phần tử

 Chiếm nhiều thời gian khi các phần tử có kích thước lớn

Các giải thuật sắp xếp cơ bản

 Đổi chổ trực tiếp – Interchange Sort

 Chọn trực tiếp – Selection Sort

 Chèn trực tiếp – Insertion Sort

 Nổi bọt – Bubble Sort

 Quick Sort

 Một số giải thuật khác đọc thêm trong tài

liệu

Đổi chổ trực tiếp – interchange sort

 Ý tưởng

Ý tưởng chính của giải thuật là xuất phát từ đầu

dãy, tìm tất cả nghịch thế chứa phần tử này, 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ế. Lặp lại

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

Đổi chổ trực tiếp – interchange sort Giả sử cần sắp xếp dãy số sau tăng dần

15

10

9

7

5

1 2 3

3 4

2 6

1 8

Đổi chổ trực tiếp – interchange sort Bước 1: Xét phần tử đầu tiên (tại vị trí 1)

15

10

9

7

5 3 4

2 6

1 8

1 2

i j

Đổi chổ trực tiếp – interchange sort Bước 1: Xét phần tử đầu tiên (tại vị trí 1)

15

10

9

7

5 3 4

2 6

1 8

2 1

j i

Đổi chổ trực tiếp – interchange sort Bước 1: Xét phần tử đầu tiên (tại vị trí 1)

15

10

9

7

5

2 3 1 5

3 4

2 6

1 8

j i

Đổi chổ trực tiếp – interchange sort Bước 1: Xét phần tử đầu tiên (tại vị trí 1)

15

10

9

7

5

2 3

3 1

4 5

2 6

1 8

i j

Đổi chổ trực tiếp – interchange sort Bước 1: Xét phần tử đầu tiên (tại vị trí 1)

15

10

9

7

5

2 3 4

3 1

2 6

1 8

i j

Đổi chổ trực tiếp – interchange sort Bước 1: Xét phần tử đầu tiên (tại vị trí 1)

15

10

9

7

5

2 3 4 5

2 1

3 6

1 8

i j

Đổi chổ trực tiếp – interchange sort Bước 1: Xét phần tử đầu tiên (tại vị trí 1)

15

10

9

7

5

2 3 4 5

3 6

2 1

1 8

i j

Đổi chổ trực tiếp – interchange sort Bước 1: Xét phần tử đầu tiên (tại vị trí 1)

Kết thúc bước 1 15

10

9

7

5

2 3 4 5

3 6

1 1 1

2 8

i j

Đổi chổ trực tiếp – interchange sort Bước 2: Xét phần tử thứ hai (tại vị trí 2)

15

10

9

7

5

2 3

1 1 1

5 4

3 6

2 8

j i

Đổi chổ trực tiếp – interchange sort Bước 2: Xét phần tử thứ hai (tại vị trí 2)

15

10

9

7

5 1 1 1

3 2 5 4

3 6

2 8

j i

Đổi chổ trực tiếp – interchange sort Bước 2: Xét phần tử thứ hai (tại vị trí 2)

15

10

9

7

5 1 1 1

2 3 4 5

3 6

2 8

i j

Đổi chổ trực tiếp – interchange sort Bước 2: Xét phần tử thứ hai (tại vị trí 2)

15

10

9

7

5

3 4

1 1 1

2 7

3 6

2 8

i j

Đổi chổ trực tiếp – interchange sort Bước 2: Xét phần tử thứ hai (tại vị trí 2)

15

10

9

7

5

3 4 5

1 1 1

3 2

2 8

i j

Đổi chổ trực tiếp – interchange sort Bước 2: Xét phần tử thứ hai (tại vị trí 2)

15

10

9

7

5

3 4 5 6

1 1 1

3 2

2 8

i j

Đổi chổ trực tiếp – interchange sort Bước 2: Xét phần tử thứ hai (tại vị trí 2)

Kết thúc bước 2 15

10

9

7

5

3 4 5 6 7

1 1 1

2 2 2

3 8

i j

Đổi chổ trực tiếp – interchange sort Bước 3: Xét phần tử thứ ba (tại vị trí 3)

15

10

9

7

5

3 4

1 1 1

2 2 2

5 6 7

3 8

j i

Đổi chổ trực tiếp – interchange sort Bước 3: Xét phần tử thứ ba (tại vị trí 3)

15

10

9

7

5 1 1 1

2 2 2

4 3 5 6 7

3 8

j i

Đổi chổ trực tiếp – interchange sort Bước 3: Xét phần tử thứ ba (tại vị trí 3)

15

10

9

7

5 1 1 1

2 2 2

4 5 3 7 6

3 8

j i

Đổi chổ trực tiếp – interchange sort Bước 3: Xét phần tử thứ ba (tại vị trí 3)

15

10

9

7

5 1 1 1

2 2 2

4 5 3 7

3 8

i j

Đổi chổ trực tiếp – interchange sort Bước 3: Xét phần tử thứ ba (tại vị trí 3)

15

10

9

7

5 1 1 1

2 2 2

4 5 6 3 7

3 8

i j

Đổi chổ trực tiếp – interchange sort Bước 3: Xét phần tử thứ ba (tại vị trí 3)

Kết thúc bước 3 15

10

9

7

5

4 5 6 7 8

1 1 1

2 2 2

3 3 3

j i

Đổi chổ trực tiếp – interchange sort Bước 4: Xét phần tử thứ tư (tại vị trí 4)

15

10

9

7

5 1 1 1

2 2 2

4 5

3 3 3

7 6 8

j i

Đổi chổ trực tiếp – interchange sort Bước 4: Xét phần tử thứ tư (tại vị trí 4)

15

10

9

7

5 1 1 1

2 2 2

3 3 3

7 6 8 4 5

i j

Đổi chổ trực tiếp – interchange sort Bước 4: Xét phần tử thứ tư (tại vị trí 4)

15

10

9

7

5 1 1 1

2 2 2

3 3 3

5 6 4 7 8

j i

Đổi chổ trực tiếp – interchange sort Bước 4: Xét phần tử thứ tư (tại vị trí 4)

15

10

9

7

5 1 1 1

2 2 2

3 3 3

5 6 4 7 8

i j

Đổi chổ trực tiếp – interchange sort Bước 4: Xét phần tử thứ tư (tại vị trí 4)

Kết thúc bước 4 15

10

9

7 5 5

1 1 1

2 2 2

3 3 3

5 6 7 4 8

i j

Đổi chổ trực tiếp – interchange sort Bước 5: Xét phần tử thứ năm (tại vị trí 5)

15

10

9

7 5 5

1 1 1

2 2 2

3 3 3

5 6 4 7 8

j i

Đổi chổ trực tiếp – interchange sort Bước 5: Xét phần tử thứ năm (tại vị trí 5)

15

10

9

7 5 5

1 1 1

2 2 2

3 3 3

4 8 7 5 6

i j

Đổi chổ trực tiếp – interchange sort Bước 5: Xét phần tử thứ năm (tại vị trí 5)

15

10

9

7 5 5

1 1 1

2 2 2

3 3 3

4 6 7 5 8

j i

Đổi chổ trực tiếp – interchange sort Bước 5: Xét phần tử thứ năm (tại vị trí 5)

Kết thúc bước 5 15

10

9 7 7

5 5

1 1 1

2 2 2

3 3 3

4 6 7 8 5

j i

Đổi chổ trực tiếp – interchange sort Bước 6: Xét phần tử thứ sáu (tại vị trí 6)

15

10

9 7 7

5 5

1 1 1

2 2 2

3 3 3

4 6 7 5 8

j i

Đổi chổ trực tiếp – interchange sort Bước 6: Xét phần tử thứ sáu (tại vị trí 6)

15

10

9 7 7

5 5

1 1 1

2 2 2

3 3 3

4 5 6 7 8

i j

Đổi chổ trực tiếp – interchange sort Bước 6: Xét phần tử thứ sáu (tại vị trí 6)

Kết thúc bước 6 15

10 9 9

7 7

5 5

1 1 1

2 2 2

3 3 3

4 5 7 8 6

j i

Đổi chổ trực tiếp – interchange sort Bước 7: Xét phần tử thứ bảy (tại vị trí 7)

15

10 9 9

7 7

5 5

1 1 1

2 2 2

3 3 3

4 5 7 8 6

j i

Đổi chổ trực tiếp – interchange sort Bước 7: Xét phần tử thứ bảy (tại vị trí 7)

Kết thúc bước 7

15 10 10

9 9

7 7

5 5

1 1 1

2 2 2

3 3 3

4 5 6 7 8

i j

Đổi chổ trực tiếp – interchange sort Hoàn tất sắp xếp

15 10 10

9 9

7 7

5 5

11 1

2 2 2

3 3 3

4 5 6 7 8

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;

j = j+1;

Nếu i < N: Lặp lại Bước 2.

Ngược lại: Dừng.

Cài đặt

void InterchangeSort(int []a, int N )

{

int i, j;

for (i = 0 ; i

for (j =i+1; j < N ; j++) if(a[j ]< a[i])

HoanVi(ref a[i], ref a[j]);

}

void HoanVi(ref int a, ref int b) {

int tam=a; a=b; b=tam;

}

Bài tập

§ Minh họa từng bước thực hiện của giải thuật Interchange Sort khi sắp dãy số sau tăng dần:

15

7

9

10

6

20

§ Cho biết tổng số phép hoán vị

1 2 3 4 5 6

§ Cài đặt phương thức sắp xếp theo phương pháp trên vào lớp CMyIntArray (có tính số phép so sánh và gán)

 Ðánh giá giải thuậ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, nhưng số lượng phép hoán vị thực hiện tùy thuộc vào kết quả so sánh, có thể ước lượng:

Các giải thuật sắp xếp cơ bản

 Đổi chổ trực tiếp – Interchange Sort

 Chọn trực tiếp – Selection Sort

 Nổi bọt – Bubble Sort

 Chèn trực tiếp – Insertion Sort

 Quick Sort

Chọn trực tiếp – selection sort

Ý tưởng:

 Chọn phần tử nhỏ nhất trong N phần tử ban đầu,

đưa phần tử này về vị trí đúng là đầu dãy hiện hành

(vị trí 1);

 Dãy hiện hành còn lại N-1 phần tử cần sắp xếp (từ vị

trí 2 đến N), lặp lại quá trình trên cho dãy hiện

hành...

 Thực hiện cho đến khi dãy hiện hành chỉ còn 1 phần

tử

Chọn trực tiếp – selection sort

Làm sao để xác định được vị trí

?

phần tử có giá trị nhỏ nhất trong một dãy gồm N phần tử?

Vấn đề tìm vị trí phần tử nhỏ nhất? Giả sử cần tìm vị trí phần tử nhỏ nhất trong dãy số sau ?

15

10

9

7

5

1 2 3

3 4

1 6

2 8

Vấn đề tìm vị trí phần tử nhỏ nhất? Bước 1: Giả sử vị trí phần tử nhỏ nhất là 1 (vtmin), phần tử này có giá trị 10

vtmi n

15

10

9

7

5

1 2 3

3 4

1 6

2 8

vtmi n

Vấn đề tìm vị trí phần tử nhỏ nhất? Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có 5 nhỏ hơn phần tử nào nhỏ hơn phần tử tại vtmin thì 10 nên cập cập nhật lại vtmin nhật vị trí min

15

10

9

7

5

1 2 3

3 4

1 6

2 8

Vấn đề tìm vị trí phần tử nhỏ nhất? Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmi n

7 lớn hơn 5 nên không cập nhật vị trí min

15

10

9

7

5

1 2 3

3 4

1 6

2 8

Vấn đề tìm vị trí phần tử nhỏ nhất? Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmi n

3 nhỏ hơn 5 nên cập nhật vị trí min

15

10

9

7

5

1 2 3

3 4

1 6

2 8

9 lớn hơn 3 nên không cập nhật vị trí min

Vấn đề tìm vị trí phần tử nhỏ nhất? Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmi n

15

10

9

7

5

1 2 3

3 4

1 6

2 8

1 nhỏ hơn 3 nên cập nhật vị trí min

Vấn đề tìm vị trí phần tử nhỏ nhất? Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin vtmi n

15

10

9

7

5

1 2 3

3 4

1 6

2 8

15 lớn hơn 1 nên không cập nhật vị trí min

Vấn đề tìm vị trí phần tử nhỏ nhất? Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin

vtmi n

15

10

9

7

5

1 2 3

3 4

1 6

2 8

Vấn đề tìm vị trí phần tử nhỏ nhất? Bước 2: So sánh giá trị tại vtmin với tất cả giá trị tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin

vtmi n

2 lớn hơn 1 nên không cập nhật vị trí min

15

10

9

7

5

1 2 3

3 4

1 6

2 8

Giải thuật tìm vị trí phần tử nhỏ nhất

Bước 1:

i=2, vt=1;

Bước 2:

Nếu i>N thì trả về giá trị vt, kết thúc;

Bước 3:

Nếu a[i]

i=i+1;

Quay lại Bước 2;

int TimVTMin(int []a, int n)

{

int vtmin=0;

int i=1;

while(i

{

if(a[i]

vtmin=i;

i++;

}

return vtmin;

}

Vấn đề tìm vị trí phần tử nhỏ nhất?

?

Hãy cài đặt hàm tìm và trả về vị trí của phần tử nhỏ nhất bằng ngôn ngữ C#, đầu vào là mảng số nguyên a, kích thước N?

Vấn đề tìm vị trí phần tử nhỏ nhất? Giả sử cần tìm vị trí phần tử nhỏ nhất bắt đầu từ vị trí k cho trước (ví dụ ? đoạn từ 3 đến 8) thì giải quyết như thế nào? Hãy viết hàm cài đặt bằng ngôn ngữ C#?

15

10

9

8

7

1 3

3 4

1 2

2 6

7 8

Chọn trực tiếp – selection sort

Giả sử cần sắp xếp dãy số sau tăng dần

15

10

9

7

5

1 2 3

3 4

2 6

1 8

Chọn trực tiếp – selection sort

Bước 1: Xét phần tử thứ nhất (vị trí • Tìm phần tử nhỏ nhất từ vị trí 1 đến 8 1) • Hoán vị 2 phần tử tại vị trí đang xét với vị trí phần tử

min

15

10

9

7

5

1 2 3

3 4

2 6

1 8

Chọn trực tiếp – selection sort

Bước 2: Xét phần tử thứ hai (vị trí 2) • Tìm phần tử nhỏ nhất từ vị trí 2 đến 8 • Hoán vị 2 phần tử tại vị trí đang xét với vị trí phần tử

min

15

10

9

7

5 1 1

2 3

3 4

2 6

7 8

Chọn trực tiếp – selection sort

Bước 3: Xét phần tử thứ ba (vị trí 3) • Tìm phần tử nhỏ nhất từ vị trí 3 đến 8 • Hoán vị 2 phần tử tại vị trí đang xét với vị trí phần tử

min

15

10

9

7

5 1 1

2 2

3 4

5 6 7 8

Chọn trực tiếp – selection sort

Bước 4: Xét phần tử thứ tư (vị trí 4) • Tìm phần tử nhỏ nhất từ vị trí 4 đến 8 • Hoán vị 2 phần tử tại vị trí đang xét với vị trí phần tử

min

15

10

9

7

5

4 5 6 7 8

1 1

2 2

3 3

Chọn trực tiếp – selection sort

Bước 5: Xét phần tử thứ năm (vị trí • Tìm phần tử nhỏ nhất từ vị trí 5 đến 8 5) • Hoán vị 2 phần tử tại vị trí đang xét với vị trí phần tử

min min

15

10

9

7

5 1 1

2 2

3 3

5 6 7 8 4

Chọn trực tiếp – selection sort

Bước 6: Xét phần tử thứ sáu (vị trí 6)• Tìm phần tử nhỏ nhất từ vị trí 6 đến 8 • Hoán vị 2 phần tử tại vị trí đang xét với vị trí phần tử

min min

15

10

9

7

5 1 1

2 2

3 3

4 6 5 7 8

Chọn trực tiếp – selection sort

Bước 7: Xét phần tử thứ bảy (vị trí 7)• Tìm phần tử nhỏ nhất từ vị trí 7 đến 8 • Hoán vị 2 phần tử tại vị trí đang xét với vị trí phần tử

min

15

10

9

7

5 1 1

2 2

3 3

4 5 7 8 6

Chọn trực tiếp – selection sort

Kết thúc giải thuật - hoàn tất sắp xếp

15

10

9

7

5 1 1

2 2

3 3

4 5 6 7 8

Giải thuật Bước 1: i = 1;

Bước 2: Tìm phần tử a[vtmin] nhỏ nhất trong dãy hiện hành từ a[i] đến a[N]

Bước 3: Hoán vị a[vtmin] 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: Dừng.

Cài đặt 1 void SelectionSort(int []a, int N )

{

int vtmin;

Tìm vị trí min tính từ i đến N- 1

for (int i=0; i

{ vtmin = i;

for(int j = i+1; j

{

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

vtmin=j;

}

HoanVi(ref a[vtmin], ref a[i]);

}

int TimVTMin(int []a, int N, int k)

{

int vtmin=k;

for(int i=k+1; i

{

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

if(a[i]

vtmin=i;

}

int vtmin; for (int i=0; i

return vtmin;

HoanVi(ref a[vtmin], ref a[i]);

}

} }

Cài đặt 2

Bài tập

§ Minh họa từng bước thực hiện của giải thuật

Selection Sort khi sắp dãy số sau tăng dần:

15 1

7 2

9 3

10 4

6 5

20 6

§ Cho biết tổng số phép gán và so sánh

Ðánh giá giải thuật

Ðố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 trong mọi trường hợp có thể kết luận:

Nổi bọt – bubble sort

Ý tưởng:

 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ử nhỏ hơn trong cặp phần tử đó về vị trí đúng đầu dãy hiện hành

 Sau đó sẽ không xét đến nó ở bước tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i



Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.

1 i

1 0

2

5

3

7

4

3

5

9

2

6

7 1 5

8

1 j

1 i

2 1 0

3

5

4

7

5

3

6

9

2

7

8 j

1 5

1

2 i

3 1 0

5

4

5

7

6

3

9

7

8 j

1 5

1

2

3 i

4 1 0

5

6

7

9

7

8 j

1 5

1

2

3

4

5 i

5 1 0

6

7

9

7

8 j

1 5

1

2

3

4

5

7 i

6 1 0

9

7

8 j

1 5

1

2

3

4

5

7

6

9 i

7

8 j

1 0 1 5

1

2

3

4

5

Kết thúc

5

7

6

9

7 i

8 1 0 1 5

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]

j = j-1;

Bước 3:

i = i+1;

Nếu i = N: Dừng

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

Cài đặt

void BubleSort(int []a, int N )

int i, j;

for (i = 0 ; i

{

for (j =N-1; j >i ; j --)

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

HoanVi(ref a[j], ref a[j-1]);

}

{

}

Đánh giá giải thuật

§ Trong mọi trường hợp, số phép so sánh là:

§ Số phép hoán vị:

§ Trường hợp xấu nhất: n(n-1)/2

§ Trường hợp tốt nhất: 0

(n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n2)

Cải tiến Buble Sort

 Dùng kỹ thuật đánh dấu biên khi xãy ra hoán

 Sinh viên nghiên cứu tài liệu và cài đặt giải

vị

thuật

Các giải thuật sắp xếp cơ bản

 Đổi chổ trực tiếp – Interchange Sort

 Chọn trực tiếp – Selection Sort

 Nổi bọt – Bubble Sort

 Chèn trực tiếp – Insertion Sort

 Quick Sort

Chèn trực tiếp – insertion sort

Ý tưởng

…

Cho dãy ban đầu a1 , a2 ,... ,an

…

ạ ộ ượ ắ ồ Đã có đo n g m m t ph n t c s p ầ ử a1 đ

Chèn trực tiếp – insertion sort

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

…

§ Tiếp tục thêm a3 vào đoạn a1 a2 để có đoạn a1

được sắp a1

…

§ Tiếp tục cho đến khi thêm xong aN vào đoạn a1

…

a2 a3 được sắp;

an a2 ...aN-1 sẽ có dãy a1 a2 .... aN được sắp.

Chèn trực tiếp – insertion sort

Giả sử cần sắp xếp dãy số sau tăng dần

15

10

9

7

5

1 2 3

3 4

2 6

1 8

Chèn trực tiếp – insertion sort Xem như phần tử thứ 1 đã có thứ tự Tìm vị trí thích hợp để chèn cho phần tử thứ 2

15

10

9

7

5

1 2 3

3 4

2 6

1 8

Chèn trực tiếp – insertion sort Hai phần tử đầu tiên đã có thứ tự Tìm vị trí thích hợp để chèn cho phần tử thứ 3

15

10

9

7

5

2 3 1 5

3 4

2 6

1 8

Chèn trực tiếp – insertion sort Ba phần tử đầu tiên đã có thứ tự Tìm vị trí thích hợp để chèn cho phần tử thứ 4

15

10

9

7

5

1 2 3

3 4

2 6

1 8

Chèn trực tiếp – insertion sort Bốn phần tử đầu tiên đã có thứ tự Tìm vị trí thích hợp để chèn cho phần tử thứ 5

15

10

9

7

5 3 1

2 4 5 3

2 6

1 8

Chèn trực tiếp – insertion sort Năm phần tử đầu tiên đã có thứ tự Tìm vị trí thích hợp để chèn cho phần tử thứ 6

15

10

9

7

5 3 1

2 3 4 5

2 6

1 8

100

Chèn trực tiếp – insertion sort Sáu phần tử đầu tiên đã có thứ tự Tìm vị trí thích hợp để chèn cho phần tử thứ 7

15

10

9

7

5 2 1

3 2

3 4 5 6 7

1 8

101

Chèn trực tiếp – insertion sort Bảy phần tử đầu tiên đã có thứ tự Tìm vị trí thích hợp để chèn cho phần tử thứ 8

15

10

9

7

5 2 1

3 2

3 4 5 6 7

1 8

102

Chèn trực tiếp – insertion sort Kết thúc giải thuật

15

10

9

7

5 1 1

2 2

3 3

103

4 5 6 7 8

Chèn trực tiếp – insertion sort

Chèn một phần tử x vào vị trí k của

mảng 1 chiều

?

Hãy viết hàm (C#) chèn x vào vị trí k của dãy a

543210

104

Chèn trực tiếp – insertion sort

Dựa vào đâu để xác định được vị trí chèn thích hợp của một giá trị trong

?

dãy có giá trị tăng dần? Hãy viết hàm chèn x vào dãy a tăng dần sao cho dãy a thu được cũng tăng dần

543210

105

Mô tả giải thuật bằng mã tự nhiên

// giả sử có đoạn a[1] đã được

Bước 1: i = 2; sắp

Bước 2: x = a[i];

p ặ L

Tìm vị trí pos thích hợp trong đoạn [1..i] để chèn a[i] vào

Bước 3: Dời chổ các phần tử từ pos đến i-1 sang phải 1 vị trí để dành chổ cho a[i]

Bước 4: a[pos] = x; // có đoạn a[1]..a[i] đã được sắp

106 Nếu i ≤ N : Lặp lại Bước 2.

Bước 5: i = i+1;

Ngược lại : Dừng.

void InsertionSort(int []a, int N )

{

int pos;

int x; for(int i=1 ; i

x = a[i];

pos = i-1;

while((pos >= 0)&&(a[pos] > x)) {

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

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

107

}

Bài tập

§ Minh họa từng bước thực hiện

543210

khi áp dụng giải thuật Insertion Sort

để sắp xếp dãy số sau tăng dần

15 1

7 2

9 3

10 4

6 5

20 6

108

 Cho biết tổng số phép gán và số phép so sánh của các phần tử trong dãy

Đánh giá giải thuật

§ Mỗi lần lặp:

ü So sánh tìm vị trí thích hợp pos

3210

ü Dời chỗ phần tử sang phải 1 vị trí

§ Giải thuật thực hiện tất cả N-1 vòng lặp

ườ

ợ

ố

S phép so sánh ???

S phép gán ???

ấ

???

109

!!! 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 Tr ng h p ấ ố T t nh t ấ X u nh t

Đánh giá giải thuật

110

§ “Chèn trực tiếp” và “Chọn trực tiếp” đều có chi

Kết luận

phí cho trường hợp xấu nhất là O(n2) do đó,

§ Dễ cài đặt, dễ kiểm lỗi

§ “Chèn trực tiếp” tốt hơn “Chọn trực tiếp”, nhất là

không thích hợp cho việc sắp xếp các mảng lớn

khi mảng đã có thứ tự sẵn

 Cần có những giải thuật hiệu quả hơn cho việc

111

sắp xếp các mảng lớn

Các giải thuật sắp xếp cơ bản

 Đổi chỗ trực tiếp – Interchange Sort

 Chọn trực tiếp – Selection Sort

 Nổi bọt – Bubble Sort

 Chèn trực tiếp – Insertion Sort

 Quick Sort

112

Quick sort

 Chia dãy cần sắp thành 2 phần

 Cách “chia”: ½ dãy bên trái chứa các giá trị nhỏ

 Thực hiện việc sắp xếp trên từng dãy con (đệ

hơn ½ dãy bên phải

qui)

113

(x là phần tử trong dãy)

Quick sort

VD: 3; 5; 8; 10; 31; 4; 81; 7; 15; 17; 1.

§ Phần nhỏ hơn x: 3; 5; 8; 4; 7; 1

§ Phần lớn hơn x: 31; 81; 15; 17

114

Giả sử x = 10 thì sẽ có 2 phần như sau:

i=1, j=8

x

L

R

5

7

3

9

2

1 1 0 1

1 5 7

i

j

Đoạn 2

Đoạn 1

L=1 R=8

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

115

L=1 R=3

L=4 R=8

i=4, j=8

x

L

R

2

3

1

9

7

5 1 5 7

1 0 8

i

j

Đoạn 1

Đoạn 2

L=4 R=8 L=1 R=3

L=4 R=5

L=5 R=8

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

116

i=5, j=8

x

L

R

2

3

1

5

7

9 1 5 7

1 0 8

i

j

Đoạn 2

L=5 R=8 L=4 R=5 L=1 R=4

L=6 R=8

117

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

i=6, j=8

x

L

R

2

3

1

5

7

9 1 5 7

1 0 8

i

j

Đoạn 1

L=6 R=8 L=4 R=5 L=1 R=4

L=6 R=7

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

118

x

i=6, j=7

L

R

2

3

1

5

7

9 1 0 7

1 5 8

i

j

L=6 R=7 L=4 R=5 L=1 R=4

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

119

x

i=4, j=5

L

R

2

3

5

7

1

9 1 0 7

1 5 8

i

j

L=4 R=5 L=1 R=4

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

120

i=1, j=4

x

L

R

2

3

1

5

7

9 1 0 7

1 5 8

i

j

Đoạn 2

L=1 R=4

L=3 R=4

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

121

x

i=3, j=4

L

R

2

3

1

5

7

9 1 0 7

1 5 8

i

j

L=3 R=4

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

122

2

3

1

5

7

9 1 0 7

1 5 8

Không còn đoạn nào cần sắp xếp! Kết thúc

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

123

Giải thuật Cho dãy aL, aL+1, … aR

Bước 1:

 Dãy con 1: aL … aj < x

 Dãy con 2: aj+1 … ai-1 =x

 Dãy con 3: ai … aR > x

Phân hoạch dãy aL … aR thành các dãy con:

 Nếu (L

 Nếu (i

124

Bước 2:

Giải thuật phân hoạch dãy aL, aL+1, … aR thành 2 dãy con

Bước 1.1:

Chọn tùy ý một phần tử a[k] trong dãy, L≤k≤R

x=a[k], i=L, j=R

Bước 1.2:

Phát hiện và hiệu chỉnh cặp a[i] và a[j] nằm sai

chỗ:

Bước 1.2a: Trong khi (a[i]

Bước 1.2b: Trong khi (a[j]>x) j--

Bước 1.2c: Nếu (i≤j): Hoán vị a[i] và a[j]; i++, j--

125

Bước 1.3:

Nếu i

Ngược lại: Dừng phân hoạch

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

{

int i, j, x;

x=a[(left+right)/2]; i=left; j=right;

do{ while(a[i]

while(a[j]>x)

j--;

if(i<=j)

{

HoanVi(a[i], a[j]);

i++;

j--;

}

} while(i

if(left

126

if(i

}

Bài tập

Minh họa từng bước thực hiện của giải thuật Quick Sort khi sắp dãy số sau tăng dần:

127

15 1 7 2 9 3 10 4 6 5 20 6 6 7 9 8 12 30 10 9

Đánh giá giải thuật

 Chi phí trung bình O(n*log2n)

 Chi phí cho trường hợp xấu nhất O(n2)

 Chi phí tùy 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)  O(n2)

128

Bài tập thuyết trình

1. Shell Sort (1-15)

2. Heap Sort (16-30)

3. Merge Sort (31-45)

4. Radix Sort (46-60)

5. Shaker Sort (61-69)

129

Nghiên cứu và trình bày minh hoạ các thuật toán:

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2.2 - Trần Minh Thái (2016)

Chủ đề:

Cấu trúc dữ liệu