Giáo trình Cấu trúc dữ liệu và Giải thuật - Chương 7: Sắp xếp - Đỗ Tuấn Anh

(N log N))
{Tuy nhiên, rất khó để tìm được trung vị
Chốt: trung vị của ba khóa
z Thay vào đó, ta chọn chốt là trung vị của ba khóa
{ So sánh ba phần tử: trái nhất, phải nhất và phần tử giữa mảng
{ Đổi chỗ các phần tử để thu được
z A[left] = Nhỏ nhất trong ba phần tử
z A[right] = Lớn nhất trong ba phần tử
z A[center] = Trung vị của ba phần tử
{ Chọn A[center] làm chốt
{ Đổi chỗ A[center] và A[right – 1] để chốt nằm ở vị trí cạnh vị trí
phải nhất (tại sao?)
median3
Chốt: trung vị của 3 khóa
pivot
5 6 4
6
3 12 192 13 6
5 6 4 3 12 192 6 13
A[left] = 2, A[center] = 13, 
A[right] = 6
Đổi chỗ A[center] và A[right]
5 6 4 3 12 192 13
pivot
65 6 4 3 12192 13
Chọn A[center] làm chốt
Đổi chỗ chốt và A[right – 1]
Chú ý: chỉ cần phân đoạn trên A[left + 1, , right – 2]. Tại sao?
Thủ tục Quicksort
Với mảng KT nhỏ
Đệ quy
Chọn chốt
Phân đoạn
Giải thuật phân đoạn
z Chỉ làm việc với chốt là trung 
vị của ba khóa.
{ A[left] = 
pivot
{ Do đó, chỉ cần phân đoạn mảng
A[left + 1, , right – 2]
z j không cần bắt đầu từ phần 
tử đầu
{ vì a[left] <= pivot
z i không cần bắt đầu từ phần 
tử cuối
{ vì a[right-1] = pivot
Quicksort nhanh hơn Mergesort
z Cả Quicksort và MergeSort đều mất O(N log N) 
trong trường hợp trung bình.
z Tại sao quicksort nhanh hơn mergesort?
{Vòng lặp trong gồm một phép tăng dần/giảm dần (1 đơn 
vị, nhanh), một phép kiểm tra điều kiện và một lệnh and a 
jump. 
{Không có thao tác hòa nhập (juggling) như mergesort.
vòng lặp 
trong
Phân tích độ phức tạp
zGiả sử:
{Chốt ngẫu nhiên (không sử dụng phân đoạn
trung vị của ba khóa)
{Không cắt những đoạn có kích thước nhỏ
zThời gian tính
{Lựa chọn chốt: hằng số - O(1)
{Phân đoạn: tuyến tính O(N)
{Thời gian tính của 2 lời gọi đệ quy
zT(N)=T(i)+T(N-i-1)+cN trong đó c là
hằng số
{i: là số phần tử trong đoạn S1
Trường hợp xấu nhất
zTrường hợp nào là xấu nhất?
{Chốt được chọn luôn là phần tử nhỏ nhất
{Việc phân đoạn luôn bị lệch (một đoạn có 0 
phần tử, một đoạn có N-1 phần tử)
Trường hợp tốt nhất
zTrường hợp nào là tốt nhất?
{Việc phân đoạn luôn tạo ra 2 đoạn có kích 
thước cân bằng.
{Chốt được chọn luôn là trung vị của mảng
Trường hợp trung bình
zGiả sử:
{Mỗi lần phân đoạn, kích thước của S1 và S2 là 
tương đối cân bằng
zGiả định này khá đúng khi chọn chốt là
trung vị của ba khóa
zTrong trường hợ trung bình, thời gian tính 
là O(N log N)
5. Sắp xếp vun đống - HeapSort
Đặt vấn đề
3 yêu cầu công việc được gửi tới cho máy in A, B, C.
Số trang: Công việc A – 100 trang
Công việc B – 10 trang
Công việc C – 1 trang
Thời gian đợi nếu sử dụng FIFO:
(100+110+111) / 3 = 107 đơn vị thời gian
Thời gian đợi trung bình nếu lựa chọn công việc ngắn nhất 
trước:
(1+11+111) / 3 = 41 time units
Cần có một hàng đợi cho phép thêm và xóa phần tử nhỏ
nhất
Hàng đợi ưu tiên
Hàng đợi ưu tiên
Priority Queue
3 thao tác:
{Thêm một phần tử theo mức ưu tiên phù hợp.
{Xóa phần tử có mức ưu tiên cao nhất
{Truy cập phần tử có mức ưu tiên cao nhất
(không xóa)
Ứng dụng của Priority Queue
Hệ thống mô phỏng các sự kiện phụ thuộc thời gian (ví dụ: bài
toán giao thông trong sân bay)
Trong phần lớn các ứng dụng, các phần tử của PQ là một cặp khóa-giá trị. 
Mức ưu tiên Nhiệm vụ
Lịch trình các tiến trình của hệ điều hành (chia sẻ thời gian) 
Là cấu trúc dữ liệu quan trọng thực hiện nhiều giải thuật (bài toán
tìm cây khung nhỏ nhất, tìm đường đi ngắn nhất, ...)
Xây dựng Priority Queue
z Danh sách kết nối không có thứ tự
{ Thêm: O(1), xóa: O(N), truy cập: O(N)
zMảng có thứ tự:
{ Thêm: O(N), xóa: O(N), truy cập: O(1)
z Danh sách kết nối có thứ tự:
{ Thêm: O(N), xóa: O(1), truy cập: O(1)
z Cây nhị phân tìm kiếm
{ Thêm, xóa: O(log N) – trung bình, O(N) – xấu nhất; truy
cập: O(1)
Xây dựng PriorityQueue sử dụng Đống
zHỗ trợ các thao tác rất hiệu quả
{Truy cập phần tử nhỏ nhất: O(1)
{Thêm phần tử: O(log N)
{Xóa phần tử nhỏ nhất: O(log N)
Đống (Heap)
Cây nhị phân có độ cao h
♦ đầy đủ ít nhất đến độ sâu h – 1 
♦ có thể thiếu một số nút bên phải nhất ở độ sâu h
Ví dụ
21
18
9 11
5 3 6 2
14
10
7
8
Độ sâu 0
Độ sâu 1
Độ sâu h
Thuộc tính của Heap
Giá trị [NútCha(i)] ≥ Giá trị [i], i > 1
21
18
9 11
5 3 6 2
14
10
7
8
Lưu trữ Heap sử dụng Mảng
21 18 14 9 11 10 8 5 3 6 2 7
Chỉ số 0 1 2 3 4 5 6 7 8 9 10 11 
Dễ dàng truy cập các nút quan hệ cha con:
Nút Cha(i) = (i – 1)/2
Nút Con trái(i) = 2i + 1
Nút Con phải(i) = 2i + 2
nút thứ (i-1)/2
nút thứ i
nút thứ 2i+1 nút thứ (2i+2)
int arr[] = { 21, 18, 14, 9, 11, 10, 8, 5, 3, 6, 2, 7 }; 
int arrSize = sizeof(arr) / sizeof(int);
zLiệu có nên lưu trữ heap bằng danh sách
liên kết?
Các thao tác với Heap
zThêm một phần tử
zXóa phần tử đỉnh
Thêm một phần tử vào đống
zThêm một phần tử mới vào đáy của đống
zVun lại đống từ dưới lên (reheapUp)
reheapUp
void reheapUp(int a[], int k)
{
while(k>0 && a[(k-1)/2] < a[k])
{
exchange(a[k], a[(k-1)/2]);
k = (k-1)/2;
}
}
zĐộ phức tạp của reheapUp = O(logN)
Xóa phần tử đỉnh của đống
zĐổi chỗ phần tử đỉnh bằng phần tử đáy 
cuối cùng
zThiết lập kích thước đống giảm đi một 
phần tử
zXếp lại đống từ trên xuống (reheapDown)
reheapDown
void reheapDown(int a[], int k, int
N){
while(2*k <= N-1){
int j = 2*k+1;
if(j<N-1 && a[j]<a[j+1]) j++;
if(!(a[k]<a[j])) break;
exchange(a[k], a[j]);
k = j;
}
}
zĐộ phức tạp của reheapDown: O(log N)
Sắp xếp vun đống - Heapsort
(1) Tạo đống ban đầu gồm N phần tử
{Phần tử nhỏ nhất (lớn nhất) sẽ nằm tại đỉnh của đống
(2) Thực hiện N-1 lần thao tác xóa phần tử đỉnh
{Các phần tử sẽ được loại ra thứ tự
Bước 1: Tạo đống
z Đầu vào: N phần tử
z Đầu ra: Một đống của N phần tử
Thực hiện: 2 cách
Cách 1: 
- Thêm dần từng phần tử vào đống (sử dụng 
reheapUp)
Cách 2:
z Xem mỗi phần tử mảng như gốc của một đống
con (bỏ qua đống có kích thước 1)
z Sử dụng reheapDown để tạo đống lớn hơn
Thuật toán HeapSort sử dụng cách 2
Heapsort
void heapsort(int a[], int left, int
right)
{
int k, N = right-left+1;
int *pq = a+left-1;
for(k=(N-1)/2; k>=0; k--)
reheapDown(pq, k, N);
while(N > 0){
exchange(pq[0], pq[N-1]);
reheapDown(pq, 0, --N);
}
}
Tạo đống
Xóa lần lượt 
phần tử đỉnh
108
Sau khi tạo đống
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
70
60
12
40
30
8
10
values
70
0
60
1
40
3 
30
4
12
2
8
5
root
10
6
109
Đổi chỗ phần tử đỉnh và phần tử 
đáy
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
70
60
12
40
30
8
10
values
70
0
60
1
40
3 
30
4
12
2
8
5
root
10
6
110
Sau khi đổi chỗ
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
values
10
0
60
1
40
3 
30
4
12
2
8
5
root
70
6
10
60
12
40
30
8
70 Loại ra khỏi đống
111
Vun lại đống
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
values
60
0
40
1
10
3 
30
4
12
2
8
5
root
70
6
60
40
12
10
30
8
70
112
Đổi chỗ phần tử đỉnh
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
values
60
0
40
1
10
3 
30
4
12
2
8
5
root
70
6
60
40
12
10
30
8
70
113
Sau khi đổi chỗ
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
values
8
0
40
1
10
3 
30
4
12
2
root
70
6
8
40
12
10
30
60
70 Loại ra khỏi đống
60
5
114
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
values
40
0
30
1
10
3 
6
4
12
2
root
70
6
40
30
12
10
6
60
70
60
5
Vun lại đống
115
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
values
40
0
30
1
10
3 
6
4
12
2
root
70
6
40
30
12
10
6
60
70
60
5
Đổi chỗ phần tử đỉnh
116
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
values
6
0
30
1
10
3 
12
2
root
70
6
60
5
Sau khi đổi chỗ
40
4
6
30
12
10
40
60
70 Loại ra khỏi đống
117
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
values
30
0
10
1
6
3 
12
2
root
70
6
60
5
40
4
30
10
12
6
40
60
70
Vun lại đống
118
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
values
30
0
10
1
6
3 
12
2
root
70
6
60
5
40
4
30
10
12
6
40
60
70
Đổi chỗ phần tử đỉnh
119
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
values
6
0
10
1
12
2
root
70
6
60
5
40
4
Sau khi đổi chỗ
6
10
12
30
40
60
70
30
3 
Loại ra khỏi đống
120
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
values
12
0
10
1
6
2
root
70
6
60
5
40
4
12
10
6
30
40
60
70
30
3 
Vun lại đống
121
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
values
12
0
10
1
6
2
root
70
6
60
5
40
4
12
10
6
30
40
60
70
30
3 
Đổi chỗ
122
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
values
6
0
10
1
root
70
6
60
5
40
4
30
3 
Sau khi đổi chỗ
Loại ra khỏi đống
12
2
6
10
12
30
40
60
70
123
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
values
10
0
6
1
root
70
6
60
5
40
4
30
3 
12
2
10
6
12
30
40
60
70
Vun lại đống
124
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
values
10
0
6
1
root
70
6
60
5
40
4
30
3 
12
2
10
6
12
30
40
60
70
Đổi chỗ
125
[ 0 ]
[ 1 ]
[ 2 ]
[ 3 ]
[ 4 ]
[ 5 ]
[ 6 ]
values
root
70
6
60
5
40
4
30
3 
12
2
Sau khi đổi chỗ
6
10
12
30
40
60
70
10
1
6
0
Tất cả các phần tử đã được sắp xếp
Heapsort
21
18
9 11
5 3 6 2
14
10
7
8
6
7
18
9 11
5 3 2
14
10
21
8
Heapsort
9
18
11
7
5 3 6 2
14
10
21
8 10
2
11
9 7
5 3 6 18
14
21
8
14
11
9 7
5 3 6 18
10
2
21
8
11
9
6 7
5 3 14 18
10
2
21
8
10
9
6 7
5 11 14 18
8
2
21
3
9
7
6 5
10 11 14 18
8
2
21
3
8
7
6 5
10 11 14 18
3
2
21
9
7
6
2 5
10 11 14 18
3
8
21
9
96
5
2 7
10 11 14 18
3
8
21
5
2
6 7
10 11 14 18
3
8
21
9
3
2
6 7
10 11 14 18
5
8
21
9
2
3
6 7
10 11 14 18
5
8
21
9
2, 3, 5, 6, 7, 8, 9, 10, 11, 14, 18, 21
Độ phức tạp về thời gian
(1) Tạo đống:
{N/2 * O( log N) ⇒ O(N log N)
(2) Thực hiện N-1 lần thao tác xóa phần tử đỉnh
{Mỗi lần xóa mất O(log N) ⇒ O(N log N)
zĐộ phức tạp thời gian: O(N log N)