CHƯƠNG 2.(TT)
GIẢI THUẬT SẮP XẾP
Võ Quang Hoàng Khang Email: vqhkhang@gmail.com
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
Khái niệm
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ự thỏa mãn một tiêu chí nào đó dựa trên nội dung thông tin lưu giữ tại mỗi phần tử.
Khái niệm nghịch thế
a2
a3
a4 …
aN-2 aN-1 aN
…
a1
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ị)
3
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
4
Đổ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.
5
Đổ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
3
1 2 3 4 5
2 6
7
1 8
6
Đổ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
1 2
7
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
2 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
3
2 3 1 5 4
2 6
7
1 8
9
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
3
2 3 1 4 5
2 6
7
1 8
10
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
2 3 4 7
2 6
1 8
5 1
11
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
3
2 3 4 5
2 1
7
1 8
6
12
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
2 3 4 5 6
2 1
7
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)
Kết thúc bước 1 15
10
9
7
5
3
2 3 4 5 6 7
1 1 1
2 8
14
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
2 3
1 1 1
5 4 6 7
2 8
15
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
3
1 1 1
3 2 5 4 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
3
1 1 1
2 3 4 5 6 7
2 8
17
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
1 1 1
2 3 4 5 7 6
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
3 4 5
1 1 1
2 7
2 8
6
19
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
3 4 5 6
1 1 1
2 7
2 8
20
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
3 4 5 6 7
1 1 1
2 2 2
8
21
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
3 4
1 1 1
2 2 2
5 6 7 8
22
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
3
1 1 1
2 2 2
4 3 5 6 7 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
3
1 1 1
2 2 2
4 5 3 7 6 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
3
4 5
1 1 1
2 2 2
3 7 8 6
25
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
1 1 1
2 2 2
3 4 5 6 7 8
26
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
3 3
4 5 6 7 8
1 1 1
2 2 2
3
27
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
3 3
1 1 1
2 2 2
4 5 3 7 6 8
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
3 3
1 1 1
2 2 2
3 7 6 8 4 5
29
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
3 3
1 1 1
2 2 2
3 5 6 4 7 8
30
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
3 3
1 1 1
2 2 2
3 5 6 4 7 8
31
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
3 3
1 1 1
2 2 2
3 5 6 7 4 8
32
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
3 3
1 1 1
2 2 2
3 5 6 4 7 8
33
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
3 3
1 1 1
2 2 2
3 4 7 8 5 6
34
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
3 3
1 1 1
2 2 2
3 4 6 7 5 8
35
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
3 3
1 1 1
2 2 2
3 4 6 7 8 5
36
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
3 3
1 1 1
2 2 2
3 4 6 7 5 8
37
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
3 3
1 1 1
2 2 2
3 4 5 8 6 7
38
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
3 3
1 1 1
2 2 2
3 4 5 7 8 6
39
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
3 3
1 1 1
2 2 2
3 4 5 7 8 6
40
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
3 3
1 1 1
2 2 2
3 4 5 6 7 8
41
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
3 3
11 1
2 2 2
3 4 5 7 8 6
42
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 :
Nếu a[j] Trong khi j <= N thực hiện j = j+1; Bước 4 : i = i+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]) } }
void Hoanvi(int &a, int &b)
{ Hoanvi(a[i],a[j]); int tam=a;
a=b;
b=tam; } Ðá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 trong từng
trường hợp như sau: 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ị 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; 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 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ử? 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 ? 1 2 3 4 5 7 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 Chọn trực tiếp – selection sort
Tìm vị trí phần tử nhỏ nhất? 1 2 3 4 5 7 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 7 lớn hơn 5
nên không cập
nhật vị trí min 1 2 3 4 5 7 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 3 nhỏ hơn 5
nên cập nhật
vị trí min 1 2 3 4 5 7 Chọn trực tiếp – selection sort
Tìm vị trí phần tử nhỏ nhất? 1 2 3 4 5 7 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 1 2 3 4 5 7 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 1 2 3 4 5 7 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 2 lớn hơn 1
nên không cập
nhật vị trí min 1 2 3 4 5 7 Chọn trực tiếp – selection sort
Tìm vị trí phần tử nhỏ nhất? Hãy cài đặt hàm tìm và trả về vị trí
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? 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? 1 3 4 5 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 1 2 3 4 5 7 Chọn trực tiếp – selection sort Bước 1: Xét phần tử thứ nhất (vị trí 1)
• Tìm phần tử nhỏ nhất từ vị trí 1 đến 8
• Hoán vị 2 phần tử tại vị trí đang xét với vị trí phần tử min 2 3 4 5 7 1 i 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 min 2 3 4 5 7 8 i 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 3 4 5 6 7 8 i 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 6 7 8 4 5 3 i Chọn trực tiếp – selection sort Bước 5: Xét phần tử thứ năm (vị trí 5)
• Tìm phần tử nhỏ nhất từ vị trí 5 đến 8
• Hoán vị 2 phần tử tại vị trí đang xét với vị trí phần tử min 5 6 7 8 3 4 i 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 3 4 6 7 8 5 i 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 min 3 4 5 7 8 6 i Chọn trực tiếp – selection sort Kết thúc giải thuật - hoàn tất sắp xếp 3 4 5 7 8 6 i = 1; Giải thuật
Bước 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 < N thì lặp lại Bước 2 i = i+1
Nếu
Ngược lại: Dừng. Tìm vị trí min
tính từ i đến N Ðá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 : 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 7 9 10 6 20 Cho biết tổng số phép gán tìm min và tổng số phép hoán vị Minh họa từng bước thực hiện khi sắp dãy số sau tăng 15 7 9 10 6 20 dần: - Đổi chỗ trực tiếp. Cho biết tổng số phép hoán vị
- Chọn trực tiếp. Cho biết tổng số phép gán tìm min và tổng số phép hoán vị Chèn trực tiếp – insertion sort Giả sử cần sắp xếp dãy số sau tăng dần 1 2 3 4 5 7 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 1 2 3 4 5 7 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 2 1 3 4 5 7 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 1 2 3 4 5 7 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 1 2 4 5 3 7 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 1 2 3 4 5 7 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 2 3 4 5 6 7 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 2 3 4 5 6 7 Chèn trực tiếp – insertion sort
Kết thúc giải thuật 3 4 5 7 8 6 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? // giả sử có đoạn a[1] đã được sắp 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ỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chỗ cho a[i] // có đoạn a[1]..a[i] đã được sắp Bước 4: a[pos] = x;
Bước 5: i = i+1; Nếu i ≤ N : Lặp lại Bước 2.
Ngược lại : Dừng. void ChenTrucTiep(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 } } Đánh giá giải thuật Các phép so sánh xảy ra trong mỗi 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.
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ó thể ước lượng
trong từng trường hợp như sau: Bài tập Minh họa từng bước thực hiện của giải thuật
Insertion Sort khi sắp dãy số sau tăng dần: 15 7 9 10 6 20 Cho biết tổng số gán 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.
Lặp lại xử lý trên cho đến khi không còn cặp
phần tử nào để xét. Bước 2: i = 1; Nếu a[j] j = N;
Trong khi (j > i) thực hiện: 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. Bước 3: i, j; int
for (i = 0 ; i if(a[j]< a[j-1]) Hoanvi(a[j],a[j-1]); } Trong mọi trường hợp, số phép so sánh là: Số phép hoán vị: (n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n2) Trường hợp tốt nhất: 0 Trường hợp xấu nhất: n(n-1)/2 “Chèn trực tiếp” và “Chọn trực tiếp” đều có chi
phí cho trường hợp xấu nhất là O(n2) do đó,
không thích hợp cho việc sắp xếp các mảng lớn 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à 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 sắp xếp các mảng lớn 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ỏ hơn ½ dãy bên phải Thực hiện việc sắp xếp trên từng dãy con (đệ 1 4 2 3 5 6 7 8 1 2 3 5 7 4 6 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 4 5 1 2 3 6 7 8 3 5 6 7 8 2 1 4 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 Không còn đoạn
nào cần sắp xếp!
Kết thúc Nếu (L Chọn tùy ý một phần tử a[k] trong dãy là giá trị mốc, L≤k≤R x=a[k], i=L, j=R Phát hiện và hiệu chỉnh cặp a[i] và a[j] nằm sai chỗ:
Bước 2a: Trong khi (a[i] Nếu i int i, j, x;
x=a[(left+right)/2];
i=left, j=right;
do{ while(a[i] if(i<=j)
{ HoanVi(a[i], a[j]);
i++;
j--; } QuickSort(a, left, j);
QuickSort(a, i, right); } while(i } tùy thuộc vào cách chọn phần tử Chi phí trung bình O(n*log2n)
Chi phí cho trường hợp xấu nhất O(n2)
Chi phí
“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)43
44
45
46
47
?
48
15
10
9
7
5
3
1
6
2
8
49
vtmin
15
10
9
7
5
3
1
2
3
4
5
1
6
7
2
8
50
vtmin
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
5 nhỏ hơn 10
nên cập nhật
vị trí min
15
10
9
7
5
3
51
1
6
2
8
vtmin
15
10
9
7
5
3
52
1
6
2
8
vtmin
15
10
9
7
5
3
53
1
6
2
8
Bước 2: So sánh giá trị tại vtmin với tất cả giá trị
9 lớn hơn 3
tại vị trí còn lại (từ 2 đến 8), nếu có phần tử nào
nên không cập
nhỏ hơn phần tử tại vtmin thì cập nhật lại vtmin
nhật vị trí min
vtmin
15
10
9
7
5
3
54
1
6
2
8
1 nhỏ hơn 3
nên cập nhật
vị trí min
vtmin
15
10
9
7
5
3
55
1
6
2
8
15 lớn hơn 1
nên không cập
nhật vị trí min
vtmin
15
10
9
7
5
3
56
1
6
2
8
vtmin
15
10
9
7
5
3
57
1
6
2
8
?
58
?
15
10
9
8
7
3
59
1
2
2
6
15
10
9
7
5
3
2
6
1
8
60
min
15
10
9
7
5
3
2
6
1
8
61
15
10
9
7
5
3
1
1
2
6
62
min
15
10
9
7
5
3
1
1
2
2
63
min
15
10
9
7
5
3
1
1
2
2
64
min
15
10
9
7
5
3
1
1
2
2
65
15
10
9
7
5
3
1
1
2
2
66
15
10
9
7
5
3
1
1
2
2
67
15
10
9
7
5
3
1
1
2
2
68
69
Cài đặt
void SelectionSort(int a[],int N )
{
int vtmin;
for (int i=0; i
vtmin = i;
for(int j = i+1; j
if (a[j ] < a[vtmin])
vtmin=j;
}
Hoanvi(a[vtmin], a[i]);
}
}
70
71
72
KIỂM TRA
73
Chèn trực tiếp – insertion sort
Ý tưởng
Cho dãy ban đầu a1 , a2 ,... ,an, ta có thể xem như
đã có đoạn gồm một phần tử a1 đã được sắp, sau
đó thêm a2 vào đoạn a1 sẽ có đoạn a1 a2 được
sắp; tiếp tục thêm a3 vào đoạn a1 a2 để có đoạn
a1 a2 a3 được sắp; tiếp tục cho đến khi thêm
xong aN vào đoạn a1 a2 ...aN-1 sẽ có dãy a1 a2 ....
aN được sắp.
74
15
10
9
7
5
3
2
6
1
8
75
15
10
9
7
5
3
2
6
1
8
76
15
10
9
7
5
3
2
6
1
8
77
15
10
9
7
5
3
2
6
1
8
78
15
10
9
7
5
3
2
6
1
8
79
15
10
9
7
5
3
2
6
1
8
80
15
10
9
7
5
3
2
1
1
8
81
15
10
9
7
5
3
2
1
1
8
82
15
10
9
7
5
3
1
1
2
2
83
?
84
Giải thuật
Bước 1: i = 2;
Bước 2: x = a[i];
85
86
87
88
Nổi bọt – bubble sort
Ý tưởng:
89
10
1
i
5
2
3
7
4
3
5
9
2
6
15
7
1
8
j
90
1
1
i
10
2
3
5
4
7
5
3
9
6
2
7
15
8
j
91
1
1
2
2
i
3
10
5
4
7
5
3
6
9
7
15
8
j
92
1
1
2
2
3
3
i
4
10
5
5
7
6
9
7
15
8
j
93
1
1
2
2
3
3
4
5
i
5
10
7
6
9
7
15
8
j
94
1
1
2
2
3
3
4
5
5
7
i
6
10
9
7
15
8
j
95
1
1
2
2
3
3
4
5
5
7
6
9
i
10
7
15
8
j
96
1
1
2
2
3
3
4
5
Kết
thúc
5
7
6
9
10
7
i
15
8
97
Giải thuật
Bước 1:
98
Cài đặt
void BubleSort(int a[], int N )
{
99
Đánh giá giải thuật
100
101
Quick sort
qui)
x
>x
(x là phần tử trong dãy)
102
i=1, j=8
x
L
R
5
7
10
3
9
2
15
1
i
j
Đoạn 2
Đoạn 1
L=1
R=8
Đoạn cần sắp xếp
103
L=1
R=3
L=4
R=8
i=4, j=8
x
L
R
2
3
1
9
15
7
5
10
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
104
i=5, j=8
x
L
R
2
3
1
5
9
7
15
10
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
105
i=6, j=8
x
L
R
2
3
1
5
7
9
15
10
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
106
x
i=6, j=7
L
R
2
3
1
5
7
9
10
15
i
j
L=6
R=7
L=4
R=5
L=1
R=4
Đoạn cần sắp xếp
107
x
i=4, j=5
L
R
2
3
5
7
1
9
10
15
i
j
L=4
R=5
L=1
R=4
Đoạn cần sắp xếp
108
i=1, j=4
L
R
x
3
2
7
9
10
15
1
5
i
j
Đoạn 2
L=1
R=4
L=3
R=4
Đoạn cần sắp xếp
109
x
i=3, j=4
L
R
2
3
1
5
7
9
10
15
i
j
L=3
R=4
Đoạn cần sắp xếp
110
2
3
1
5
7
9
10
15
Đoạn cần sắp xếp
111
Giải thuật
Cho dãy aL, aL+1, … aR
Bước 1:
Phân hoạch dãy aL … aR thành các dãy con:
Dãy con 1: aL … aj < x
Dãy con 2: aj+1 … ai-1 =x
Dãy con 3: ai … aR > x
Bước 2:
112
Giải thuật phân hoạch dãy aL, aL+1, … aR thành 2 dãy con
Bước 1:
Bước 2:
Bước 3:
113
Cài đặt
void QuickSort(int a[], int left, int right)
{
114
Đánh giá giải thuật
115
![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)
