Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 1
Đỗ Bích Diệp - Khoa CNTT
Cấutrúcdữ liệuvàGiảithuật
Chương VI: Sắpxếp
7 2 ⏐ 9 4 → 2 4 7 9
7 ⏐ 2 → 2 7 9 ⏐ 4 → 4 9
7 → 7 2 → 2 9 → 9 4 → 4
Đỗ Bích Diệp - Khoa CNTT
Chương VI: Sắpxếp
z Nội dung
1. Bài toán sắpxếp
2. Ba phương pháp sắpxếpcơ bản
1. Lựachọn, thêm dầnvàđổichỗ
2. Phân tích, đánh giá
3. Sắpxếpkiểu hòa nhập
4. Sắpxếp nhanh
5. Sắpxếpkiểuvunđống
6. Mộtsố phương pháp sắpxếp đặcbiệt
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 2
Đỗ Bích Diệp - Khoa CNTT
Bài toán Sắpxếp
– Sắpxếplạimộttập các phầntử dữ liệu theo chiều
tăng dầnhoặcgiảmdần
23 78 45 8 32 56
8 23 32 45 78 56
Đỗ Bích Diệp - Khoa CNTT
Bài toán Sắpxếp
– Khóa sắpxếp
z Mộtbộ phậncủabản ghi biểudiễn đốitượng đượcsắp

z Tính ổn định củathuật toán sắpxếp
– Các phầntử có cùng khóa sẽ giữ nguyên thứ tự tương
đốicủa chúng như trướckhisắpxếp
z Tính tạichỗ
– Thuật toán đòi hỏi không gian nhớ phụ là hằng số (không
phụ thuộcvàosố lượng phầntử trong dãy cầnsắp)
78 8 45 8 32 56 8 8 32 45 56 78
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 4
Đỗ Bích Diệp - Khoa CNTT
Bài toán Sắpxếp
– Trong chương này, bài toán sắpxếp được đơn
giảnhóadướidạng như sau
z Đầu vào: Một dãy các số nguyên a
1
, a
2
, …, a
n
z Đầura: Một hoán vị củadãysốđãchotrongđó các giá
trịđượcsắpxếp theo chiềutăng dần
Đỗ Bích Diệp - Khoa CNTT
Ba phương pháp sắpxếpcơ bản
1. Sắpxếpkiểulựachọn (Selection Sort)
2. Sắpxếpkiểu thêm dần (Insertion Sort)
3. Sắpxếpkiểu đổichỗ -Sắpxếpkiểunổibọt
(Buble Sort)
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 5
Đỗ Bích Diệp - Khoa CNTT

min = i;
3. {Chọnphầntử nhỏ nhất}
for j = i+1 to n do
if A[j] < A[min] then
min = j ;
4. {Đổichổ phầntử i và phầntử nhỏ nhất}
T = A[i]; A[i] = A[min]; A[min] = T;
end;
End.
Đỗ Bích Diệp - Khoa CNTT
Sắpxếpkiểulựachọn
– Thờigianthựchiệnthuật toán
z Trường hợptốtnhất:
– Dãy ban đầu đã đượcsắpxếp
– 0 phép đổichỗ, chỉ thựchiện n(n-1)/2 phép so sánh
z Trường hợpxấunhất
– n-1 phép đổichỗ, n(n-1)/2 phép so sánh
–
Độ phứctạpthời gian trung bình O(n
2
)
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 7
Đỗ Bích Diệp - Khoa CNTT
Sắpxếpkiểuthêmdần – Insertion sort
z Ý tưởng:
– Dãy cầnsắp được chia thành 2 phần: mộtlàphần đã
sắp, còn lạilàphầnchưasắp
– Tạimỗilượt, phầntửđầu tiên trong phầnchưasắpsẽ
được “thêm” vào đúng vị trí của nó trong phần đãsắp.

A[j] := val; end;
5. End
Đỗ Bích Diệp - Khoa CNTT
Sắpxếpkiểuthêmdần
– Sắpxếp thêm dầnlàtạichỗ và ổn định
– Thờigianthựchiệngiảithuật
z Trường hợptốtnhất:
– Dãy ban đầu đã đượcsắpxếp
– 0 thựchiệnphépđổichỗ, n-1 phép so sánh
z Trường hợpxấunhất
– n(n-1)/2 phép đổichỗ và so sánh
–
Độ phứctạpthời gian trung bình O(n
2
)
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 9
Đỗ Bích Diệp - Khoa CNTT
Sắpxếpkiểunổibọt
– Ví dụ
z A = {12, 5, 3, 10, 18, 4, 9, 16}
1818181818161616
16161616161899
121212101010184
10101012991018
9999125410
555551253
444444125
333333312
Lượt7Lượt6Lượt5Lượt4Lượt3Lượt2Lượt1

z Trường hợptốtnhất:
– Dãy ban đầu đã đượcsắpxếp
– 0 thựchiệnphépđổichỗ, n(n-1)/2 phép so sánh
z Trường hợpxấunhất
– n(n-1)/2 phép đổichỗ và so sánh
–
Độ phứctạpthời gian trung bình O(n
2
)
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 11
Đỗ Bích Diệp - Khoa CNTT
Sắpxếp Nhanh (Quick Sort)
– Được đưarabởi C. A. Hoare (1962).
– Là phương pháp sắpxếpdựatrênchiếnlượcchiađể trị
z Trường hợpcơ sở: Dãy chỉ có 1 phầntử, dãy đã đượcsắp
z Chia – Pha phân đoạn
– Chọnmộtphầntử trong dãy làm phầntử chốtp
– Chia dãy đã cho thành 3 nhóm : <p ; p ; >=p
z Trị:
– Sắpxếp đượctiếptụcmộtcáchđệ qui với nhóm thứ 1 và nhóm
thứ 3
p
< p
>=
p
Chốt
Đỗ Bích Diệp - Khoa CNTT
Sắpxếp nhanh
Procedure QUICK-SORT(A, left, right)

Sắpxếp nhanh
– Phân đoạn
Chốt
Chốt
Vị trí trái
Vị trí phải
Đỗ Bích Diệp - Khoa CNTT
Sắpxếp nhanh
– Giảithuậtcủa pha phân đoạn
Function PARTITION-LEFT(A, left, right)
{A là mảng cầnsắp, left là chỉ số củaphầntửđầu , right là chỉ số củaphầntử cuối.
Phầntử chốtlàphầntửởđầu danh sách}
1. i:=left + 1; j := right; pivot = left // i là khởi đầucủavị trí trái, j là khởi đầucủa
vị trí phải
2. { Tiếnhànhduyệt, so sánh, đổichỗđểhình thành phân đoạn}
while ( i<=j) do begin
while (A[i] < A[pivot]) do i := i+1;
while (A[j] > A[pivot]) do j:= j-1;
if i < j then begin A[i] <-> A[j]; i := i+1; j := j -1; end
end
3. {Đưachốtvề vị trí thựcgiữa2 phânđoạn, lưuvị trí thự
ccủaphầntử chốt}
k:= j; A[pivot] <-> A[j];
4. Return k
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 14
Đỗ Bích Diệp - Khoa CNTT
Sắpxếp nhanh
78 21 14 97 87 62 74 85 76 45 84 22
78 21 14 97 87 62 74 85 76 45 84 22

Đánh giá giảithuậtSắpxếp nhanh
– Sắpxếp nhanh là tạichỗ nhưng không ổn định
– Thờigianthựchiệngiảithuật
z Trường hợptổng quát
– T(0) = T(1) = c
– Pha phân đoạn đượcthựchiệnbằng việcduyệtdanh
sách ban đầu1 lần Æ ThờigianthựchiệnlàO(n)
– Trong giảithuậtxuấthiện2 lờigọi đệ qui: Giả sử sau khi
phân đoạn, phầntử chốt ở vị trí p thì
T(n) = T(p-1) + T(n-p) + O(n) + O(1)
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 16
Đỗ Bích Diệp - Khoa CNTT
Đánh giá giảithuậtSắpxếp nhanh
z Trường hợpxấunhất:
– Công thức đệ qui: T(n) = T(n-1) + O(n) + O(1)
– Độ phứctạpcủagiảithuậtsắpxếp nhanh là O(n
2
) khi A
vốn đã đượcsắpvàchốt đượcchọnlànútnhỏ nhất
z Trường hợp hoàn hảo:
– Phân đoạncânbằng T(n) = 2 T(n/2) + n
– Độ phứctạp trung bình củagiảithuậtlàO(nlog
2
n)
Đỗ Bích Diệp - Khoa CNTT
Sắpxếpkiểu hòa nhập
z Tương tự như sắpxếp nhanh dựavàocơ chế chia để trị
để thựchiệnsắpxếp.
z Bao gồm3 bước

4. {Trị- Hòa nhậphaidãyđượcsắp}
MERGE(S1,S2, S);
5. Return S;
Đỗ Bích Diệp - Khoa CNTT
Sắpxếpkiểu hòa nhập–Vídụ minh họa
z Chia
7 2 9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7 2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6
7 → 7 2 → 2 9 → 9 4 → 4 3 → 3 8 → 8 6 → 6 1 → 1
7 2 9 4 ⏐ 3 8 6 1 → 1 2 3 4 6 7 8 9
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 18
Đỗ Bích Diệp - Khoa CNTT
Sắpxếpkiểu hòa nhập-Vídụ minh họa
z Lờigọi đệ qui - Chia
7 2 ⏐ 9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7 2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6
7 → 7 2 → 2 9 → 9 4 → 4 3 → 3 8 → 8 6 → 6 1 → 1
7 2 9 4 ⏐ 3 8 6 1 → 1 2 3 4 6 7 8 9
Đỗ Bích Diệp - Khoa CNTT
Sắpxếpkiểu hòa nhập-Vídụ minh họa
z Lờigọi đệ qui - Chia
7 2 ⏐ 9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7 ⏐ 2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6
7 → 7 2 → 2 9 → 9 4 → 4 3 → 3 8 → 8 6 → 6 1 → 1
7 2 9 4 ⏐ 3 8 6 1 → 1 2 3 4 6 7 8 9
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 19
Đỗ Bích Diệp - Khoa CNTT
Sắpxếpkiểu hòa nhập-Vídụ minh họa

Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 21
Đỗ Bích Diệp - Khoa CNTT
Sắpxếpkiểu hòa nhập-Vídụ minh họa
z Hòa nhập
7 2 ⏐ 9 4 → 2 4 7 9 3 8 6 1 → 1 3 8 6
7 ⏐ 2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6
7 → 7 2 → 2 9 → 9 4 → 4 3 → 3 8 → 8 6 → 6 1 → 1
7 2 9 4 ⏐ 3 8 6 1 → 1 2 3 4 6 7 8 9
Đỗ Bích Diệp - Khoa CNTT
Sắpxếpkiểu hòa nhập-Vídụ minh họa
z Tương tự ….
7 2 ⏐ 9 4 → 2 4 7 9 3 8 6 1 → 1 3 6 8
7 ⏐ 2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6
7 → 7 2 → 2 9 → 9 4 → 4 3 → 3 8 → 8 6 → 6 1 → 1
7 2 9 4 ⏐ 3 8 6 1 → 1 2 3 4 6 7 8 9
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 22
Đỗ Bích Diệp - Khoa CNTT
Sắpxếpkiểu hòa nhập-Vídụ minh họa
z Hòa nhậplầncuối
7 2 ⏐ 9 4 → 2 4 7 9 3 8 6 1 → 1 3 6 8
7 ⏐ 2 → 2 7 9 4 → 4 9 3 8 → 3 8 6 1 → 1 6
7 → 7 2 → 2 9 → 9 4 → 4 3 → 3 8 → 8 6 → 6 1 → 1
7 2 9 4 ⏐ 3 8 6 1 → 1 2 3 4 6 7 8 9
Đỗ Bích Diệp - Khoa CNTT
Sắpxếpkiểu hòa nhập
z Giảithuật: Hòa nhập hai dãy đã đượcsắpxếp
Procedure MERGE(A, B, C)
{A, B là hai dãy đãsắpvớisố phầntử lầnlượt là sizea và sizeb, C là dãy hợpnhất
củaA vàB}

– CấutrúcĐống
– Đống là một cây nhị phâncóhaitínhchất
z Là cây nhị phân hoàn chỉnh
z Có thứ tự : mỗi nút đượcgắnvớimộtgiátrị số tự
nhiên, sao cho giá trị của nút cha bao giờ cũng lớn
hơngiátrị của nút con (Max Heap)
87
65
33
45 23 18 5
27 9 12
Đỗ Bích Diệp - Khoa CNTT
Sắpxếpkiểuvunđống
– Đống đượclưutrữ trong máy tính dướidạng mộtvector
lưutrữ
V[10]V[9]V[8]V[7]V[6]V[5]V[4]V[3]V[2]V[1]
129275182345336587
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp -Khoa CNTT - ĐHBKHN 25
Đỗ Bích Diệp - Khoa CNTT
Sắpxếpkiểuvunđống
z Phép tạo đống
– Dãy số cầnsắp đượccoilàdãycácphầntử củamộtcâynhị
phân hoàn chỉnh đượclưutrữ kế tiếp
z Dãy số A: {31, 54, 21, 11, 79, 47, 28, 87, 69, 65, 51}
z Vector lưutrữ
V[1]
31
V[2]
54

5
6
7
8
9
10
11