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
1
Mục tiêu
Nắm vững, minh họa và tính toán được
các phép gán (hoán vị) 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++
2
Các khái niệm
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
3
tử.
Các khái niệm
Khái niệm nghịch thế
a1 a2 a3
a4 … … aN-
aN
aN- 1
2
Giả sử xét mảng có thứ tự tăng dần, nếu có
i
Mục tiêu của sắp xếp là khử các nghịch thế
4
(bằng cách hoán vị)
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
5
Đổ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
6
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
5
2 6
7
1 8
7
Đổ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
3 4
5
2 6
7
1 8
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
3 4
5
2 6
7
1 8
9
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
7
1 8
10
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
7
1 8
11
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
7
2 6
1 8
12
5
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
7
3 6
1 8
13
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
7
1 8
14
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
7
1 1 1
2 8
15
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
7
2 8
16
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
7
2 8
17
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
7
2 8
18
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
19
5
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
7
2 8
20
6
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
7
2 8
21
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
22
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
23
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
24
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
25
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
26
6
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
27
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
28
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
29
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
30
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
31
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
32
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
33
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
34
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
35
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
36
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
37
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
38
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
39
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
40
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
41
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
42
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
43
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. 44 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(a[i],a[j]); } } void HoanVi(int &a, int &b)
{ 45 int tam=a;
a=b;
b=tam; } § 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: § Cho biết tổng số phép hoán vị 46 1 2 3 4 5 6 Ðánh giá giải thuật 47 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 trong từng trường
hợp như sau: Ý 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; lúc này dãy hiện hành chỉ còn N-1 phần tử cần sắp xếp, bắt đầu từ vị trí thứ 2; lặp lại quá trình trên cho dãy hiện hành... đến khi dãy hiện hành chỉ còn 1 48 phần tử 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ử? 49 1 2 3 5 7 50 1 2 3 5 7 51 52 1 2 3 5 7 7 lớn hơn 5
nên không
cập nhật vị
trí min 53 1 2 3 5 7 3 nhỏ hơn 5
nên cập
nhật vị trí
min 54 1 2 3 5 7 9 lớn hơn 3
nên không
cập nhật vị
trí min 55 1 2 3 5 7 1 nhỏ hơn 3
nên cập
nhật vị trí
min 56 1 2 3 5 7 15 lớn hơn 1
nên không
cập nhật vị
trí min 57 1 2 3 5 7 2 lớn hơn 1
nên không
cập nhật vị
trí min 58 1 2 3 5 7 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? 59 60 1 3 5 7 8 Giả sử cần sắp xếp dãy số sau tăng
dần 1 2 3 5 7 61 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 min 1 2 3 5 62 7 i 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 min 2 3 5 63 7 8 i 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 min 3 64 5 6 7 8 i 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 min 4 5 6 7 8 65 i 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 66 5 6 7 8 4 i 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 67 4 6 5 7 8 i 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 min 68 4 5 7 8 6 i Kết thúc giải thuật - hoàn tất sắp
xếp 69 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. 70 { 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]) 71 vtmin=j; } HoanVi(a[vtmin], a[i]); } } int TimVTMin(int a[], int N, int k) void SelectionSort(int a[],int N )
{ { int vtmin=k; for(int i=k+1; i { if(a[i] int vtmin;
for (int i=0; i vtmin=i; }
} } return vtmin; } 72 Cài đặt 2 § 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: § Cho biết tổng số phép gán tìm min và tổng số 73 phép hoán vị Ðá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 : 74 75 Ý 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. 76 77 78 79 80 81 82 Kết
thúc 83 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; 84 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(a[j],a[j-1]); } } 85 { } § 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 86 (n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n2) Đổ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 87 Ý tưởng a1 a2 a3 a4 … an Cho dãy ban đầu a1 , a2 ,... ,an a1 a2 a3 a4 … an 88 ạ ộ ượ ắ ồ
1. Đã có đo n g m m t ph n t c s p ầ ử a1 đ § Sau đó thêm a2 vào đoạn a1 sẽ có đoạn a1 a2 a2 a3 a4 … an § Tiếp tục thêm a3 vào đoạn a1 a2 để có đoạn a1 được sắp
a1 a1 a2 a3 a4 … an § Tiếp tục cho đến khi thêm xong aN vào đoạn a1 … a3 a4 a1 a2 a2 a3 được sắp; 89 Giả sử cần sắp xếp dãy số sau tăng dần 1 2 3 5 7 90 1 2 3 5 7 91 2 3 1 5 7 92 1 2 3 5 7 93 2 4 5 3 7 94 2 3 4 5 7 95 3 4 5 6 7 96 3 4 5 6 7 97 98 4 5 6 7 8 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 99 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 100 // giả sử có đoạn a[1] đã được Bước 1: i = 2;
sắp Bước 2: x = a[i]; 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 101
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 102 } } § Minh họa từng bước thực hiện khi áp dụng giải thuật Insertion Sort để sắp xếp dãy số sau tăng dần 103 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 § Mỗi lần lặp: ü So sánh tìm vị trí thích hợp pos ü 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
??? ấ ??? ??? 104 !!! 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 105 § “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 106 sắp xếp các mảng lớ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 107 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 x >x qui) 108 (x là phần tử trong dãy) § Phần nhỏ hơn x: 3; 5; 8; 4; 7; 1 § Phần lớn hơn x: 31; 81; 15; 17 109 VD: 3; 5; 8; 10; 31; 4; 81; 7; 15; 17; 1. Giả sữ x
= 10 thì sẽ có 2 phần như sau: 4 2 3 5 6 8 110 1 2 3 5 4 6 111 1 2 3 4 6 5 112 1 2 3 4 5 6 113 1 2 3 4 5 6 114 4 5 1 2 3 6 115 2 3 1 4 5 6 116 1 2 3 4 5 6 117 1 2 3 4 5 6 Không còn đoạn
nào cần sắp xếp!
Kết thúc 118 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 119 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-- 120 Bước 1.3: Nếu i Ngược lại: Dừng phân hoạch { 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 121 if(i } 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: 122 15
1 7
2 9
3 10
4 6
5 20
6 6
7 9
8 12 30
10
9 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) 123Bài tập
15
7
9
10
6
20
Chọn trực tiếp – selection sort
Chọn trực tiếp – selection sort
?
Chọn trực tiếp – selection sort
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
3
4
1
6
2
8
Chọn trực tiếp – selection sort
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
3
4
1
6
2
8
vtmi
n
Chọn trực tiếp – selection sort
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
3
4
1
6
2
8
Chọn trực tiếp – selection sort
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
3
4
1
6
2
8
Chọn trực tiếp – selection sort
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
3
4
1
6
2
8
Chọn trực tiếp – selection sort
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
3
4
1
6
2
8
Chọn trực tiếp – selection sort
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
3
4
1
6
2
8
Chọn trực tiếp – selection sort
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
3
4
1
6
2
8
Chọn trực tiếp – selection sort
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
3
4
1
6
2
8
Chọn trực tiếp – selection sort
Tìm vị trí phần tử nhỏ nhất?
?
Chọn trực tiếp – selection sort
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
3
4
1
2
2
6
Chọn trực tiếp – selection sort
15
10
9
7
5
3
4
2
6
1
8
Chọn trực tiếp – selection sort
15
10
9
7
5
3
4
2
6
1
8
Chọn trực tiếp – selection sort
15
10
9
7
5
1
1
3
4
2
6
Chọn trực tiếp – selection sort
15
10
9
7
5
1
1
2
2
3
4
Chọn trực tiếp – selection sort
15
10
9
7
5
1
1
2
2
3
3
Chọn trực tiếp – selection sort
15
10
9
7
5
1
1
2
2
3
3
Chọn trực tiếp – selection sort
15
10
9
7
5
1
1
2
2
3
3
Chọn trực tiếp – selection sort
15
10
9
7
5
1
1
2
2
3
3
Chọn trực tiếp – selection sort
15
10
9
7
5
1
1
2
2
3
3
Cài đặt 1
void SelectionSort(int a[],int N )
Bài tập
15
1
7
2
9
3
10
4
6
5
20
6
Nổi bọt – bubble sort
1
i
1
0
2
5
3
7
4
3
5
9
2
6
7
1
5
8
1
j
1
1
i
2
1
0
3
5
4
7
5
3
6
9
2
7
8
j
1
5
1
1
2
2
i
3
1
0
5
4
5
7
6
3
9
7
8
j
1
5
1
1
2
2
3
3
i
4
1
0
5
5
6
7
9
7
8
j
1
5
1
1
2
2
3
3
4
5
i
5
1
0
6
7
9
7
8
j
1
5
1
1
2
2
3
3
4
5
5
7
i
6
1
0
9
7
8
j
1
5
1
1
2
2
3
3
4
5
5
7
6
9
i
7
8
j
1
0
1
5
1
1
2
2
3
3
4
5
5
7
6
9
7
i
8
1
0
1
5
Giải thuật
Bước 1:
Đánh giá giải thuật
Các giải thuật sắp xếp cơ bản
Chèn trực tiếp – insertion sort
Chèn trực tiếp – insertion sort
an
a2 ...aN-1 sẽ có dãy a1 a2 .... aN được sắp.
Chèn trực tiếp – insertion sort
15
10
9
7
5
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
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
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
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
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
6
1
8
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
1
8
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
1
8
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
Chèn trực tiếp – insertion sort
?
543210
Chèn trực tiếp – insertion sort
?
543210
Mô tả giải thuật bằng mã tự nhiên
p
ặ
L
Bài tập
543210
15
1
7
2
9
3
10
4
6
5
20
6
Đánh giá giải thuật
3210
Đánh giá giải thuật
Các giải thuật sắp xếp cơ bản
Quick sort
Quick sort
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
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
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
Đ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
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
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
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
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
2
3
1
5
7
9
1
0
7
1
5
8
Đoạn cần sắp xếp
Giải thuật
Cho dãy aL, aL+1, … aR
Cài đặt
void QuickSort(int a[], int left, int right)
Bài tập
Đánh giá giải thuật
![Bài giảng Thực hành cơ sở dữ liệu Trường ĐH Công Nghệ [năm] mới nhất](https://cdn.tailieu.vn/images/document/thumbnail/2025/20251120/oursky02/135x160/14661768233842.jpg)
%20--%3e%3cdefs%3e%3cstyle%3e%20.st0%20{%20fill:%20%23fff;%20}%20.st1%20{%20fill:%20%237800fa;%20}%20%3c/style%3e%3c/defs%3e%3cpath%20class='st1'%20d='M117.78,12.18H43.11c2.9,3.47,4.65,7.94,4.65,12.82,0,5.6-2.3,10.66-6.01,14.29h76.02l7.22-13.56-7.22-13.56Z'/%3e%3cg%3e%3cpath%20class='st0'%20d='M53.58,26.17h-.59v-1.46h.59v-4.96h2.83c1.78,0,2.67.94,2.67,2.82v5.76c0,1.87-.89,2.81-2.67,2.81h-2.83v-4.96ZM55.36,21.37v3.34h1.1v1.46h-1.1v3.34h1.01c.61,0,.91-.37.91-1.1v-5.93c0-.74-.3-1.1-.91-1.1h-1.01Z'/%3e%3cpath%20class='st0'%20d='M65.99,31.14h-1.8l-.31-2.07h-2.19l-.31,2.07h-1.64l1.82-11.39h2.62l1.82,11.39ZM65.28,18.04c-.25.46-.51.77-.75.94-.21.15-.47.22-.79.22-.26,0-.57-.07-.92-.22l-.38-.15c-.14-.05-.26-.07-.37-.07-.3,0-.53.18-.71.54l-.91-.68c.25-.46.51-.77.75-.94.21-.14.48-.21.79-.21.26,0,.57.07.92.21l.38.15c.14.05.26.07.37.07.3,0,.53-.18.71-.54l.91.68ZM61.91,27.52h1.73l-.87-5.76-.87,5.76Z'/%3e%3cpath%20class='st0'%20d='M74.53,26.89v1.52c0,1.91-.89,2.86-2.67,2.86s-2.67-.95-2.67-2.86v-5.93c0-1.91.89-2.86,2.67-2.86s2.67.95,2.67,2.86v1.11h-1.69v-1.22c0-.75-.31-1.12-.93-1.12s-.93.37-.93,1.12v6.15c0,.74.31,1.11.93,1.11s.93-.37.93-1.11v-1.63h1.69Z'/%3e%3cpath%20class='st0'%20d='M81.4,31.14h-1.8l-.31-2.07h-2.19l-.31,2.07h-1.64l1.82-11.39h2.62l1.82,11.39ZM75.9,19.2l1.52-1.91h1.71l1.51,1.91h-1.61l-.76-.95-.75.95h-1.61ZM77.32,27.52h1.73l-.87-5.76-.87,5.76ZM83.1,15.99l-1.76,1.91h-1.26l1.17-1.91h1.86Z'/%3e%3cpath%20class='st0'%20d='M84.86,19.75c1.78,0,2.67.94,2.67,2.82v1.48c0,1.87-.89,2.81-2.67,2.81h-.85v4.28h-1.79v-11.39h2.64ZM84.01,21.37v3.86h.85c.58,0,.87-.36.87-1.08v-1.71c0-.71-.29-1.07-.87-1.07h-.85Z'/%3e%3cpath%20class='st0'%20d='M93.51,19.75c1.78,0,2.67.94,2.67,2.82v1.48c0,1.87-.89,2.81-2.67,2.81h-.85v4.28h-1.79v-11.39h2.64ZM92.66,21.37v3.86h.85c.58,0,.87-.36.87-1.08v-1.71c0-.71-.29-1.07-.87-1.07h-.85Z'/%3e%3cpath%20class='st0'%20d='M98.8,31.14h-1.79v-11.39h1.79v4.88h2.03v-4.88h1.83v11.39h-1.83v-4.88h-2.03v4.88Z'/%3e%3cpath%20class='st0'%20d='M105.36,24.55h2.46v1.62h-2.46v3.34h3.09v1.63h-4.88v-11.39h4.88v1.63h-3.09v3.18ZM108.17,17.29l-1.76,1.91h-1.26l1.17-1.91h1.86Z'/%3e%3cpath%20class='st0'%20d='M112.2,19.75c1.78,0,2.67.94,2.67,2.82v1.48c0,1.87-.89,2.81-2.67,2.81h-.85v4.28h-1.79v-11.39h2.64ZM111.35,21.37v3.86h.85c.58,0,.87-.36.87-1.08v-1.71c0-.71-.29-1.07-.87-1.07h-.85Z'/%3e%3c/g%3e%3ccircle%20class='st1'%20cx='25'%20cy='25'%20r='20'/%3e%3cpath%20class='st0'%20d='M32.78,19.27c2.92,0,4.43,2.55,5.28,5.33l.71,2.17c.14.38-.33.75-.71.75h-5.61c.19-.33.24-.71.09-1.08l-.75-2.45c-.43-1.32-.99-2.64-1.79-3.77.75-.57,1.65-.94,2.78-.94h0ZM25,18.38c3.25,0,4.9,2.78,5.89,5.89l.76,2.45c.14.42-.33.8-.8.8h-11.69c-.42,0-.94-.38-.8-.8l.75-2.45c.99-3.11,2.64-5.89,5.89-5.89h0ZM25,11.35c1.74,0,3.11,1.37,3.11,3.11s-1.37,3.11-3.11,3.11-3.11-1.41-3.11-3.11,1.41-3.11,3.11-3.11h0ZM17.27,19.27c1.08,0,1.98.38,2.73.94-.8,1.13-1.37,2.45-1.74,3.77l-.8,2.45c-.14.38-.05.75.09,1.08h-5.56c-.42,0-.9-.38-.75-.75l.71-2.17c.9-2.78,2.41-5.33,5.33-5.33h0ZM17.27,12.91c1.51,0,2.78,1.27,2.78,2.83s-1.27,2.83-2.78,2.83-2.83-1.27-2.83-2.83,1.27-2.83,2.83-2.83h0ZM32.78,12.91c1.56,0,2.78,1.27,2.78,2.83s-1.23,2.83-2.78,2.83-2.83-1.27-2.83-2.83,1.27-2.83,2.83-2.83h0ZM27.07,28.56v.09c0,.57-.24,1.08-.61,1.46h0v.05c-.38.33-.9.57-1.46.57s-1.08-.24-1.46-.61h0c-.38-.38-.61-.9-.61-1.46v-.09h1.41v.09c0,.19.05.38.19.47v.05c.09.09.28.19.47.19s.38-.09.47-.19v-.05c.14-.09.24-.28.24-.47t-.05-.09h1.41ZM30.99,28.56v.09c0,1.65-.66,3.16-1.74,4.24-1.08,1.08-2.59,1.79-4.24,1.79s-3.16-.71-4.24-1.79l-.05-.05c-1.04-1.08-1.7-2.55-1.7-4.2v-.09h1.41v.09c0,1.27.47,2.4,1.27,3.25h.05c.85.85,1.98,1.37,3.25,1.37s2.4-.52,3.25-1.37c.85-.8,1.37-1.98,1.37-3.25v-.09h1.37ZM34.99,28.56v.09c0,2.78-1.13,5.28-2.92,7.07-1.79,1.79-4.29,2.92-7.07,2.92s-5.23-1.13-7.07-2.92c-1.79-1.79-2.92-4.29-2.92-7.07v-.09h1.41v.09c0,2.4.94,4.53,2.5,6.08,1.56,1.56,3.72,2.5,6.08,2.5s4.52-.94,6.08-2.5c1.56-1.56,2.5-3.68,2.5-6.08v-.09h1.41Z'/%3e%3c/svg%3e)