Bài giảng Chương 5: Sorting | Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa Hà Nội

Bài giảng Chương 5: Sorting | Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa Hà Nội. Tài liệu được biên soạn giúp các bạn tham khảo, củng cố kiến thức, ôn tập và đạt kết quả cao kết thúc học phần. Mời các bạn đọc đón xem!

29 15 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Cấu trúc dữ liệu và giải thuật (ET2100)

Trường: Đại học Bách Khoa Hà Nội

Thông tin:

94 trang 6 tháng trước

Tác giả:

Profile Thùy Dương
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Chương 5
Sắp xếp (Sorting)
William A. Martin, Sorting. ACM Computing Surveys, Vol. 3, Nr 4, Dec 1971, pp. 147-174.
" ...The bibliography appearing at the end of this article lists 37 sorting algorithms
and 100 books and papers on sorting published in the last 20 years...
Suggestions are made for choosing the algorithm best suited to a given situation."
D. Knuth: 40% thời gian hoạt động của các máy tính là dành cho sắp xếp!
Heap Sort Quick Sort
NỘI DUNG
5.1. Bài toán sắp xếp
5.2. Ba thuật toán sắp xếp cơ bản
5.3. Sắp xếp trộn (Merge Sort)
5.4. Sắp xếp nhanh (Quick Sort)
5.5. Sắp xếp vun đống (Heap Sort)
5.6. Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp
5.7. Các phương pháp sắp xếp đặc biệt
2
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
5.1. Bài toán sắp xếp
• 5.1.1. Bài toán sắp xếp
• 5.1.2. Giới thiệu sơ lược về các thuật toán sắp xếp
3
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
5.1.1. Bài toán sắp xếp
• Sắp xếp (Sorting)
– Là quá trình tổ chức lại họ các dữ liệu theo thứ tự giảm dần
hoặc tăng dần (ascending or descending order)
• Dữ liệu cần sắp xếp có thể là
– Số nguyên (Integers)
– Xâu ký tự (Character strings)
– Đối tượng (Objects)
• Khoá sắp xếp (Sort key)
– Là bộ phận của bản ghi xác định thứ tự sắp xếp của bản ghi
trong họ các bản ghi.
– Ta cần sắp xếp các bản ghi theo thứ tự của các khoá.
4
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
5.1.1. Bài toán sắp xếp
• Chú ý:
• Việc sắp xếp tiến hành trực tiếp trên bản ghi đòi hỏi di chuyển
vị trí bản ghi, có thể là thao tác rất tốn kém.
• Vì vậy, người ta thường xây dựng bảng khoá gồm các bản ghi
chỉ có hai trường là (khoá, con trỏ)
– trường "khoá" chứa giá trị khoá,
– trường "con trỏ" để ghi địa chỉ của bản ghi tương ứng.
• Việc sắp xếp theo khoá trên bảng khoá không làm thay đổi
bảng chính, nhưng trình tự các bản ghi trong bảng khoá cho
phép xác định trình tự các bản ghi trong bảng chính.
5
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
6
5.1.1. Bài toán sắp xếp
Ta có thể hạn chế xét bài toán sắp xếp dưới dạng sau đây:
Input: Dãy = ( , , …, )n số A a
1
a
2
a
n
Output: Một hoán vị (sắp xếp lại) ( ) của dãy số đã cho a'
1
,…, a’
n
thoả mãn
a’ a’≤ … ≤
• Ứng dụng của sắp xếp:
– Quản trị cơ sở dữ liệu (Database management);
– Khoa học và kỹ thuật (Science and engineering);
– Các thuật toán lập lịch (Scheduling algorithms),
• ví dụ thiết kế chương trình dịch, truyền thông,... (compiler design,
telecommunication);
– Máy tìm kiếm web (Web search engine);
– và nhiều ứng dụng khác…
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
5.1.1. Bài toán sắp xếp
• Các loại thuật toán sắp xếp
– Sắp xếp trong (internal sort)
• Đòi hỏi họ dữ liệu được đưa toàn bộ vào bộ nhớ trong của máy tính
– Sắp xếp ngoài (external sort)
• Họ dữ liệu không thể cùng lúc đưa toàn bộ vào bộ nhớ trong,
nhưng có thể đọc vào từng bộ phận từ bộ nhớ ngoài
• Các đặc trưng của một thuật toán :sắp xếp
– Tại chỗ (in place): nếu không gian nhớ phụ mà thuật toán làđòi hỏi
O(1), nghĩa là bị chặn bởi hằng số không phụ thuộc vào độ dài của dãy
cần sắp xếp.
– Ổn định (stable): Nếu các phần tử có cùng giá trị vẫn giữ nguyên thứ tự
tương đối của chúng như trước khi sắp xếp.
7
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
5.1.1. Bài toán sắp xếp
• Có hai phép toán cơ bản mà thuật toán sắp xếp thường phải sử dụng:
– Đổi chỗ (Swap): Thời gian thực hiện là O(1)
void swap( datatype &a, datatype &b){
datatype temp = a; //datatype-kiểu dữ liệu của phần tử
a = b;
b = temp;
}
– So sánh: Compare(a, b) trả lại true nếu a đi trước b trong thứ tự cần
sắp xếp và false nếu trái lại.
• Các thuật toán chỉ sử dụng phép toán so sánh để xác định thứ tự giữa
hai phần tử được gọi là thuật toán sử dụng phép so sánh
(Comparison-based sorting algorithm)
8
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
9
5.1.2. Giới thiệu sơ lược về các thuật toán sắp xếp
Simple
algorithms:
O( )
n
2
Fancier
algorithms:
O(n log )n
Comparison
lower bound:
(n log )n
Specialized
algorithms:
O( )n
Handling
huge data
sets
Insertion sort
Selection sort
Bubble sort
Shell sort
…
Heap sort
Merge sort
Quick sort
…
Bucket sort
Radix sort
External
sorting
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Các thuật toán sắp xếp dựa trên phép so sánh
Name Average Worst Memory Stable Method
Bubble sort — O(n²) O(1) Yes Exchanging
Cocktail sort — O(n²) O(1) Yes Exchanging
Comb sort O(n log logn) O(n n) O(1) No Exchanging
Gnome sort — O(n²) O(1) Yes Exchanging
Selection sort O(n²) O(n²) O(1) No Selection
Insertion sort tion
Shell sort tion
Binary tree sort O(n nlog n) O( log n) O(n) Yes Insertion
Library sort O(n log n) O(n²) O(n) Yes Insertion
Merge sort O(n log logn) O(n n) O(n) Yes Merging
In-place merge sort O(n log logn) O(n n) O(1) Yes Merging
Heapsort O(n log logn) O(n n) O(1) No Selection
Smoothsort — O(n log n) O(1) No Selection
Quicksort O(n log n) O(n²) O(log n) No Partitioning
Introsort O(n log logn) O(n n) O(log n) No Hybrid
Patience sorting — O(n²) O(n) No Insertion
10
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Các thuật toán sắp xếp không dựa trên phép so sánh
Name Average Worst Memory Stable n << 2 ?
k
Pigeonhole sort O(
n+2 +2
k
) O(n
k
) O(2
k
) Yes Yes
Bucket sort O(n·k) O(n²·k) O(n·k) Yes No
Counting sort O(
n+2 +2 +2
k
) O(n
k
) O(n
k
) Yes Yes
LSD Radix sort O(n·k/ /s) O(n·k s) O(n) Yes No
MSD Radix sort O(
n·k/ ·( / )·2 / )·2s) O(n k s
s
) O((k s
s
) No No
Spreadsort O(
n·k/log( O(n))
O( · ( -log( ))n k n
0.5
)
n) No No
11
Các thông số trong bảng
n - số phần tử cần sắp xếp
k - kích thước mỗi phần tử
s - kích thước bộ phận được sử dụng khi cài đặt.
Nhiều thuật toán được xây dựng dựa trên giả thiết là n << 2 .
k
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
NỘI DUNG
5.1. Bài toán sắp xếp
5.2. Ba thuật toán sắp xếp cơ bản
5.3. Sắp xếp trộn (Merge Sort)
5.4. Sắp xếp nhanh (Quick Sort)
5.5. Sắp xếp vun đống (Heap Sort)
5.6. Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp
5.7. Các phương pháp sắp xếp đặc biệt
12
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
5.2. Ba thuật toán sắp xếp cơ bản
• 5.2.1. Sắp xếp chèn (Insertion Sort)
• 5.2.2. Sắp xếp lựa chọn (Selection Sort)
• 5.2.3. Sắp xếp nổi bọt (Bubble Sort)
13
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
14
Phỏng theo cách làm của người
chơi bài khi cần "chèn" thêm một
con bài vào bộ bài đã được sắp
Để chèn 12, ta cần tạo chỗ cho
nó bởi việc dịch chuyển đầu tiên
là 36 và sau đó là 24.
5.2.1. Sắp xếp chèn (Insertion Sort)
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
15
Sắp xếp chèn (Insertion Sort)
Phỏng theo cách làm của người
chơi bài khi cần "chèn" thêm một
con bài vào bộ bài đã được sắp
xếp trên tay.
Để chèn , ta cần tạo chỗ cho 12
nó bởi việc dịch chuyển đầu tiên
là 36 và sau đó là 24.
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
16
Sắp xếp chèn (Insertion Sort)
Phỏng theo cách làm của người
chơi bài khi cần "chèn" thêm một
con bài vào bộ bài đã được sắp
Để chèn 12, ta cần tạo chỗ cho
nó bởi việc dịch chuyển đầu tiên
là 36 và sau đó là 24.
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
17
Sắp xếp chèn (Insertion Sort)
Phỏng theo cách làm của người
chơi bài khi cần "chèn" thêm một
con bài vào bộ bài đã được sắp
xếp trên tay.
Để chèn 12, ta cần tạo chỗ cho
nó bởi việc dịch chuyển đầu tiên
là 36 và sau đó là 24.
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
18
Don’t start coding
You must design a working algorithm first.
CuuDuongThanCong.com
5.2.1. Sắp xếp chèn (Insertion Sort)
• Thuật toán:
– Tại bước , đưa phần tử thứ trong mảng đã cho vào đúng k = 1, 2, ..., n k
vị trí trong dãy gồm k phần tử đầu tiên.
– Kết quả là sau bước k, k phần tử đầu tiên là được sắp thứ tự.
void insertionSort(int a[], int array_size) {
int i, j, last;
for (i=1; i < array_size; i++) {
last = a[i];
j = i;
while ((j > 0) && (a[j-1] > last)) {
a[j] = a[j-1];
j = j - 1; }
a[j] = last;
} // end for
} // end of isort
19
Giải thích:
• Ở đầu lần lặp i của vòng
"for" ngoài, dữ liệu từ a[0]
đến a[ 1] là được sắp xếp. i-
• Vòng lặp "while" tìm vị trí
cho phần tử tiếp theo (last
=a[i]) trong dãy gồm i phần
tử đầu tiên.
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Ví dụ Insertion sort (1)
20
1 2 3 8 7 9 10 12 23 18 15 16 17 14
1 2 3 7 8 9 10 12 23 18 15 16 17 14
18 23 15 16 17 14
15 18 23 16 17 14
15 18 16 23 17 14
1 2 3 7 8 9 10 12
1 2
1 2 3 7 8 9 10 12
1 2 3 7 8 9 10 12
15 16 18 23 17 141 2 3 7 8 9 10 12
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Ví dụ Insertion sort (1)
21
15 16 18 17 23 141 2 3 7 8 9 10 12
15 16 17 18 23 141 2 3 7 8 9 10 12
15 16 17 18 14 231 2 3 7 8 9 10 12
15 16 17 14 18 231 2 3 7 8 9 10 12
15 16 14 17 18 231 2 3 7 8 9 10 12
15 14 16 17 18 231 2 3 7 8 9 10 12
14 15 16 17 18 231 2 3 7 8 9 10 12
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
13 phép đổi chỗ:
20 phép so sánh:
Ví dụ: Insertion Sort (2)
22
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
23
Các đặc tính của Insertion Sort
• Sắp xếp chèn là tại chỗ và ổn định (In place and Stable)
• Phân tích thời gian tính của thuật toán
– Best Case: 0 hoán đổi, n-1 so sánh (khi dãy đầu vào là đã được sắp)
– Worst Case: n
2
/2 hoán đổi và so sánh (khi dãy đầu vào có thứ tự
ngược lại với thứ tự cần sắp xếp)
– Average Case: n
2
/4 hoán đổi và so sánh
• Thuật toán này có thời gian tính trong tình huống tốt nhất là
tốt nhất
• Là thuật toán sắp xếp tốt đối với dãy đã gần được sắp xếp
– Nghĩa là mỗi phần tử đã đứng ở vị trí rất gần vị trí trong thứ tự cần
sắp xếp
Thử nghiệm insertion sort
#include <stdlib.h>
#include <stdio.h>
void insertionSort(int a[], int array_size);
int a[1000];
int main() {
int i, N;
printf("\nGive n = "); scanf("%i", &N);
//seed rand
srand(getpid());
//fill array with random integers
for (i = 0; i < N; i++)
a[i] = rand();
//perform insertion sort on array
insertionSort(a, N);
printf("\nOrdered sequence:\n");
for (i = 0; i < N; i++)
printf("%8i", a[i]);
getch();
}
24
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
5.2.2. Sắp xếp chọn (Selection Sort)
• Thuật toán
– Tìm phần tử nhỏ nhất đưa vào vị trí 1
– Tìm phần tử nhỏ tiếp theo đưa vào vị trí 2
– Tìm phần tử nhỏ tiếp theo đưa vào vị trí 3
– …
void selectionSort(int a[], int n){
int i, j, min, temp;
for (i = 0; i < n-1; i++) {
min = i;
for (j = i+1; j < n; j++){
if (a[j] < a[min]) min = j;
}
swap(a[i], a[min]);
}
}
25
void swap(int &a,int &b)
{
int temp = a;
a = b;
b = temp;
}
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Selection Sort
template <class Elem, class Comp>
void selection_sort(Elem A[], int n) {
for (int i=0; i<n-1; i++) {
int lowindex = i; // Remember its index
for (int j=n-1; j>i; j--) // Find least
if (Comp::lt(A[j], A[lowindex]))
lowin
swap(A, i, lowindex);
}
}
• Best case: 0 đổi chỗ (n-1 như trong đoạn mã), n
2
/2 so sánh.
• Worst case: n - 1 đổi chỗ và n
2
/2 so sánh.
• Average case: O(n) đổi chỗ và n
2
/2 so sánh.
• Ưu điểm nổi bật của sắp xếp chọn là số phép đổi chỗ là ít. Điều này là có ý
nghĩa nếu như việc đổi chỗ là tốn kém.
26
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Ví dụ: Selection Sort
27
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
5.2.3. Sắp xếp nổi bọt - Bubble Sort
• Bubble sort là phương pháp sắp xếp đơn giản thường được sử dụng
như ví dụ minh hoạ cho các giáo trình nhập môn lập trình.
• Bắt đầu từ đầu dãy, thuật toán tiến hành so sánh mỗi phần tử với
phần tử đi sau nó và thực hiện đổi chỗ, nếu đúngchúng không theo
thứ tự. Quá trình này sẽ được lặp lại cho đến khi gặp lần duyệt từ
đầu dãy đến à tất cả
các phần tử đã đứng đúng vị trí). Cách làm này đã đẩy phần tử lớn
nhất xuống cuối dãy, trong khi đó những phần tử có giá trị nhỏ hơn
được dịch chuyển về đầu dãy.
• Mặc dù thuật toán này là đơn giản, nhưng nó là thuật toán kém hiệu
quả nhất trong ba thuật toán cơ bản trình bày trong mục này. Vì thế
ngoài mục đích giảng dạy, Sắp xếp nổi bọt rất ít khi được sử dụng.
• Giáo sư Owen Astrachan (Computer Science Department, Duke
University) còn đề nghị là không nên giảng dạy về thuật toán này.
28
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
5.2.3. Sắp xếp nổi bọt - Bubble Sort
void bubbleSort(int a[], int n){
int i, j;
for (i = (n-1); i >= 0; i--) {
for (j = 1; j <= i; j++){
if (a[j-1] > a[j])
swap(a[j-1],a[j]);
}
}
}
• Best case: 0 đổi chỗ, n
2
/2 so sánh.
• Worst case: n
2
/2 đổi chỗ và so sánh.
• Average case: /2 so sánh.n
2
/4 đổi chỗ và n
2
void swap(int &a,int &b)
{
int temp = a;
a = b;
b = temp;
}
29
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Ví dụ: Bubble Sort
Chú ý:
– Các phần tử được đánh chỉ số bắt đầu từ 0.
– n=5
7 4 1 9 2
4 7 1 9 2
4 1 7 9 2
4 1 7 9
4 1 7 2 9
4 1 7 2 9
1 4 7 2 9
1 4 7 2 9
1 4 2 7 9
1 4 2 7 9
1 2 4 7 9
i = 4
i = 3 i = 2
30
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
So sánh ba thuật toán cơ bản
31
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Tổng kết 3 thuật toán sắp xếp cơ bản
Insertion Bubble Selection
Comparisons:
Best Case )( (n) n
2
) (n
2
Average
Worst Case )(n
2
) (n
2
) (n
2
Swaps
Best Case 0 0 )(n
Average Case )(n
2
) (n
2
) (n
Worst Case )(n
2
) (n
2
) (n
32
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
NỘI DUNG
5.1. Bài toán sắp xếp
5.2. Ba thuật toán sắp xếp cơ bản
5.3. Sắp xếp trộn (Merge Sort)
5.4. Sắp xếp nhanh (Quick Sort)
5.5. Sắp xếp vun đống (Heap Sort)
5.6. Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp
5.7. Các phương pháp sắp xếp đặc biệt
33
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Sắp xếp trộn (Merge Sort)
34
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Hoà nhập hai dòng xe theo Khoá
[độ liều lĩnh của lái xe].
Lái xe liều lĩnh hơn sẽ vào trước!
CuuDuongThanCong.com
Sắp xếp trộn (Merge Sort)
• Bài toán: Cần sắp xếp mảng A[1 .. n]:
• Chia (Divide)
– Chia dãy gồm phần tử cần sắp xếp ra thành 2 dãy, mỗi dãy có n n/2
phần tử
• Trị (Conquer)
– Sắp xếp mỗi dãy con một cách đệ qui sử dụng sắp xếp trộn
– Khi dãy chỉ còn một phần tử thì trả lại phần tử này
• Tổ hợp (Combine)
– Trộn (Merge) hai dãy con được sắp xếp để thu được dãy được sắp xếp
gồm tất cả các phần tử của cả hai dãy con
35
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Merge Sort
MERGE-SORT(A, p, r)
if p < r Kiểm tra điều kiện neo
then q (p←
MERGE-SORT(A, p, q) Trị (Conquer)
MERGE-SORT(A, q + 1, r) Trị (Conquer)
MERGE(A, p, q, r) Tổ hợp (Combine)
endif
• Lệnh gọi thực hiện thuật toán: MERGE-SORT(A, 1, n)
1 2 3 4 5 6 7 8
6231742
5
p
r
q
36
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Trộn (Merge) - Pseudocode
MERGE(A, p, q, r)
1. Tính n
1
và n
2
2. Sao và n
1
phần tử đầu tiên vào L[1 . . n
1
] n
2
phần tử tiếp theo vào R[1 . . n ]
2
3. L[n
1
+ 1] + 1] ← ; R[n
2
←
4. i 1← 1; j ←
5. for to k ← p r do
6. if L[ i ] ≤ R[ j ]
7. then A[k] L[ i ]←
8. i i + 1←
9. else A[k] R[ j ]←
10. j j + 1←
p q
7542
6321
rq + 1
L
R
1 2 3 4 5 6 7 8
6321754
2
p
r
q
n
1
n
2
37
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Thời gian tính của trộn
• Khởi tạo (tạo hai mảng con tạm thời L và R):
– (n (n)
1
+ n ) =
2
• Đưa các phần tử vào mảng kết quả (vòng lặp cuối cùng):for
– n lần lặp,
• Tổng cộng thời gian của trộn là:
– (n)
38
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Thời gian tính của sắp xếp trộn
MERGE-SORT Running Time
• Chia:
– tính và q như là giá trị trung bình của p r: D(n) = (1)
• Trị:
– giải đệ qui 2 bài toán con, mỗi bài toán kích thước n/2 2T (n/2)
• Tổ hợp:
– TRỘN (MERGE) trên các mảng con cỡ phần tử đòi hỏi thời gian n (n)
C(n) = (n)
(1) nếu n =1
T(n) = 2T(n/2) + (n) nếu n > 1
– Suy ra theo định lý thợ: T n( ) =
(n log )n
39
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Ví dụ: Sắp xếp trộn
40
61354928
1 2 3 4 5 6 7 8
6135
5 6 7 8
4928
1 2 3 4
Divide
49
3 4
28
1 2
61
7 8
35
5 6
Divide
21
28
49
35 61
1 phần tử
94
3 4
82
1 2
61
7 8
53
5 6
Merge
6531
5 6 7 8
9842
1 2 3 4
Merge
98654321
1 2 3 4 5 6 7 8
Kết quả:
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Cài đặt merge: Trộn A[first..mid] và A[mid+1.. last]
void merge(DataType A[], int first, int mid, int last){
DataType tempA[MAX_SIZE]; // mảng phụ
int first1 = first; int last1 = mid;
int first2 = mid + 1; int last2 = last; int index = first1;
for (; (first1 <= last1) && (first2 <= last2); ++index){
if (A[first1] < A[first2]) {
tempA[index] = A[first1]; ++first1;}
else
{ tempA[index] = A[first2]; ++first2;} }
for (; first1 <= last1; ++first1, ++index)
tempA[index] = A[first1]; // sao nốt dãy con 1
for (; first2 <= last2; ++first2, ++index)
tempA[index] = A[first2]; // sao nốt dãy con 2
for (index = first; index <= last; ++index)
A[index] = tempA[index]; // sao trả mảng kết quả
} // end merge
Chú ý: DataType: kiểu dữ liệu phần tử mảng.
41
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Cài đặt mergesort
void mergesort(DataType A[], int first, int last)
{
if (first < last)
{ // chia thành hai dãy con
int mid = (first + last)/2; // chỉ số điểm giữa
// sắp xếp dãy con trái A[first..mid]
mergeso
// sắp xếp dãy con phải A[mid+1..last]
mergesort(A, mid+1, last);
// Trộn hai dãy con
merge(A, first, mid, last);
} // end if
} // end mergesort
Lệnh gọi thực hiện mergesort(A,0,n-1)
42
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
NỘI DUNG
5.1. Bài toán sắp xếp
5.2. Ba thuật toán sắp xếp cơ bản
5.3. Sắp xếp trộn (Merge Sort)
5.4. Sắp xếp nhanh (Quick Sort)
5.5. Sắp xếp vun đống (Heap Sort)
5.6. Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp
5.7. Các phương pháp sắp xếp đặc biệt
43
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
5.4. Sắp xếp nhanh (Quick Sort)
• 5.4.1. Sơ đồ tổng quát
• 5.4.2. Phép phân đoạn
• 5.4.3. Độ phức tạp của sắp xếp nhanh
44
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
5.4.1. Sơ đồ Quick Sort
• Thuật toán sắp xếp nhanh được phát triển bởi
Hoare năm 1960 khi ông đang làm việc cho
hãng máy tính nhỏ Elliott Brothers ở Anh.
• Theo thống kê tính toán, Quick sort (sẽ viết tắt là
QS) là thuật toán sắp xếp nhanh nhất hiện nay.
• QS có thời gian tính trung bình là O(n log n), tuy
nhiên thời gian tính tồi nhất của nó lại là O(n
2
).
• QS là thuật toán nósắp xếp tại chỗ, nhưng
không có tính .ổn định
• QS khá đơn giản về lý thuyết, nhưng lại không
dễ cài đặt .
45
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
đường nằm ngang cho biết pivot
C.A.R. Hoare
January 11, 1934
ACM Turing Award, 1980
Photo: 2006
10 Algorithms in 20th Century
Science, Vol. 287, No. 5454, p. 799, February 2000
Computing in Science & Engineering, January/February 2000
1946: The Metropolis Algorithm for Monte Carlo
1947: Simplex Method for Linear Programming // Tính toán khoa học
1950: Krylov Subspace Iteration Method
1951: The Dec
1957: The Fortran Optimizing Compiler
1959: QR Algorithm for Computing Eigenvalues
1962: Quicksort Algorithms for Sorting
1965: Fast Fourier Transform // Xử lý ảnh
1977: Integer Relation Detection
1987: Fast Multipole Method
có ảnh hưởng sâu rộng đến việc phát triển và ứng dụng của khoa
học kỹ thuật …
CuuDuongThanCong.com
5.4.1. Sơ đồ Quick Sort
• Quick sort là thuật toán sắp xếp được phát triển dựa trên kỹ thuật chia .để trị
• Thuật toán có thể mô tả đệ qui như sau (có dạng tương tự như merge sort):
1. Neo đệ qui (Base case). Nếu dãy chỉ còn không quá một phần tử thì nó là dãy
được sắp và trả lại ngay dãy này mà không phải làm gì cả.
2. Chia (Divide):
• Chọn một phần tử trong dãy và gọi nó là phần tử chốt p (pivot).
• Chia dãy đã cho ra thành hai dãy con: Dãy con trái (L) gồm những phần tử
không lớn hơn phần tử chốt, còn dãy con phải (R) gồm các phần tử không
nhỏ hơn phần tử chốt. Thao tác này được gọi là "Phân đoạn" (Partition).
3. Trị (Conquer): Lặp lại một cách đệ qui thuật toán đối với hai dãy con L và .R
4. Tổng hợp (Combine): Dãy được sắp xếp là L p R.
• Ngược lại với Merge Sort, trong QS thao tác chia là phức tạp, nhưng thao
tác .tổng hợp lại đơn giản
• Điểm mấu chốt để thực hiện QS chính là thao tác chia. Phụ thuộc vào thuật
toán thực hiện thao tác này mà ta có các .dạng QS cụ thể
47
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Các bước của QuickSort
48
13
81
92
43
65
31 57
26
75
0
A
Chọn pivot
13
92
5726
0
L R
Phân đoạn A
13 4331 57260
L
81 927565
R
QuickSort(L) và
QuickSort(R)
13 4331 57260 65 81 9275
A
OK! A được sắp
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Sơ đồ tổng quát của QS
• Sơ đồ tổng quát của QS có thể mô tả như sau:
Quick-Sort(A, Left, Right)
1. if {(Left < Right )
2. Pivot = Partition(A, Left Right, );
3. Quick-Sort(A, , Left Pivot –1);
4. Quick-Sort(A, +1, Pivot Right); }
• Hàm Partition( , A Left Right, ) thực hiện chia A Left..Right[ ] thành hai
đoạn A[Left..Pivot –1 ] và A Pivot Right[ +1.. ] sao cho:
• Các phần tử trong A[ [Left..Pivot –1] là nhỏ hơn hoặc bằng A Pivot]
• Các phần tử trong A[Pivot Right+1.. ] là lớn hơn hoặc bằng A[Pivot].
• Lệnh gọi thực hiện thuật toán Quick-Sort(A, 1, )n
49
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Sơ đồ tổng quát của QS
• Knuth cho rằng khi dãy con chỉ còn một số lượng không lớn phần tử
(theo ông là không quá 9 phần tử) thì ta nên sử dụng các thuật toán
đơn giản để sắp xếp dãy này, chứ không nên tiếp tục chia nhỏ. Thuật
toán trong tình huống như vậy có thể mô tả như sau:
Quick-Sort(A, L
1. if (Right - Left < n
0
)
2. Insertion_sort(A, Left Right, );
3. else {
4. Pivot = Partition(A, Left Right, );
5. Quick-Sort(A, , Left Pivot –1);
6. Quick-Sort(A, +1, Pivot Right); }
50
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
5.4.2. Thao tác chia
• Trong QS thao tác chia bao gồm 2 công việc:
– Chọn phần tử chốt p.
– Phân đoạn: Chia dãy đã cho ra thành hai dãy con: Dãy con trái (L) gồm
những phần tử không lớn hơn phần tử chốt, còn dãy con phải (R) gồm
các phần tử không nhỏ hơn phần tử chốt.
• Thao tác phân đoạn có thể cài đặt (tại chỗ) với thời gian (n).
• Hiệu quả của thuật toán phụ thuộc rất nhiều vào việc phần tử nào
được chọn làm phần tử chốt:
– Thời gian tính trong tình huống tồi nhất của QS là O(n
2
). Trường hợp
xấu nhất xảy ra khi danh sách là đã được sắp xếp và phần tử chốt được
chọn là phần tử trái nhất của dãy.
– Nếu phần tử chốt được chọn ngẫu nhiên, thì QS có độ phức tạp tính
toán là O(n log n).
51
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Chọn phần tử chốt
• Việc chọn phần tử chốt có vai trò quyết định đối với hiệu quả
của thuật toán. Tốt nhất nếu chọn được phần tử chốt là phần tử
đứng giữa trong danh sách được sắp xếp (ta gọi phần tử như
vậy là trung vị/median). Khi đó, sau log
2
n lần phân đoạn ta sẽ
đạt tới danh sách với kích thước bằng 1. Tuy nhiên, điều đó rất
khó thực hi hần tử
chốt sau đây:
– Chọn phần tử trái nhất (đứng đầu àm phần tử chốt. ) l
– Chọn phần tử phải nhất (đứng cuối) làm phần tử chốt.
– Chọn phần tử đứng giữa danh sách làm phần tử chốt.
– Chọn phần tử trung vị trong 3 phần tử đứng đầu, đứng giữa và đứng
cuối làm phần tử chốt (Knuth).
– Chọn ngẫu nhiên một phần tử làm phần tử chốt.
52
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Thuật toán phân đoạn
• Ta xây dựng hàm làm việc sau: Partition(a, left, right)
• Input: Mảng a[left .. right].
• Output: Phân bố lại các phần tử của mảng đầu vào và trả lại
chỉ số thoả mãn:jpivot
– a[jpivot] chứa giá trị ban đầu của a[left],
– a[i] ≤ ], với mọi ≤ a[jpivot left i < , pivot
– a[j] ≥ ]), với mọi a[jpivot pivot < j ≤ right.
53
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Phần tử chốt là phần tử đứng đầu
Partition(a, left, right)
i j= left; = right + 1; pivot = a[ ];left
while i < j do
i i= + 1;
while i i right and a[i] < pivot do = i + 1;
j j= – 1;
while j left and a[j] > pivot do j = j – 1;
swap(a[ ]);i] , a[j
swap(a[i], a[ ]); swap(a[ ], a[j j left]);
return j;
54
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
i
j
Sau khi chọn dịch các con trỏ từ đầu và cuối mảng pivot, i và j
và đổi chỗ cặp phần tử thoả mãn a[i] > pivot và a[ ] < j pivot
pivot được chọn là
phần tử đứng đầu
j là chỉ số (jpivot) cần trả lại,
do đó cần đổi chỗ a[left] và a[j]
CuuDuongThanCong.com
Ví dụ
Khoá (Key): 9 1 11 17 13 18 4 12 14 5
> > <
lần 1while: 9 1 5 17 13 18 4 12 14 11
> < < <
lần 2while: 9 1 5 4 13 18 17 12 14 11
< >< <
lần 3while: 9 1 5 13 4 18 17 12 14 11
2 lần đổi chỗ: 4 1 5 9 13 18 17 12 14 11
Vị trí: 0 1 2 3 4 5 6 7 8 9
56
Ví dụ: Phân đoạn với pivot là phần tử đứng đầu
7 2 8 3 5 9 6
Chọn pivot:
Phân đoạn: Con trỏ 7 2 8 3 5 9 6
< >
7 2 8 3 5 9 6
2 nhỏ hơn pivot
7 2 6 3 5 9 8
< >
đổi chỗ 6, 8
7 2 6 3 5 9 8
3,5 nhỏ hơn 9 lớn hơn
7 2 6 3 5 9 8
Kết thúc phân đoạn
8973625
Đưa pivot vào vị trí
CuuDuongThanCong.com
Phần tử chốt là phần tử đứng giữa
PartitionMid(a, left, right);
i = left; j = right; pivot left + right= a[( )/2];
repeat
while a[i] < pivot do i = + 1;i
while pivot < a[j] do j = j - 1;
if i <= j
swap(a[i], a[j]);
i = i j = j+ 1; - 1;
until i > j;
return j;
• Cài đặt thuật toán phân đoạn trong đó pivot được chọn là phần tử đứng
giữa (Đây cũng là cách cài đặt mà TURBO C lựa chọn).
57
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
pivot được chọn là
phần tử đứng giữa
Phần tử chốt là phần tử đứng cuối
int PartitionR(int a[], int p, int r) {
int x = a[r];
int j = p - 1;
for (int i = p; i < r; i++) {
if (x >= a[i])
{ j = j + 1
}
a[r] = a[j + 1]; a[j + 1] = x;
return (j + 1);
}
void quickSort(int int inta[], p, r) {
if (p < r) {
int q = PartitionR(a, p, r);
quickSort(a, p, q - 1);
quickSort(a, q + 1, r);
}
58
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Cài đặt QUICK SORT
int Partition(int a[], int left, int right) {
int i, j, pivot;
i = left; j = right + 1; pivot = a[left];
while (i < j) {
i = i + 1; while ((i <= right)&&(a[i] < pivot)) i++;
j--; while ((j >= left)&& (a[j] > pivot)) j--;
swap(a[i] , a[j]); }
swap(a[i], a[j]); swap(a[j], a[left]);
return j;
}
void quick_sort(int a[], int left, int right) {
int pivot;
if (left < right) {
pivot = Partition(a, left, right);
if (left < pivot) quick_sort(a, left, pivot-1);
if (right > pivot) quick_sort(a, pivot+1, right);}
}
59
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
void swap(int &a,int &b)
{ int t = a; a = b; b = t; }
Cài đặt Quick Sort (dễ đọc hơn?)
int Partition(int a[], int L, R) int
{
int i, j, p;
i = L; j = R + 1; p = a[L];
while (i < j) {
i = i + 1;
while ((i <= R)&&(a[i]<p)) i++;
j--;
while ((j >= L)&& (a[j]>p)) j--;
swap(a[i] , a[j]);
}
swap(a[i], a[j]); swap(a[j], a[L]);
return j;
}
void quick_sort(int a[], int intleft, right)
{
int p;
if (left < right)
{
;
if (left < pivot)
quick_sort(a, left, pivot-1);
if (right > pivot)
quick_sort(a, pivot+1, right);}
}
60
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Chương trình DEMO
/* CHUONG TRINH DEMO QUICK SORT */
/* include: stdlib.h; stdio.h; conio.h; process.h; include time.h */
void quick_sort(int a[], int left, int right);
void swap(int &a, int &b);
int Partition(int a[], int left, int right);
int a[1000]; int n; // n - so luong phan tu cua day can sap xep
void main() {
int i; clrscr();
printf("\n Give n = "); scanf("%i",&n); randomize();
for (i = 0; i < n; i++) a[i] = rand(); // Tao day ngau nhien
printf("\nDay ban dau la: \n");
for (i = 0; i < n; i++) printf("%8i ", a[i]);
quick_sort(a, 0, n-1); // Thuc hien quick sort
printf("\n Day da duoc sap xep.\n");
for (i = 0; i < n; i++) printf("%8i ", a[i]);
a[n]=32767;
for (i = 0; i < n; i++)
if (a[i]>a[i+1]) {printf(" ??????? Loi o vi tri: %6i ", i); getch(); }
printf("\n Correct!"); getch();
}
61
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
62
30 19 24 28 41 34 15 43 20 12 36
12 15 19 20 24 28 30 34 36 41 43
19 24 28 15 20 12 41 34 43 3630
12 15 19 20 24 28
15 12 19 24 28 20
12 15 20 24 28
34 36 41 43
34 36
12 15 20 24 28 34 36
T(q) O(n)
O(1)
T(n-q)
34 36 41 43
(0) (1) 1
( ) ( ) ( ) ( ) (1)
T T
T n T q T n q O n O
CuuDuongThanCong.com
Thời gian tính của Quick-Sort
• Thời gian tính của Quick-Sort phụ thuộc vào việc phép phân chia là
cân bằng (balanced) hay không cân bằng (unbalanced), và điều
đó lại phụ thuộc vào việc phần tử nào được chọn làm chốt.
1. Phân đoạn không cân bằng: thực sự không có phần nào cả, do
đó một bài toán con có kích thước n – 1 còn bài toán kia có kích
thước 0.
2. Phân đoạn hoàn hảo (Perfect partition): việc phân đoạn luôn
được thực hiện dưới dạng phân đôi, như vậy mỗi bài toán con
có kích thước cỡ n/2.
3. Phân đoạn cân bằng: việc phân đoạn được thực hiện ở đâu đó
quanh điểm giữa, nghĩa là một bài toán con có kích thước n – k
còn bài toán kia có kích .thước k
63
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Ta sẽ xét từng tình huống!
64
Phân đoạn không cân bằng
(Unbalanced partition)
Công thức đệ qui là:
T T(n) = T(n – 1) + (0) + Θ(n)
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
n
2
n – 1
1
1
1
1
n – 2
1
nnTnT
TT
)1()(
1)1()0(
)1()2()1(
nnTnT
)2()3()2(
nnTnT
)2()1()2(
...
TT
n
i
iTnT
2
)1()(
)(
2
nO
CuuDuongThanCong.com
65
Khi phần tử chốt được chọn là phần tử đứng đầu:
Tình huống tồi nhất xảy ra khi dãy đầu vào là đã được sắp xếp
1 2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10 11
2 3 4 5 6 7 8 9 10 11
3 4 5 6 7 8 9 10 11
4 5 6 7 8 9 10 11
nnTnT
TT
)1()(
1)1()0(
66
Phân đoạn hoàn hảo - Perfect partition
nTnT 2
log
T n n n
Công thức đệ qui:
T(n) = T(n/2) + T(n/2) + Θ(n)
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Theo định lý thợ !
It's Best Case!
CuuDuongThanCong.com
67
Phân tích tình huống tồi nhất
Ta có công thức đệ qui:
Mệnh đề: T(n n) ≤ cn O
2
= (
2
)
Chứng minh: Qui nạp theo n.
• Base case: Rõ ràng bổ đề đúng cho n=1.
• Induction step: n Giả sử bổ đề đúng với mọi < n’, ta chứng minh
nó đúng cho n’. Ta có:
1 '
2 2
2 2
' max ( ) ' '
( ' ) '
2 ( ') 2 ' '
q n
T n T q T n q n
cq c n q dn
cq c n cqn dn
1
max ( )
q n
T n T q T n q n
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
(giả thiết qui nạp)
68
Phân tích tình huống tồi nhất
• Để hoàn thành chứng minh, ta cần chỉ ra rằng
2 ( ') 2 (cq
2
+ c n
2
cqn' +dn' ≤ c n') ,
2
• và bất đẳng thức này là :tương đương với
dn cq' ≤ 2 (n'q)
• Do q n( ’-q) có thể
xét hai tình huống: q < n/2 và n ≥ q ≥ n/2), nên ta có thể chọn c
đủ lớn để bất đẳng thức cuối cùng là đúng.
• Mệnh đề được chứng minh.
• Do trong tình huống phân đoạn không cân bằng QS có thời
gian tính Θ(n
2
), nên từ mệnh đề suy ra thời gian tính trong tình
huống tồi nhất của QS là O(n
2
).
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
69
Thời gian tính trung bình của QS
QuickSort Average Case
• Giả sử rằng pivot được chọn ngẫu nhiên trong số các
phần tử của dãy đầu vào
• Tất cả các tình huống sau đây là đồng khả năng:
– Pivot là phần tử nhỏ nhất trong dãy
– Pivot là phần tử nhỏ nhì trong dãy
– Pivot là phần tử nhỏ thứ ba trong dãy
…
– Pivot là phần tử lớn nhất trong dãy
• Điều đó cũng là đúng khi pivot luôn được chọn là phần
tử đầu tiên, với giả thiết là dãy đầu vào là hoàn toàn
ngẫu nhiên
70
Thời gian tính trung bình của QS
QuickSort Average Case
• Thời gian tính trung bình =
(thời gian phân đoạn kích thước i)(xác suất phân đoạn có kích thước i)
• Trong tình huống ngẫu nhiên, tất cả các kích thước là đồng khả
năng xác suất chính là - 1/N
• Giải công thức đệ qui này ta thu được
E T N O N( ( )) = (N log ).
0
0
1
1
( ( )) (1/
( ) ( ) ( 1)
( ( )) (2 / ) ( ( )
) ( ( )) ( ( 1)
)
)
i
N
N
i
E T N N E T i E T N
T N T i T N i cN
E T N N E T i cN
i cN
CuuDuongThanCong.com
NỘI DUNG
5.1. Bài toán sắp xếp
5.2. Ba thuật toán sắp xếp cơ bản
5.3. Sắp xếp trộn (Merge Sort)
5.4. Sắp xếp nhanh (Quick Sort)
5.5. Sắp xếp vun đống (Heap Sort)
5.6. Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp
5.7. Các phương pháp sắp xếp đặc biệt
71
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
5.5. Sắp xếp vun đống (Heap Sort)
5.5.1. Cấu trúc dữ liệu đống (heap)
5.5.2. Sắp xếp vun đống
5.5.3. Hàng đợi có ưu tiên (priority queue)
72
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
5.5.1. The Heap Data Structure
• Định nghĩa: Đống (heap) là cây nhị phân gần hoàn chỉnh có hai
tính chất sau:
– Tính cấu trúc (Structural property): tất cả các mức đều là đầy, ngoại
trừ mức cuối cùng, mức cuối được điền từ trái sang .phải
– Tính có thứ tự hay tính chất đống (heap property): với mỗi nút x
Parent( .x) ≥ x
• Cây được cài đặt bởi mảng A[i] có độ dài length[A]. Số lượng
phần tử là ]heapsize[A
73
Heap
5
7
8
4
2
Từ tính chất đống suy ra:
“Gốc chứa phần tử lớn nhất của đống!”
Như vậy có thể nói:
Đống là cây nhị phân được điền theo thứ tự
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Biểu diễn đống bởi mảng
74
• Đống có thể cất giữ trong mảng A.
– Gốc của cây là A[1]
– Con trái của A[i] là A[2*i]
– Con phải của A[i] là A[2*i + 1]
– Cha của A[i
– Heapsize[A] ≤ length[A]
• Các phần tử trong mảng con
A[( n/2 +1) .. n] là các lá
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
parent(i) = i/2
left-child(i) = 2i
right-child(i) = 2i +1
CuuDuongThanCong.com
75
Ví dụ đống
16
14
8 7
142
10
9
3
0
1
2
3
parent(i) = i/2
left-child(i) = 2i
right-child(i) = 2i +1
1
2 3
4 5 6 7
8 9
10
16 14 10 8 7 9 3 2 4 1
1 2 3 4 5 6 7 8 9 10
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Hai dạng đống
• Đống max - Max-heaps (Phần tử lớn nhất ở gốc), có tính chất
max-heap:
– với mọi nút i, ngoại trừ gốc:
A[parent(i)] ≥ A[i]
• Đống min - Min-heaps (phần tử nhỏ nhất ở gốc), có tính chất
min-heap:
– với mọi nút i, ngoại trừ gốc:
A[parent(i)] ≤ A[i]
• Phần dưới đây ta sẽ chỉ xét đống max (max heap). Đống min -
được xét hoàn toàn tương tự.
76
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Bổ sung và loại bỏ nút
Adding/Deleting Nodes
• Nút mới được bổ sung vào mức đáy (từ trái sang phải)
• Các nút được loại bỏ khỏi mức đáy (từ phải sang trái)
77
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Các phép toán đối với đống
Operations on Heaps
• Khôi phục tính chất max heap (Vun lại đống)-
– Max-Heapify
• Tạo max heap từ một mảng không được sắp xếp-
– Build-M
78
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Khôi phục tính chất đống
79
• Giả sử có nút i với giá trị bé hơn con của nó
– Giả thiết là: Cây con trái và Cây con phải của đều là maxi -heaps
• Để loại bỏ sự vi phạm này ta tiến hành như sau:
– Đổi chỗ với con lớn hơn
– Di chuyển xuống theo cây
– Tiếp tục quá trình cho đến khi nút không còn bé hơn con
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Ví dụ
80
A[2] vi phạm tính chất đống
A[2] A[4]
A[4] vi phạm
A[4] A[9]
Tính chất đống được khôi phục
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Max-Heapify(A, i, n)
// n = ]heapsize[A
1. l left-child(i)
2. r right-child(i)
3. if (l ≤ n) and (A[l] > A[i])
4. then largest l
5. else largest i
6. if (r ≤ n) and (A[r] > A largest[ ])
7. then largest r
8. if largest = i!
9. then Exchange(A A largest[i], [ ])
10. Max-Heapify(A,largest,n)
Thuật toán khôi phục tính chất đống
81
• Giả thiết:
– Cả hai cây con trái
và phải của i đều là
max-heaps
– A[i] có thể bé hơn
các con của nó
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Thời gian tính của MAX-HEAPIFY
• Ta nhận thấy rằng:
– Từ nút i phải di chuyển theo đuờng đi xuống phía dưới của cây. Độ dài
của đường đi này không vượt quá độ dài đường đi từ gốc đến lá, nghĩa
là khôngvượt quá h.
– Ở mỗi mứ
– Do đó tổng số phép so sánh không vượt quá 2h.
– Vậy, thời gian tính là O(h) hay (log O n).
• Kết luận: Thời gian tính của MAX-HEAPIFY là (log ) O n
• Nếu viết trong ngôn ngữ chiều cao của đống, thì thời gian này
là O(h)
82
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Xây dựng đống (Building a Heap)
Alg: Build-Max-Heap(A)
1. n = length[A]
2. for i ← n/2 1 downto
3. do Max-Heappify(A, i, n)
83
• Biến đổi mảng A[1 … n] thành max-heap (n = length[A])
• Vì các phần tử của mảng con A[(n/2+1) .. n] là các lá
• Do đó để tạo đống ta chỉ cần áp dụng MAX HEAPIFY đối với -
các phần tử từ 1 đến n/2
2
14 8
1
16
7
4
3
9 10
1
2 3
4 5 6 7
8 9 10
4 1 3 2 16 9 10 14 8 7A:
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Ví dụ: A:
4 1 3 2 16 9 10 14 8 7
84
2
14 8
1
16
7
4
3
9 10
1
2 3
4 5 6 7
8 9 10
14
2 8
1
16
7
4
10
9 3
1
2 3
4 5 6 7
8 9 10
2
1
16
4
3
9 10
1
2 3
4 5 6 7
8 9 10
14
1
16
4
3
9 10
1
2 3
4 5 6 7
8 9 10
14
2 8
16
7
1
4
10
9 3
1
2 3
4 5 6 7
8 9 10
8
2 4
14
7
1
16
10
9 3
1
2 3
4 5 6 7
8 9 10
i i= 5 i = 4 = 3
i i= 2 = 1
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Ví dụ: Build-Min-Heap
87
43
68
6 77 33 9
11
19 99 6 23 89 2 14
1 5 27 35 7 42 12 71 3 67
22
size = 26
Ví dụ: Build-Min-Heap
87
43
68
6 77 33 9
11
19 99 6 23 89 2 14
1 5 27 35 7 42 12 71 3 67
22
size = 26
Bắt đầu từ phần
tử ở vị trí n/2
13
CuuDuongThanCong.com
Build-Min-Heap
87
43
68
6 77 33 9
11
19 99 6 23 89 2 14
1 5 27 35 7 42 12 71 3 67
22
size = 26
Vun lại đống
13
Build-Min-Heap
87
43
68
6 77 33 9
11
19 99 6 23 22 2 14
1 5 27 35 7 42 12 71 3 67
89
size = 26
Vun lại đống
13
CuuDuongThanCong.com
Build-Min-Heap
87
43
68
6 77 33 9
11
19 99 6 23 22 2 14
1 5 27 35 7 42 12 71 3 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
87
43
68
6 77 33 9
11
19 99 6 3 22 2 14
1 5 27 35 7 42 12 71 23 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
87
43
68
6 77 33 9
11
19 99 6 3 22 2 14
1 5 27 35 7 42 12 71 23 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
87
43
68
6 77 33 9
11
19 99 6 3 22 2 14
1 5 27 35 7 42 12 71 23 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
87
43
68
6 77 33 9
11
19 7 6 3 22 2 14
1 5 27 35 99 42 12 71 23 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
87
43
68
6 77 33 9
11
19 7 6 3 22 2 14
1 5 27 35 99 42 12 71 23 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
87
43
68
6 77 33 9
11
19 7 6 3 22 2 14
1 5 27 35 99 42 12 71 23 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
87
43
68
6 77 33 9
1
19 7 6 3 22 2 14
11 5 27 35 99 42 12 71 23 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
87
43
68
6 77 33 9
1
19 7 6 3 22 2 14
11 5 27 35 99 42 12 71 23 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
87
43
68
6 77 33 2
1
19 7 6 3 22 9 14
11 5 27 35 99 42 12 71 23 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
87
43
68
6 77 33 2
1
19 7 6 3 22 9 14
11 5 27 35 99 42 12 71 23 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
87
43
68
6 77 3 2
1
19 7 6 33 22 9 14
11 5 27 35 99 42 12 71 23 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
87
43
68
6 77 3 2
1
19 7 6 33 22 9 14
11 5 27 35 99 42 12 71 23 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
87
43
68
6 77 3 2
1
19 7 6 23 22 9 14
11 5 27 35 99 42 12 71 33 67
89
size = 26
13
CuuDuongThanCong.com
Build-Min-Heap
87
43
68
6 77 3 2
1
19 7 6 23 22 9 14
11 5 27 35 99 42 12 71 33 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
87
43
68
6 6 3 2
1
19 7 77 23 22 9 14
11 5 27 35 99 42 12 71 33 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
87
43
68
6 6 3 2
1
19 7 77 23 22 9 14
11 5 27 35 99 42 12 71 33 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
87
43
68
6 6 3 2
1
19 7 12 23 22 9 14
11 5 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
87
43
68
6 6 3 2
1
19 7 12 23 22 9 14
11 5 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
87
43
68
1 6 3 2
6
19 7 12 23 22 9 14
11 5 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
87
43
68
1 6 3 2
6
19 7 12 23 22 9 14
11 5 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
87
43
68
1 6 3 2
5
19 7 12 23 22 9 14
11 6 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
87
43
68
1 6 3 2
5
19 7 12 23 22 9 14
11 6 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
87
43
2
1 6 3 68
5
19 7 12 23 22 9 14
11 6 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
87
43
2
1 6 3 68
5
19 7 12 23 22 9 14
11 6 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
87
43
2
1 6 3 9
5
19 7 12 23 22 68 14
11 6 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
87
43
2
1 6 3 9
5
19 7 12 23 22 68 14
11 6 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
87
1
2
43 6 3 9
5
19 7 12 23 22 68 14
11 6 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
87
1
2
43 6 3 9
5
19 7 12 23 22 68 14
11 6 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
87
1
2
5 6 3 9
43
19 7 12 23 22 68 14
11 6 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
87
1
2
5 6 3 9
43
19 7 12 23 22 68 14
11 6 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
87
1
2
5 6 3 9
6
19 7 12 23 22 68 14
11 43 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
87
1
2
5 6 3 9
6
19 7 12 23 22 68 14
11 43 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
1
87
2
5 6 3 9
6
19 7 12 23 22 68 14
11 43 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
1
87
2
5 6 3 9
6
19 7 12 23 22 68 14
11 43 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
1
5
2
87 6 3 9
6
19 7 12 23 22 68 14
11 43 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
1
5
2
87 6 3 9
6
19 7 12 23 22 68 14
11 43 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
1
5
2
6 6 3 9
87
19 7 12 23 22 68 14
11 43 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
1
5
2
5 6 3 9
87
19 7 12 23 22 68 14
11 43 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
Build-Min-Heap
1
5
2
5 6 3 9
11
19 7 12 23 22 68 14
87 43 27 35 99 42 77 71 33 67
89
size = 26
13
Vun lại đống
CuuDuongThanCong.com
Build-Min-Heap
1
5
2
5 6 3 9
11
19 7 12 23 22 68 14
87 43 27 35 99 42 77 71 33 67
89
size = 26
13
Kết thúc
Thời gian tính của Buil-Max-Heap
Thời gian tính là: log )O(n n
• Đánh giá này là không sát !
130
Alg: Build-Max-Heap(A)
1. n = length[A]
2. for i ← n/2 1 downto
3. do
O(n)
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Thời gian tính của Buid-Max-Heap
0 0
( ) 2 ( ) ( )
h h
i
i i
i i
T n n h h i O n
131
• Heapify đòi hỏi thời gian O h( ) chi phí của Heapify ở nút i
là tỷ lệ với chiều cao của nút i trên cây
Chiều cao Mức
h
0
= 3 ( log n )
h
1
= 2
h
2
= 1
h
3
= 0
i = 0
i = 1
i = 2
i = 3 ( log n )
Số lượng nút
2
0
2
1
2
2
2
3
h
i
= h – i chiều cao của đống gốc tại mức i
n
i
= 2
i
số lượng nút ở mức i
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Thời gian tính của Build-Max-Heap
132
i
h
i
i
hnnT
0
)(
(Chi phí Heapify tại mức (số lượng nút trên mức này)i) ×
ih
h
i
i
0
2
Thay giá trị của tính được ở trênn
i
và h
i
h
i
ih
ih
2
0
Nhân cả tử và mẫu với 2 và viết 2
1
h
k
k
h
k
0
2
2
Đổi biến: k = h - i
0
2
k
k
k
n
Thay tổng hữu hạn bởi tổng vô hạn
và = log h n
)(nO
Tổng trên là nhỏ hơn 2
Thời gian tính của Build-Max-Heap: ) = T(n O(n)
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
5.5.2. Sắp xếp vun đống - Heapsort
• Sử dụng đống ta có thể phát triển thuật toán sắp xếp mảng.
• Sơ đồ của thuật toán được trình bày như sau:
– Tạo đống max-heap từ mảng đã cho
– Đổi chỗ gốc (phần tử lớn nhất) với phần tử cuối cùng trong mảng
– Loại bỏ nút cuối cùng bằng cách giảm kích thước của đống đi 1
– Thực hiện Max-Heapify đối với gốc mới
– Lặp lại quá trình cho đến khi đống chỉ còn 1 nút
133
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Ví dụ: A=[7, 4, 3, 1, 2]
134
Max-Heapyfy(A, 1 1, 2)
Max-Heapyfy(A, 1, 1)
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Algorithm: HeapSort( )A
1. Build-Max-Heap(A)
2. for i ← length[A] downto 2
3. do exchange A[1] ↔ A[i]
4. Max-Heapify(A, 1, i - 1)
• Thời gian tính: O n(n log )
• Có thể chứng minh thời gian tính là Θ(n log n)
135
O(n)
O(log n)
n-1 lần lặp
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
5.5.3. Hàng đợi có ưu tiên - Priority Queues
136
• Cho tập S thường xuyên biến động, mỗi phần tử x được gán với
một giá trị gọi là khoá (hay độ ưu tiên). Cần một cấu dữtrúc
liệu hỗ trợ hiệu quả các thao tác chính sau:
– Insert(S, x) – Bổ sung phần tử x vào S
– Max(S) – t
– Extract-Max(S) – loại bỏ và trả lại phần tử lớn nhất
– Increase-Key(S,x,k) – tăng khoá của x thành k
• Cấu trúc dữ liệu đáp ứng các yêu cầu đó là hàng đợi có ưu
tiên.
• Hàng đợi có ưu tiên có thể tổ chức nhờ sử dụng cấu trúc dữ
liệu đống để cất giữ các khoá.
• Chú ý: Có thể thay "max" bởi "min" .
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Các phép toán đối với hàng đợi có ưu tiên
Operations on Priority Queues
• Hàng đợi có ưu tiên (max) có các phép toán cơ bản sau:
– Insert(S, x): bổ sung phần tử x vào tập S
– Extract-Max(S): loại bỏ và trả lại phần tử của S với khoá
lớn nhất
– Maximum(S): trả lại phần tử của S với khoá lớn nhất
– Increase-Key(S, x, k): tăng giá trị của khoá của phần tử x
lên thành k (Giả sử k ≥ khoá hiện tại của x)
137
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Các phép toán đối với hàng đợi có ưu tiên (min)
Operations on Priority Queues
• Hàng đợi có ưu tiên (min) có các phép toán cơ bản sau:
– Insert(S, x): bổ sung phần tử x vào tập S
– Extract-Min(S): loại bỏ và trả lại phần tử của S với khoá
nhỏ nhất
– Minimum(S): trả lại phần tử của S với khoá nhỏ nhất
– Deacrease-Key(S, x, k): giảm giá trị của khoá của phần tử
x xuống còn k (Giả sử k khoá hiện tại của x)
138
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Phép toán HEAP-MAXIMUM
139
Chức năng: Trả lại phần tử lớn nhất của đống
Alg: Heap-Maximum(A)
1.
return A[1]
Thời gian tính: O(1)
Heap A:
Heap-Maximum(A) trả lại 7
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Heap-Extract-Max
Chức năng: Trả lại phần tử lớn nhất và loại bỏ nó khỏi đống
Thuật toán:
– Hoán đổi gốc với phần tử cuối cùng
– Giảm kích thước của đống đi 1
– Gọi Ma
140
Đống A:
Gốc là phần tử lớn nhất
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Ví dụ: Heap-Extract-Max
141
8
2 4
14
7
1
16
10
9 3
max = 16
8
2 4
14
7
1
10
9 3
Kích thước đống giảm đi 1
4
2 1
8
7
14
10
9 3
Thực hiện Max-Heapify(A, 1, n-1)
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Alg: Heap-Extract-Max(A, n)
1. if n < 1
2. then e
3. max ← A[1]
4. A[1] ← A[n]
5. Max-Heapify(A, 1, n-1) // Vun lại đống
6. return max
Heap-Extract-Max
142
Thời gian tính: O(log )n
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Heap-Increase-Key
• Chức năng: Tăng giá trị khoá của phần tử i trong đống
• Thuật toán:
– Tăng khoá của A[i] thành giá trị mới
– Nếu tính chất max-heap bị vi phạm: di chuyển theo đường
đến gốc để tìm chỗ thích hợp cho khoá mới bị tăng này
143
8
2 4
14
7
1
16
10
9 3
i
Key [i] ← 15
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Ví dụ: Heap-Increase-Key
144
14
2 8
15
7
1
16
10
9 3
i
8
2 4
14
7
1
16
10
9 3
i
Key [i ] ← 15
8
14
7
16
10
9 3
i
15
2 8
14
7
1
16
10
9 3
i
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Heap-Increase-Key
Alg: Heap-Increase-Key(A, i, key)
1. if key < A[i]
2. then error “khoá mới nhỏ hơn khoá hiện tại”
3. A[i] ← key
4. while i > 1 and A[parent(i)] < A[i]
5. do hoán đổi A[i] ↔ A[parent(i)]
6. i ← parent(i)
• Thời gian tính: O(log n)
145
8
2 4
14
7
1
16
10
9 3
i
Key [i] ← 15
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
146
Ví dụ: Heap-Increase-Key (1)
16
14
8
7
1
42
10
9
3
1
2 3
4 5 6 7
8 9
10
increase 4 to 15
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
147
Ví dụ: Heap-Increase-Key (2)
16
14
8
7
1
152
10
9
3
1
2 3
4 5 6 7
8 9
10
thay 4 bởi 15
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
148
Ví dụ: Heap-Increase-Key (3)
16
15
7
1
82
9
3
1
2 3
4 5 6 7
8 9
10
đi ngược lên để sửa vi phạm
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
149
Ví dụ: Heap-Increase-Key (4)
16
15
14
7
1
82
10
9
3
1
2 3
4 5 6 7
8 9
10
đã đặt đúng vị trí
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Max-Heap-Insert
• Chức năng: Chèn một phần tử
mới vào max-heap
• Thuật toán:
– Mở rộng max-heap với một nút
mới có khoá là -
– Gọi Heap-Increase-Key để tăng
khoá của nút mới này thành giá
trị của phần tử mới và vun lại
đống
150
8
14
7
16
10
9 3
15
8
2 4
14
7
1
16
10
9 3
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Ví dụ: Max-Heap-Insert
151
-
8
2 4
14
7
1
16
10
9 3
Chèn giá trị 15:
- Bắt đầu với -
15
8
2 4
14
7
1
16
10
9 3
Tăng khoá thành 15
Gọi Heap Key với A[11] = 15-Increase-
7
8
2 4
14
15
1
16
10
9 3
7
8
2 4
15
14
1
16
10
9 3
Vun lại đống
với phần tử
mới bổ sung
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Max-Heap-Insert
Alg: Max-Heap-Insert(A, key, n)
1. heap- 1size[A] ← n +
2. A[n + 1] ← -
3. Heap-Increase-Key(A, n + 1, key)
152
Running time: (log )O n
-
8
2 4
14
7
1
10
9 3
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Tổng kết
• Chúng ta có thể thực hiện các phép toán sau đây với đống:
Phép toán Thời gian tính
– Max-Heapify O(log )n
– Build-Max-Heap )O(n
– Heap-Sort O(n log )n
– Max-Heap-Insert O(log )n
– Heap-Extract-Max O(log )n
– Heap-Increase-Key O(log )n
– Heap-Maximum O(1)
153
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Câu hỏi
154
• Giả sử các số trong max-heap là phân biệt, phần tử lớn thứ hai
nằm ở đâu?
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
• Ans: Con lớn hơn trong hai con của gốc
CuuDuongThanCong.com
Mã Huffman: Thuật toán
procedure Huffman(C, f);
begin
n |C|;
Q C;
for i:=1 to n-1 do
begin
x, y 2 chữ cái có tần suất nhỏ nhất trong Q; (* Thao tác 1 *)
Tạo nút p với hai con x, y;
f(p) := f(x) + f(y);
Q Q \ {x, y} {p} (* Thao tác 2 *)
end;
end;
•
Cà
Cà
Cà
CàCà
i
i
i
i i
đ
đ
đ
đđ
ặt
ặt
ặt
ặtặt
t
t
t
tt
rự
rự
rự
rựrự
c
c
c
c c
ti
ti
ti
titi
ế
ế
ế
ếế
p:
p:
p:
p:p:
– Thao tác 1: O(n)
– Thao tác 2: O(1)
=>
=>
=>
=>=>
T
T
T
TT
hờ
hờ
hờ
hờhờ
i
i
i
i i
g
g
g
gg
i
i
i
ii
an
an
an
an an
O(n
2
)
1/28/2013
Mã Huffman: Thuật toán
procedure Huffman(C, f);
begin
n |C|;
Q C;
for i:=1 to n-1 do
begin
x, y 2 chữ cái có tần suất nhỏ nhất trong Q; (* Thao tác 1 *)
Tạo nút p
f(p) := f(x) + f(y);
Q Q \ {x, y} {p} (* Thao tác 2 *)
end;
end;
•
Cà
Cà
Cà
CàCà
i
i
i
i i
đ
đ
đ
đđ
ặt
ặt
ặt
ặtặt
s
s
s
ss
ử
ử
ử
ửử
d
d
d
dd
ụ
ụ
ụ
ụụ
ng
ng
ng
ngng
priority queue Q:
– Thao tác 1 và 2: O(log
n
)
=>
=>
=>
=>=>
T
T
T
TT
hờ
hờ
hờ
hờhờ
i
i
i
i i
g
g
g
gg
i
i
i
ii
an
an
an
an an O(n log n )
1/28/2013
CuuDuongThanCong.com
Có thể sắp xếp nhanh đến mức độ nào?
• Heapsort, Mergesort, và Quicksort có thời gian O(n log n) là
các thuật toán có thời gian tính tốt nhất trong các thuật toán
trình bày ở trên
• Liệu có thể phát triển được thuật toán tốt hơn không?
• Câu trả lời là: "Không, nếu như phép toán cơ bản là phép so
sánh".
157
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
NỘI DUNG
5.1. Bài toán sắp xếp
5.2. Ba thuật toán sắp xếp cơ bản
5.3. Sắp xếp trộn (Merge Sort)
5.4. Sắp xếp nhanh (Quick Sort)
5.5. Sắp xếp vun đống (Heap Sort)
5.6. Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp
5.7. Các phương pháp sắp xếp đặc biệt
158
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Cây quyết định
• Cây quyết định là cây nhị phân thoả mãn:
– Mỗi nút một phép so sánh "a < b"
• cũng có thể coi tương ứng với một tựkhông gian con các trình
– Mỗi cạnh rẽ nhánh theo câu trả lời (true hoặc false)
– Mỗi lá 1 trình tự sắp xếp
– Cây quyết định có bao nhiêu lá, nếu có N phần tử phân biệt
cần sắp xếp?
• N!, tức là tất cả các trình tự có thể
• Đối với mỗi bộ dữ liệu, chỉ có 1 lá chứa trình tự sắp
xếp cần tìm
159
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Ví dụ: Cây quyết định với N=3
160
"a < b?"
a < b < c, b < c < a,
c < a < b, a < c < b,
b < a < c, c < b < a
"a < c?"
a < b < c
c <
a < c < b
"b < c?"
b < c < a
c < b < a
"b < c?"
a < b < c
a < c < b
c < a < b
a < b < c
a < c < b
"b < c?"
b < c < a
b < a < c
c < b < a
b < c < a b < a < c
true
false
falsetrue
true
false
true
false
true
false
các trình tự có thể
trình tự cần tìm
Các lá chứa tất cả các trình tự có thể
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Cây quyết định và sắp xếp
• Mỗi thuật toán đều có thể mô tả bởi cây quyết định
– Tìm lá nhờ di chuyển theo cây (tức là thực hiện phép so
sánh)
– Mỗi quyết định sẽ giảm không gian tìm kiếm đi một nửa
• Thời gian tính trong tình huống tồi nhất số phép so
sánh nhiều nhất phải thực hiện
– số phép so sánh nhiều nhất cần thực hiện chính là độ dài
đường đi dài nhất trên cây quyết định, tức là độ cao của cây
161
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Cận dưới của chiều cao
• Cây nhị phân có chiều cao có nhiều nhất bao nhiêu lá?h
L ≤ 2
h
• Cây quyết định có nhiều nhất bao nhiêu lá?
L = N!
• Cây quyết định với lá có độ cao ít nhất là:L
h ≥ log
2
L
• Vậy cây quyết định có độ cao:
h ≥ log
2
(N!)
162
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
log( ( log )N!) là
N N
163
)log(
2
log
2
)2log(log
2
2
log
2
2
log)2log()1log(log
1log2log)2log()1log(log
)1()2()2()1(log)!log(
NN
N
N
N
N
N
NN
N
NNN
NNN
NNNN
chỉ chọn N/2
số hạng đầu
mỗi số hạng được
chọn là log /2N
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Cận dưới cho độ phức tạp của bài toán sắp xếp
• Thời gian tính của mọi thuật toán chỉ dựa trên phép
so sánh là
(N log )N
• Độ phức tạp tính toán của bài toán sắp xếp chỉ dựa
trên phép so sánh là
(N log )N
• Ta có thể phát triển thuật toán tốt hơn hay không nếu
không hạn chế là chỉ được sử dụng phép so sánh?
164
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
NỘI DUNG
5.1. Bài toán sắp xếp
5.2. Ba thuật toán sắp xếp cơ bản
5.3. Sắp xếp trộn (Merge Sort)
5.4. Sắp xếp vun đống (Heap Sort)
5.5. Sắp xếp nhanh (Quick Sort)
5.6. Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp
5.7. Các phương pháp sắp xếp đặc biệt
165
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
5.7. Các phương pháp sắp xếp đặc biệt
5.7.1. Mở đầu
5.7.2. Sắp xếp đếm (Counting Sort)
5.7.3. Sắp xếp theo cơ số (Radix Sort)
5.7.4. Sắp xếp đóng gói (Bucket Sort)
166
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Mở đầu: Sắp xếp trong thời gian tuyến tính
Linear-time sorting
• Ta có thể làm tốt hơn sắp xếp chỉ sử dụng phép so sánh?
• Với những thông tin bổ sung (hay là giả thiết) về đầu vào,
chúng ta có thể làm tốt hơn sắp xếp chỉ dựa vào phép so sánh.
• Thông tin :bổ sung/Giả thiết
– Các số nguyên nằm trong khoảng [0..k] trong đó k = O(n).
– Các số thực phân bố đều trong khoảng [0,1)
• Ta trình bày ba thuật toán có thời gian tuyến tính:
– Sắp xếp đếm (Counting-Sort)
– Sắp xếp theo cơ số (Radix-Sort)
– Sắp xếp đóng gói (Bucket-sort)
• Để đơn giản cho việc trình bày, ta xét việc sắp xếp các số
nguyên không âm.
167
5.7.2. Sắp xếp đếm (Counting sort)
• Input: n số nguyên trong khoảng [0..k] trong đó k là số
nguyên và k = O n( ).
• Ý tưởng: với mỗi phần tử x của dãy đầu vào ta xác định hạng
(rank) của nó như là số lượng phần tử nhỏ hơn x.
• Một khi ta í r+1.
• Ví dụ: Nếu có 6 phần tử nhỏ hơn 17, ta có thể xếp 17 vào vị
trí 7.thứ
• Lặp: khi có một loạt phần tử có cùng giá trị, ta sắp xếp chúng
theo thứ tự xuất hiện trong dãy ban đầu (để có được tính ổn
định của sắp xếp).
168
CuuDuongThanCong.com
Cài đặt
void countSort(int a[],int b[],int c[],int k) {
// k - giá trị phần tử lớn nhất
// Đếm: b[i] - số phần tử có giá trị i
for (int i=0; i <= k; i++) b[i] = 0;
for (i=0; i<n; i++) b[a[i]]++;
// Tính hạng: b[i] hạng của phần tử có giá trị i
for (i = 1; i <= k; i++)
b[i] += b[i - 1];
// Sắp xếp
for (i = n-1; i >= 0; i--) {
c[b[a[i]] - 1] = a[i];
b[a[i]] = b[a[i]] - 1;
}
}
169
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Chương trình demo
/* include <iostream.h, stdlib.h, stdio.h,
conio.h, process.h, time.h */
int a[10000], c[10000]; int n;
void print(int a[], int n) {
for (int i = 0; i < n; i++)
printf("%8i", a[i]);
printf("\n");
}
void countSort(int a[], int b[], int c[], int amax);
void main() {
int i, k; // gia tri lon nhat co the cua mang A
clrscr(); randomize();
printf("\ n n = "); scanf("%i",&n);
printf("\ n max = "); scanf("%i",&k);
for (i = 0; i < n; i++) a[i] = rand() % k;
printf("\n Day ban dau:\n"); print(a,n);
int * b; int amax = 0;
// Tinh phan tu lon nhat amax
for (i = 0; i < n; i++)
if (a[i] > amax) amax = a[i];
b = new int[amax];
printf("\n Day ket qua:\n");print(c,n);
// Verify result array
c[n]=32767;
for (i = 0; i < n; i++)
if (c[i]>c[i+1]) {
printf(" ??????? Loi o vi tri: %6i ", i);
getch(); }
printf("\n Correct!"); getch();
}
170
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Phân tích độ phức tạp của sắp xếp đếm
void countSort(int a[],int b[],int c[],int k) {
// Đếm: b[i] số phần tử có giá trị i-
for (int i=0; i <= k; i++) b[i] = 0;
for (i=0; i<n; i++) b[a[i]]++;
// Tính hạng: b[i] hạng của phần tử có giá trị i
for (i = 1; i <= k; i++) b[i] += b[i - 1];
// Sắp xếp
for (i = n-1; i >= 0; i--) {
c[b[a[i]] - 1] = a[i];
b[a[i]] = b[a[i]] - 1; }
}
• Vòng lặp for đếm b[i] - số phần tử có giá trị i, đòi hỏi thời gian Θ(n+k).
• Vòng lặp for tính hạng đòi hỏi thời gian Θ(n).
• Vòng lặp for thực hiện sắp xếp đòi hỏi thời gian Θ(k).
• Tổng cộng, thời gian tính của thuật toán là Θ(n+k)
• Do k = O(n), nên thời gian tính của thuật toán là Θ(n), nghĩa là, trong trường hợp này nó là
một trong những thuật toán tốt nhất.
• Điều đó là không xảy ra nếu giả thiết k = O(n) là không được thực hiện. Thuật toán sẽ làm
việc rất tồi khi k >> n.
• Sắp xếp đếm không có tính tại chỗ.
171
5.7.3. Sắp xếp theo cơ số (Radix sort)
• Giả thiết: Đầu vào gồm n số nguyên, mỗi số có .d chữ số
• Ý tưởng của thuật toán: Do thứ tự sắp xếp các số cần tìm
cũng chính là thứ tự từ điển của các xâu tương ứng với chúng,
nên để sắp xếp ta sẽ tiến hành d bước sau:
Bước 1. Sắp xếp số chữ số thứ
Bước 2. Sắp xếp các số trong dãy thu được theo chữ số thứ 2 (sử dụng sắp
xếp ổn định)
...
Bước d. Sắp xếp các số trong dãy thu được theo chữ số thứ d (sử dụng sắp
xếp ổn định)
• Giả sử các số được xét trong hệ đếm cơ số k. Khi đó mỗi chữ
số chỉ có k giá trị , nên ở mỗi bước ta có thể sử dụng sắp xếp
đếm với thời gian tính O n+k( ).
172
CuuDuongThanCong.com
Ví dụ
173
329
457
657
839
436
720
355
720
355
436
457
657
329
839
720
329
436
839
355
457
657
329
355
436
457
657
720
839
Radix Sort
Việc sắp xếp bao gồm nhiều bước bắt đầu từ chữ số hàng đơn vị, ,
tiếp đến là chữ số hàng chục, hàng trăm, v.v...
Ví dụ: 23, 45, 7, 56, 20, 19, 88, 77, 61, 13, 52, 39, 80, 2, 99
99
Bước 1:
Bước 2:
2 4
3 5
7
562 10 9
88
77
61
13
52
3980 2
2
0
8061
52
2
23
45
56
77
7
88
19
3
9
99
13
Thứ tự cần tìm
CuuDuongThanCong.com
Sơ đồ thuật toán Radix-Sort
Radix-Sort(A, d)
1. for i 1 to d do
2. Sử dụng sắp xếp ổn định để sắp xếp A theo chữ số thứ i
• Phân tích độ phức tạp:
• Thời gian tính: Nếu bước 2 sử dụng sắp xếp đếm thì thời gian
tính của một lần lặp là Θ(n+k), do đó thời gian tính của thuật
toán Radix Sort là T( ( ( làn) = Θ d n+k)). Thời gian này sẽ
Θ( ( )n) nếu d là hằng số và k = O n
• Chú ý: Để thực hiện sắp xếp ở mỗi lần lặp của thuật toán,
phải sử dụng thuật toán sắp xếp ổn định, nếu không sẽ không
có .kết quả đúng
175
Thuật toán sắp xếp theo cơ số nhị phân
• Ta xét các số nguyên không âm 32-bit và ta sẽ chuyển chúng về các số có
bốn chữ số trong hệ đếm cơ số 256.
• Giả sử
p = a
31
×2
31
+ a
30
×2
30
+ ... + a
2
×2 ×2 ×2
2
+ a
1
1
+ a
0
0
trong đó là bằng 0 hoặc 1. a
i
• Khi đó trong
p = b
3
×256 ×256
3
+ b
2
2
+ b
1
×256 ×256
1
+ b
0
0
trong đó
b
3
= a a
31
2
7
+
30
2
6
+ a
29
2
5
+ a
28
2
4
+ a
27
2
3
+ a
26
2
2
+ a
25
2
1
+ a
24
2
0
,
b
2
= a a
23
2
7
+
22
2
6
+ a
21
2
5
+ a
20
2
4
+ a
19
2
3
+ a
18
2
2
+ a
17
2
1
+ a
16
2
0
,
b
1
= a a
15
2
7
+
14
2
6
+ a
13
2
5
+ a
12
2
4
+ a
11
2
3
+ a
10
2
2
+ a a
9
2
1
+
8
2
0
,
b
0
= a a
7
2
7
+
6
2
6
+ a a
5
2
5
+
4
2
4
+ a a
3
2
3
+
2
2
2
+ a a
1
2
1
+
0
2
0
.
176
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Tính các chữ số
• Nếu số nguyên n nằm trong phạm vi [0,2
31
), ta có thể
tính các chữ số b
0
, b , b
1 2
, b
3
của nó nhờ sử dụng các
phép toán & (bitwise) và >> (dịch phải - right shift)
được cung cấp sẵn trong C (các phép toán này thực
hiện rất hiệu quả) như sau:
b
0
= n & 255
b
1
= (n >> 8) & 255
b
2
= (n >> 16) & 255
b
3
= (n >> 24) & 255
177
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Cài đặt trên C
void radixsort(long a[], int n){
int i, j, shift;
long temp[1000];
int bin_size[256], first_ind[256];
for (shift=0; shift
/* Tính kích thước mỗi cụm và sao chép các
phần tử của mảng a vào mảng temp */
for (i=0; i<256; i++) bin_size[i]=0;
for (j=0; j<n; j++) {
i=(a[j]>>shift)&255;
bin_size[i]++;
temp[j]=a[j];
}
/* Tính chỉ số vị trí bắt đầu của mỗi cụm */
first_ind[0]=0;
for (i=1; i<256; i++)
first_ind[i]=first_ind[i-1]+bin_size[i-1];
temp
*/
for (j=0; j<n; j++) {
i=(temp[j]>>shift)&255;
a[first_ind[i]]=temp[j];
first_ind[i]++; }
} // end for shift
} // end radixsort
178
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
Chương trình chính
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <conio.h>
void print(long a[], int n) {
for (int i = 0; i < n; i++)
printf("%8i", a[i]);
printf("\n");
}
int main () {
long data[1000];
int i, N;
printf("\ Nhap so luong phan tu n = ");
scanf("%i",&N);
// Randomdata
for ( i=0; i<N; i++ ) data[i]=rand();
printf("\n Day dau vao:\n"); print(data, N);
radixsort (data, N);
printf("\n Day duoc sap thu tu:\n"); print(data, N);
data[N]=9999999;
for ( i=0; i<N; i++ )
if (data[i]>data[i+1]) printf("\n ??????
ERROR:\n");
getch();
}
179
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
Chọn cơ số như thế nào?
180
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
… …
chữ số gồm
Mỗi chữ số trong khoảng
0 -- 2
r –1
b n/r bước, mỗi bước đòi hỏi thời gian ( +2
r
) (áp dụng Sắp xếp đếm).
Thời gian tính là ((b/r) (n + 2
r
)).
b/r chữ số
Nếu , chọnb ≤ log n r = b (n)
Nếu , chọn b > log n r = log n (bn/log n)
Khoá gồm b bit:
CuuDuongThanCong.com
Radix-Sort tổng quát
• Cho n số, mỗi số có b bit và số r ≤ b. Khi đó Radix-Sort đòi hỏi
thời gian Θ((b/r)( 2 )):n+
r
– Chọn d=b/ [0..2 1].r chữ số, mỗi chữ số gồm r bit có giá trị trong khoảng
r
–
– Vì thế ở mỗi bước có thể sử dụng Counting-Sort với k=2
r
–1, đòi hỏi thời
gian Θ(n+k),
– Tất cả phải thực hiện d bước, do đó thời gian tổng cộng là Θ(d(n+2
r
)), hay
Θ((b/ )( )).r n+2
r
• Với các giá trị của n và b cho trước, ta có thể chọn r ≤ b để đạt
cực tiểu của Θ(( )( 2 )).b/r n+
r
• Nếu b ≤ log n, chọn r = log n ta thu được thuật toán với thời gian
Θ(n).
• Nếu b > log logn, chọn r = n ta thu được thuật toán với thời gian
( ).bn/log n
181
5.7.4. Sắp xếp phân cụm (Bucket sort)
Giả thiết: Đầu vào gồm n số thực có phân bố đều trong khoảng
[0..1) (các số có xác suất xuất hiện như nhau)
Ý tưởng của thuật toán:
• Chia đoạn [0..1) ra làm n cụm (buckets)
0, 1/n
• Đưa mỗi phần tử a
j
vào đúng cụm của nó i/n ≤ a
j
< ( .i+1)/n
• Do các số là phân bố đều nên không có quá nhiều số rơi vào
cùng .một cụm
• Nếu ta chèn chúng vào các cụm (sử dụng sắp xếp chèn) thì các
cụm và các phần tử trong chúng đều được sắp xếp theo đúng
thứ tự.
182
CuuDuongThanCong.com
Bổ sung vào
các cụm
Ví dụ: Sắp xếp phân cụm,
n=10, các cụm là 0, 0.1, 0.2, ..., 0.9
183
.78
.17
.39
.26
.72
.94
. 21
.12
.23
.68
7
6
8
9
5
4
3
2
1
0
.17.12
.26.23.21
.39
.68
.78.72
.94
.68
.72
.78
.94
.39
.26
.23
.21
.17
.12
Sắp xếp mỗi cụm
Nối
các
cụm
Ví dụ
.78
.17
.26
.94
.12
.68
.72
.23.21
0
1
2
3
4
5
6
7
8
9
Bước : Nối các danh sách2
Bước : thực hiện insertion sort 1
trong mỗi danh sách
n số được phân vào n đoạn con bằng nhau của [0, 1).
.78
.17
.39
.26
.72
.94
.21
.12
.68
.23
A[ ]
Từ trên xuống dưới
Từ trái sang phải
CuuDuongThanCong.com
Sơ đồ thuật toán Bucket-Sort
Bucket-Sort(A)
1. n = length( )A
2. for i = 0 to n-1
3. do Bổ sung A[i] vào danh sách B[n*A[i] ]
4. for i = 0 to n –1
5. do Insertion-Sort( ])B[i
6. Nối các danh sách B[0], B B[1], … [n –1] theo thứ tự
185
A n[0.. -1] là mảng đầu vào
B B B[0], [1], …, [n –1] là các
danh sách cụm
Phân tích thời gian tính của Bucket-Sort
• Tất cả các dòng, ngoại trừ dòng 5 (Insertion-Sort), đòi hỏi thời
gian O(n) trong tình .huống tồi nhất
• Trong tình huống tồi nhất, O(n) số được đưa vào cùng một
cụm, do đó thuật toán có thời gian tính O(n
2
) trong tình huống
tồi nhất.
• Tuy nhiên, trong tình huống trung bình, chỉ có một số lượng
hằng số phần tử của dãy cần sắp xếp rơi vào trong mỗi cụm và
vì thế thuật toán có thời gian tính trung bình là O(n) (ta công
nhận sự kiện này).
• Mở rộng: sử dụng các sơ đồ chỉ số hoá khác nhau để phân
cụm các phần tử.
186
CuuDuongThanCong.com
Tổng kết:
Các thuật toán sắp xếp dựa trên phép so sánh
Name Average Worst In place Stable
Bubble sort — O(n²) Yes Yes
Selection sort O(n²) O(n²) Yes No
Insertion sort O( + n d) O(n²) Yes Yes
Merge sort O(n log logn) O(n n) No Yes
Heapsort O(n log logn) O(n n) Yes No
Quicksort O(n log n) O(n²) No No
187
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
QUESTIONS?
188
NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN
CuuDuongThanCong.com
| 1/94
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

Chương 5 Sắp xếp (Sorting) Heap Sort Quick Sort
William A. Martin, Sorting. ACM Computing Surveys, Vol. 3, Nr 4, Dec 1971, pp. 147-174.
" ...The bibliography appearing at the end of this article lists 37 sorting algorithms
and 100 books and papers on sorting published in the last 20 years...
Suggestions are made for choosing the algorithm best suited to a given situation."
D. Knuth: 40% thời gian hoạt động của các máy tính là dành cho sắp xếp! NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT - ĐHBKHN NỘI DUNG 5.1. Bài toán sắp xếp
5.2. Ba thuật toán sắp xếp cơ bản
5.3. Sắp xếp trộn (Merge Sort)
5.4. Sắp xếp nhanh (Quick Sort)
5.5. Sắp xếp vun đống (Heap Sort)
5.6. Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp
5.7. Các phương pháp sắp xếp đặc biệt NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 2
Bộ môn KHMT - ĐHBKHN 5.1. Bài toán sắp xếp
• 5.1.1. Bài toán sắp xếp
• 5.1.2. Giới thiệu sơ lược về các thuật toán sắp xếp NGUYỄN ĐỨC NGHĨA 3
Bộ môn KHMT - ĐHBKHN 5.1.1. Bài toán sắp xếp • Sắp xếp (Sorting)
– Là quá trình tổ chức lại họ các dữ liệu theo thứ tự giảm dần
hoặc tăng dần (ascending or descending order)
• Dữ liệu cần sắp xếp có thể là – Số nguyên (Integers)
– Xâu ký tự (Character strings) – Đối tượng (Objects)
• Khoá sắp xếp (Sort key)
– Là bộ phận của bản ghi xác định thứ tự sắp xếp của bản ghi trong họ các bản ghi.
– Ta cần sắp xếp các bản ghi theo thứ tự của các khoá. NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 4
Bộ môn KHMT - ĐHBKHN 5.1.1. Bài toán sắp xếp • Chú ý:
• Việc sắp xếp tiến hành trực tiếp trên bản ghi đòi hỏi di chuyển
vị trí bản ghi, có thể là thao tác rất tốn kém.
• Vì vậy, người ta thường xây dựng bảng khoá gồm các bản ghi
chỉ có hai trường là (khoá, con trỏ)
– trường "khoá" chứa giá trị khoá,
– trường "con trỏ" để ghi địa chỉ của bản ghi tương ứng.
• Việc sắp xếp theo khoá trên bảng khoá không làm thay đổi
bảng chính, nhưng trình tự các bản ghi trong bảng khoá cho
phép xác định trình tự các bản ghi trong bảng chính. NGUYỄN ĐỨC NGHĨA 5
Bộ môn KHMT - ĐHBKHN 5.1.1. Bài toán sắp xếp
Ta có thể hạn chế xét bài toán sắp xếp dưới dạng sau đây:
Input: Dãy n số A = (a , a , …, a ) 1 2 n
Output: Một hoán vị (sắp xếp lại) (a' ,…, a’ ) của dãy số đã cho 1 n thoả mãn
a’ ≤ … ≤ a’
• Ứng dụng của sắp xếp:
– Quản trị cơ sở dữ liệu (Database management);
– Khoa học và kỹ thuật (Science and engineering);
– Các thuật toán lập lịch (Scheduling algorithms),
• ví dụ thiết kế chương trình dịch, truyền thông,... (compiler design, telecommunication);
– Máy tìm kiếm web (Web search engine);
– và nhiều ứng dụng khác… NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 6
Bộ môn KHMT - ĐHBKHN 5.1.1. Bài toán sắp xếp
• Các loại thuật toán sắp xếp
– Sắp xếp trong (internal sort)
• Đòi hỏi họ dữ liệu được đưa toàn bộ vào bộ nhớ trong của máy tính
– Sắp xếp ngoài (external sort)
• Họ dữ liệu không thể cùng lúc đưa toàn bộ vào bộ nhớ trong,
nhưng có thể đọc vào từng bộ phận từ bộ nhớ ngoài
• Các đặc trưng của một thuật toán sắp xếp:
– Tại chỗ (in place): nếu không gian nhớ phụ mà thuật toán đòi hỏi là
O(1), nghĩa là bị chặn bởi hằng số không phụ thuộc vào độ dài của dãy cần sắp xếp.
– Ổn định (stable): Nếu các phần tử có cùng giá trị vẫn giữ nguyên thứ tự
tương đối của chúng như trước khi sắp xếp. NGUYỄN ĐỨC NGHĨA 7
Bộ môn KHMT - ĐHBKHN 5.1.1. Bài toán sắp xếp
• Có hai phép toán cơ bản mà thuật toán sắp xếp thường phải sử dụng:
– Đổi chỗ (Swap): Thời gian thực hiện là O(1)
void swap( datatype &a, datatype &b){
datatype temp = a; //datatype-kiểu dữ liệu của phần tử a = b; b = temp; }
– So sánh: Compare(a, b) trả lại true nếu a đi trước b trong thứ tự cần
sắp xếp và false nếu trái lại.
• Các thuật toán chỉ sử dụng phép toán so sánh để xác định thứ tự giữa
hai phần tử được gọi là thuật toán sử dụng phép so sánh
(Comparison-based sorting algorithm) NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 8
Bộ môn KHMT - ĐHBKHN
5.1.2. Giới thiệu sơ lược về các thuật toán sắp xếp Simple Fancier Comparison Specialized Handling algorithms: algorithms: lower bound: algorithms: huge data O(n2) O(n log n) (n log n) O(n) sets Insertion sort Heap sort Bucket sort External Selection sort Merge sort Radix sort sorting Bubble sort Quick sort Shell sort … … NGUYỄN ĐỨC NGHĨA 9
Bộ môn KHMT - ĐHBKHN
Các thuật toán sắp xếp dựa trên phép so sánh Name Average Worst Memory Stable Method Bubble sort — O(n²) O(1) Yes Exchanging Cocktail sort — O(n²) O(1) Yes Exchanging Comb sort
O(n log n)
O(n log n) O(1) No Exchanging Gnome sort — O(n²) O(1) Yes Exchanging Selection sort O(n²) O(n²) O(1) No Selection Insertion sort tion Shell sort tion Binary tree sort
O(n log n)
O(n log n) O(n) Yes Insertion Library sort
O(n log n) O(n²) O(n) Yes Insertion Merge sort
O(n log n)
O(n log n) O(n) Yes Merging In-place merge sort
O(n log n)
O(n log n) O(1) Yes Merging Heapsort
O(n log n)
O(n log n) O(1) No Selection Smoothsort —
O(n log n) O(1) No Selection Quicksort
O(n log n) O(n²) O(log n) No Partitioning Introsort
O(n log n)
O(n log n) O(log n) No Hybrid Patience sorting — O(n²) O(n) No Insertion NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 10
Bộ môn KHMT - ĐHBKHN
Các thuật toán sắp xếp không dựa trên phép so sánh Name Average Worst Memory
Stable n << 2k? Pigeonhole sort O(n+2k) O(n+2k) O(2k) Yes Yes Bucket sort O(n·k) O(n²· k) O(n·k) Yes No Counting sort O(n+2k) O(n+2k) O(n+2k) Yes Yes LSD Radix sort O(n·k/s) O(n·k/s) O(n) Yes No MSD Radix sort O(n·k/s)
O(n· (k/s)· 2s)
O((k/s)· 2s) No No Spreadsort
O(n·k/log(n)) O(n· (k-log(n))0.5) O(n) No No Các thông số trong bảng
n - số phần tử cần sắp xếp
k - kích thước mỗi phần tử
s - kích thước bộ phận được sử dụng khi cài đặt.
Nhiều thuật toán được xây dựng dựa trên giả thiết là n << 2k. NGUYỄN ĐỨC NGHĨA 11
Bộ môn KHMT - ĐHBKHN NỘI DUNG 5.1. Bài toán sắp xếp
5.2. Ba thuật toán sắp xếp cơ bản
5.3. Sắp xếp trộn (Merge Sort)
5.4. Sắp xếp nhanh (Quick Sort)
5.5. Sắp xếp vun đống (Heap Sort)
5.6. Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp
5.7. Các phương pháp sắp xếp đặc biệt NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 12
Bộ môn KHMT - ĐHBKHN
5.2. Ba thuật toán sắp xếp cơ bản
• 5.2.1. Sắp xếp chèn (Insertion Sort)
• 5.2.2. Sắp xếp lựa chọn (Selection Sort)
• 5.2.3. Sắp xếp nổi bọt (Bubble Sort) NGUYỄN ĐỨC NGHĨA 13
Bộ môn KHMT - ĐHBKHN
5.2.1. Sắp xếp chèn (Insertion Sort)
Phỏng theo cách làm của người
chơi bài khi cần "chèn" thêm một
con bài vào bộ bài đã được sắp
Để chèn 12, ta cần tạo chỗ cho
nó bởi việc dịch chuyển đầu tiên là 36 và sau đó là 24. NGUYỄN Đ C ỨC N uuD GHĨA uongThanCong.com 14
Bộ môn KHMT - ĐHBKHN
Sắp xếp chèn (Insertion Sort)
Phỏng theo cách làm của người
chơi bài khi cần "chèn" thêm một
con bài vào bộ bài đã được sắp xếp trên tay.
Để chèn 12, ta cần tạo chỗ cho
nó bởi việc dịch chuyển đầu tiên
là 36 và sau đó là 24. NGUYỄN ĐỨC NGHĨA 15
Bộ môn KHMT - ĐHBKHN
Sắp xếp chèn (Insertion Sort)
Phỏng theo cách làm của người
chơi bài khi cần "chèn" thêm một
con bài vào bộ bài đã được sắp
Để chèn 12, ta cần tạo chỗ cho
nó bởi việc dịch chuyển đầu tiên là 36 và sau đó là 24. NGUYỄN ĐỨC NGHĨA C 16 uuDuongThanCong.com
Bộ môn KHMT - ĐHBKHN
Sắp xếp chèn (Insertion Sort)
Phỏng theo cách làm của người
chơi bài khi cần "chèn" thêm một
con bài vào bộ bài đã được sắp xếp trên tay.
Để chèn 12, ta cần tạo chỗ cho
nó bởi việc dịch chuyển đầu tiên là 36 và sau đó là 24. NGUYỄN ĐỨC NGHĨA 17
Bộ môn KHMT - ĐHBKHN Don’t start coding
You must design a working algorithm first. CuuDuongThanCong.com 18
5.2.1. Sắp xếp chèn (Insertion Sort) • Thuật toán:
– Tại bước k = 1, 2, ..., n, đưa phần tử thứ k trong mảng đã cho vào đúng
vị trí trong dãy gồm k phần tử đầu tiên.
– Kết quả là sau bước k, k phần tử đầu tiên là được sắp thứ tự.
void insertionSort(int a[], int array_size) { int i, j, last; Giải thích:
for (i=1; i < array_size; i++) {
• Ở đầu lần lặp i của vòng last = a[i];
"for" ngoài, dữ liệu từ a[0] j = i;
đến a[i-1] là được sắp xếp.
while ((j > 0) && (a[j-1] > last)) {
• Vòng lặp "while" tìm vị trí a[j] = a[j-1];
cho phần tử tiếp theo (last j = j - 1; }
=a[i]) trong dãy gồm i phần a[j] = last; tử đầu tiên. } // end for } // end of isort NGUYỄN ĐỨC NGHĨA 19
Bộ môn KHMT - ĐHBKHN Ví dụ Insertion sort (1) 1 2 3 8 7 9 10 12 23 18 15 16 17 14 1 2 3 7 8 9 10 12 23 18 15 16 17 14 1 2 3 7 8 9 10 12 18 23 15 16 17 14 1 2 1 2 3 7 8 9 10 12 15 18 23 16 17 14 1 2 3 7 8 9 10 12 15 18 16 23 17 14 1 2 3 7 8 9 10 12 15 16 18 23 17 14 NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 20
Bộ môn KHMT - ĐHBKHN Ví dụ Insertion sort (1) 1 2 3 7 8 9 10 12 15 16 18 17 23 14 1 2 3 7 8 9 10 12 15 16 17 18 23 14 1 2 3 7 8 9 10 12 15 16 17 18 14 23 1 2 3 7 8 9 10 12 15 16 17 14 18 23 1 2 3 7 8 9 10 12 15 16 14 17 18 23 1 2 3 7 8 9 10 12 15 14 16 17 18 23 1 2 3 7 8 9 10 12 14 15 16 17 18 23 13 phép đổi chỗ: 20 phép so sánh: NGUYỄN ĐỨC NGHĨA 21
Bộ môn KHMT - ĐHBKHN Ví dụ: Insertion Sort (2) NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 22
Bộ môn KHMT - ĐHBKHN
Các đặc tính của Insertion Sort
• Sắp xếp chèn là tại chỗ và ổn định (In place and Stable)
• Phân tích thời gian tính của thuật toán
– Best Case: 0 hoán đổi, n-1 so sánh (khi dãy đầu vào là đã được sắp)
– Worst Case: n2/2 hoán đổi và so sánh (khi dãy đầu vào có thứ tự
ngược lại với thứ tự cần sắp xếp)
– Average Case: n2/4 hoán đổi và so sánh
• Thuật toán này có thời gian tính trong tình huống tốt nhất là tốt nhất
• Là thuật toán sắp xếp tốt đối với dãy đã gần được sắp xếp
– Nghĩa là mỗi phần tử đã đứng ở vị trí rất gần vị trí trong thứ tự cần sắp xếp 23 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT - ĐHBKHN Thử nghiệm insertion sort #include #include
void insertionSort(int a[], int array_size); int a[1000]; int main() { int i, N;
printf("\nGive n = "); scanf("%i", &N); //seed rand srand(getpid());
//fill array with random integers
for (i = 0; i < N; i++) a[i] = rand();
//perform insertion sort on array insertionSort(a, N);
printf("\nOrdered sequence:\n"); for (i = 0; i < N; i++) printf("%8i", a[i]); getch(); } NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 24
Bộ môn KHMT - ĐHBKHN
5.2.2. Sắp xếp chọn (Selection Sort) • Thuật toán
void swap(int &a,int &b)
– Tìm phần tử nhỏ nhất đưa vào vị trí 1 { int temp = a;
– Tìm phần tử nhỏ tiếp theo đưa vào vị trí 2 a = b; b = temp;
– Tìm phần tử nhỏ tiếp theo đưa vào vị trí 3 } – …
void selectionSort(int a[], int n){ int i, j, min, temp;
for (i = 0; i < n-1; i++) { min = i;
for (j = i+1; j < n; j++){
if (a[j] < a[min]) min = j; } swap(a[i], a[min]); } } NGUYỄN ĐỨC NGHĨA 25
Bộ môn KHMT - ĐHBKHN Selection Sort template
void selection_sort(Elem A[], int n) { for (int i=0; i
int lowindex = i; // Remember its index
for (int j=n-1; j>i; j--) // Find least
if (Comp::lt(A[j], A[lowindex])) lowin swap(A, i, lowindex); } } •
Best case: 0 đổi chỗ (n-1 như trong đoạn mã), n2/2 so sánh. •
Worst case: n - 1 đổi chỗ và n2/2 so sánh. •
Average case: O(n) đổi chỗ và n2/2 so sánh. •
Ưu điểm nổi bật của sắp xếp chọn là số phép đổi chỗ là ít. Điều này là có ý
nghĩa nếu như việc đổi chỗ là tốn kém. NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 26
Bộ môn KHMT - ĐHBKHN Ví dụ: Selection Sort NGUYỄN ĐỨC NGHĨA 27
Bộ môn KHMT - ĐHBKHN
5.2.3. Sắp xếp nổi bọt - Bubble Sort
• Bubble sort là phương pháp sắp xếp đơn giản thường được sử dụng
như ví dụ minh hoạ cho các giáo trình nhập môn lập trình.
• Bắt đầu từ đầu dãy, thuật toán tiến hành so sánh mỗi phần tử với
phần tử đi sau nó và thực hiện đổi chỗ, nếu chúng không theo đúng
thứ tự. Quá trình này sẽ được lặp lại cho đến khi gặp lần duyệt từ đầu dãy đến à tất cả
các phần tử đã đứng đúng vị trí). Cách làm này đã đẩy phần tử lớn
nhất xuống cuối dãy, trong khi đó những phần tử có giá trị nhỏ hơn
được dịch chuyển về đầu dãy.
• Mặc dù thuật toán này là đơn giản, nhưng nó là thuật toán kém hiệu
quả nhất trong ba thuật toán cơ bản trình bày trong mục này. Vì thế
ngoài mục đích giảng dạy, Sắp xếp nổi bọt rất ít khi được sử dụng.
• Giáo sư Owen Astrachan (Computer Science Department, Duke
University) còn đề nghị là không nên giảng dạy về thuật toán này. NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 28
Bộ môn KHMT - ĐHBKHN
5.2.3. Sắp xếp nổi bọt - Bubble Sort
void bubbleSort(int a[], int n){
void swap(int &a,int &b) { int i, j; int temp = a; a = b;
for (i = (n-1); i >= 0; i--) { b = temp;
for (j = 1; j <= i; j++){ } if (a[j-1] > a[j]) swap(a[j-1],a[j]); } } } •
Best case: 0 đổi chỗ, n2/2 so sánh. •
Worst case: n2/2 đổi chỗ và so sánh. •
Average case: n2/4 đổi chỗ và n2/2 so sánh. NGUYỄN ĐỨC NGHĨA 29
Bộ môn KHMT - ĐHBKHN Ví dụ: Bubble Sort 7 4 1 9 2 4 1 7 2 9 1 4 2 7 9 4 7 1 9 2 1 4 7 2 9 1 4 2 7 9 4 1 7 9 2 1 4 7 2 9 1 2 4 7 9 4 1 7 9 4 1 7 2 9 i = 4 i = 3 i = 2 Chú ý:
– Các phần tử được đánh chỉ số bắt đầu từ 0. – n=5 NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 30
Bộ môn KHMT - ĐHBKHN
So sánh ba thuật toán cơ bản NGUYỄN ĐỨC NGHĨA 31
Bộ môn KHMT - ĐHBKHN
Tổng kết 3 thuật toán sắp xếp cơ bản Insertion Bubble Selection Comparisons: Best Case (n) (n2) (n2) Average    Worst Case (n2) (n2) (n2) Swaps Best Case 0 0 (n) Average Case (n2) (n2) (n) Worst Case (n2) (n2) (n) NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 32
Bộ môn KHMT - ĐHBKHN NỘI DUNG 5.1. Bài toán sắp xếp
5.2. Ba thuật toán sắp xếp cơ bản
5.3. Sắp xếp trộn (Merge Sort)
5.4. Sắp xếp nhanh (Quick Sort)
5.5. Sắp xếp vun đống (Heap Sort)
5.6. Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp
5.7. Các phương pháp sắp xếp đặc biệt NGUYỄN ĐỨC NGHĨA 33
Bộ môn KHMT - ĐHBKHN
Sắp xếp trộn (Merge Sort)
Hoà nhập hai dòng xe theo Khoá
[độ liều lĩnh của lái xe].
Lái xe liều lĩnh hơn sẽ vào trước! NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 34
Bộ môn KHMT - ĐHBKHN
Sắp xếp trộn (Merge Sort)
• Bài toán: Cần sắp xếp mảng A[1 .. n]: • Chia (Divide)
– Chia dãy gồm n phần tử cần sắp xếp ra thành 2 dãy, mỗi dãy có n/2 phần tử • Trị (Conquer)
– Sắp xếp mỗi dãy con một cách đệ qui sử dụng sắp xếp trộn
– Khi dãy chỉ còn một phần tử thì trả lại phần tử này • Tổ hợp (Combine)
– Trộn (Merge) hai dãy con được sắp xếp để thu được dãy được sắp xếp
gồm tất cả các phần tử của cả hai dãy con NGUYỄN ĐỨC NGHĨA 35
Bộ môn KHMT - ĐHBKHN Merge Sort p q r MERGE-SORT(A, p, r) 1 2 3 4 5 6 7 8 5 2 4 7 1 3 2 6 if p < r Kiểm tra điều kiện neo then q ← (p MERGE-SORT(A, p, q) Trị (Conquer) MERGE-SORT(A, q + 1, r) Trị (Conquer) MERGE(A, p, q, r) Tổ hợp (Combine) endif
• Lệnh gọi thực hiện thuật toán: MERGE-SORT(A, 1, n) NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 36
Bộ môn KHMT - ĐHBKHN
Trộn (Merge) - Pseudocode MERGE(A, p, q, r) 1. Tính n p q r 1 và n2 1 2 3 4 5 6 7 8
2. Sao n phần tử đầu tiên vào L[1 . . n và 1 1] n2
phần tử tiếp theo vào R[1 . . n 2 4 5 7 1 2 3 6 2] 3. L[n ←  ←  1 + 1] ; R[n2 + 1] n n 4. i ← 1; j ← 1 1 2 5.
for k ← p to r do p q 6. if L[ i ] ≤ R[ j ] L 2 4 5 7  7. then A[k] ← L[ i ] q + 1 r 8. i ←i + 1 R 1 2 3 6  9. else A[k] ← R[ j ] 10. j ← j + 1 NGUYỄN ĐỨC NGHĨA 37
Bộ môn KHMT - ĐHBKHN Thời gian tính của trộn
• Khởi tạo (tạo hai mảng con tạm thời L và R): – (n  1 + n2) = (n)
• Đưa các phần tử vào mảng kết quả (vòng lặp for cuối cùng): – n lần lặp,
• Tổng cộng thời gian của trộn là: – (n) NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 38
Bộ môn KHMT - ĐHBKHN
Thời gian tính của sắp xếp trộn MERGE-SORT Running Time • Chia:
– tính q như là giá trị trung bình của p và r: D(n) = (1) • Trị:
– giải đệ qui 2 bài toán con, mỗi bài toán kích thước n/2  2T (n/2) • Tổ hợp:
– TRỘN (MERGE) trên các mảng con cỡ n phần tử đòi hỏi thời gian (n)  C(n) = (n) (1) nếu n =1 T(n) = 2T(n/2) + (n) nếu n > 1
– Suy ra theo định lý thợ: T(n) = (n log n) NGUYỄN ĐỨC NGHĨA 39
Bộ môn KHMT - ĐHBKHN Ví dụ: Sắp xếp trộn 1 2 3 4 5 6 7 8 8 2 9 4 5 3 1 6 1 2 3 4 5 6 7 8 Divide 8 2 9 4 5 3 1 6 1 2 3 4 5 6 7 8 Divide 8 2 9 4 5 3 1 6 1 2 1 phần tử 8 2 9 4 5 3 1 6 1 2 3 4 5 6 7 8 Merge 2 8 4 9 3 5 1 6 1 2 3 4 5 6 7 8 Merge 2 4 8 9 1 3 5 6 1 2 3 4 5 6 7 8 Kết quả: 1 2 3 4 5 6 8 9 NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 40
Bộ môn KHMT - ĐHBKHN
Cài đặt merge: Trộn A[first..mid] và A[mid+1.. last]
void merge(DataType A[], int first, int mid, int last){
DataType tempA[MAX_SIZE]; // mảng phụ
int first1 = first; int last1 = mid;
int first2 = mid + 1; int last2 = last; int index = first1;
for (; (first1 <= last1) && (first2 <= last2); ++index){
if (A[first1] < A[first2]) {
tempA[index] = A[first1]; ++first1;} else
{ tempA[index] = A[first2]; ++first2;} }
for (; first1 <= last1; ++first1, ++index)
tempA[index] = A[first1]; // sao nốt dãy con 1
for (; first2 <= last2; ++first2, ++index)
tempA[index] = A[first2]; // sao nốt dãy con 2
for (index = first; index <= last; ++index)
A[index] = tempA[index]; // sao trả mảng kết quả } // end merge
Chú ý: DataType: kiểu dữ liệu phần tử mảng. NGUYỄN ĐỨC NGHĨA 41
Bộ môn KHMT - ĐHBKHN Cài đặt mergesort
void mergesort(DataType A[], int first, int last) { if (first < last)
{ // chia thành hai dãy con
int mid = (first + last)/2; // chỉ số điểm giữa
// sắp xếp dãy con trái A[first..mid] mergeso
// sắp xếp dãy con phải A[mid+1..last]
mergesort(A, mid+1, last); // Trộn hai dãy con
merge(A, first, mid, last); } // end if } // end mergesort
Lệnh gọi thực hiện mergesort(A,0,n-1) NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 42
Bộ môn KHMT - ĐHBKHN NỘI DUNG 5.1. Bài toán sắp xếp
5.2. Ba thuật toán sắp xếp cơ bản
5.3. Sắp xếp trộn (Merge Sort)
5.4. Sắp xếp nhanh (Quick Sort)
5.5. Sắp xếp vun đống (Heap Sort)
5.6. Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp
5.7. Các phương pháp sắp xếp đặc biệt NGUYỄN ĐỨC NGHĨA 43
Bộ môn KHMT - ĐHBKHN
5.4. Sắp xếp nhanh (Quick Sort)
• 5.4.1. Sơ đồ tổng quát • 5.4.2. Phép phân đoạn
• 5.4.3. Độ phức tạp của sắp xếp nhanh NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 44
Bộ môn KHMT - ĐHBKHN 5.4.1. Sơ đồ Quick Sort
• Thuật toán sắp xếp nhanh được phát triển bởi
Hoare năm 1960 khi ông đang làm việc cho
hãng máy tính nhỏ Elliott Brothers ở Anh.
• Theo thống kê tính toán, Quick sort (sẽ viết tắt là
QS) là thuật toán sắp xếp nhanh nhất hiện nay.
• QS có thời gian tính trung bình là O(n log n), tuy C.A.R. Hoare
nhiên thời gian tính tồi nhất của nó lại là O(n2). January 11, 1934 ACM Turing Award, 1980
• QS là thuật toán sắp xếp tại chỗ, nhưng nó Photo: 2006 không có tính ổn định.
• QS khá đơn giản về lý thuyết, nhưng lại không dễ cài đặt .
đường nằm ngang cho biết pivot NGUYỄN ĐỨC NGHĨA 45
Bộ môn KHMT - ĐHBKHN
10 Algorithms in 20th Century
có ảnh hưởng sâu rộng đến việc phát triển và ứng dụng của khoa học kỹ thuật …
1946: The Metropolis Algorithm for Monte Carlo
1947: Simplex Method for Linear Programming // Tính toán khoa học
1950: Krylov Subspace Iteration Method 1951: The Dec
1957: The Fortran Optimizing Compiler
1959: QR Algorithm for Computing Eigenvalues
1962: Quicksort Algorithms for Sorting
1965: Fast Fourier Transform // Xử lý ảnh
1977: Integer Relation Detection 1987: Fast Multipole Method
Computing in Science & Engineering, January/February 2000
Science, Vol. 287, No. 5454, p. 799, February 2000 CuuDuongThanCong.com 5.4.1. Sơ đồ Quick Sort •
Quick sort là thuật toán sắp xếp được phát triển dựa trên kỹ thuật chia để trị. •
Thuật toán có thể mô tả đệ qui như sau (có dạng tương tự như merge sort):
1. Neo đệ qui (Base case). Nếu dãy chỉ còn không quá một phần tử thì nó là dãy
được sắp và trả lại ngay dãy này mà không phải làm gì cả. 2. Chia (Divide): •
Chọn một phần tử trong dãy và gọi nó là phần tử chốt p (pivot). •
Chia dãy đã cho ra thành hai dãy con: Dãy con trái (L) gồm những phần tử
không lớn hơn phần tử chốt, còn dãy con phải (R) gồm các phần tử không
nhỏ hơn phần tử chốt. Thao tác này được gọi là "Phân đoạn" (Partition).
3. Trị (Conquer): Lặp lại một cách đệ qui thuật toán đối với hai dãy con L và R.
4. Tổng hợp (Combine): Dãy được sắp xếp là L p R. •
Ngược lại với Merge Sort, trong QS thao tác chia là phức tạp, nhưng thao
tác tổng hợp lại đơn giản. •
Điểm mấu chốt để thực hiện QS chính là thao tác chia. Phụ thuộc vào thuật
toán thực hiện thao tác này mà ta có các dạng QS cụ thể. NGUYỄN ĐỨC NGHĨA 47
Bộ môn KHMT - ĐHBKHN Các bước của QuickSort A Chọn pivot 81 31 57 13 43 75 92 0 65 26 L R Phân đoạn A 0 13 92 26 57 L QuickSort(L) và R QuickSort(R) 0 13 26 31 43 57 65 75 81 92 A 0 13 26 31 43 57 65 75 81 92 OK! A được sắp NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 48
Bộ môn KHMT - ĐHBKHN
Sơ đồ tổng quát của QS
• Sơ đồ tổng quát của QS có thể mô tả như sau:
Quick-Sort(A, Left, Right) 1.
if (Left < Right ) { 2.
Pivot = Partition(A, Left, Right); 3.
Quick-Sort(A, Left, Pivot –1); 4.
Quick-Sort(A, Pivot +1, Right); }
• Hàm Partition(A, Left Right ,
) thực hiện chia A[Left..Right] thành hai
đoạn A[Left..Pivot –1 ] và A[Pivot+1..Right] sao cho: •
Các phần tử trong A[Left..Pivot –1] là nhỏ hơn hoặc bằng A[Pivot] •
Các phần tử trong A[Pivot+1..Right] là lớn hơn hoặc bằng A[Pivot].
• Lệnh gọi thực hiện thuật toán Quick-Sort(A, 1, n) NGUYỄN ĐỨC NGHĨA 49
Bộ môn KHMT - ĐHBKHN
Sơ đồ tổng quát của QS
• Knuth cho rằng khi dãy con chỉ còn một số lượng không lớn phần tử
(theo ông là không quá 9 phần tử) thì ta nên sử dụng các thuật toán
đơn giản để sắp xếp dãy này, chứ không nên tiếp tục chia nhỏ. Thuật
toán trong tình huống như vậy có thể mô tả như sau: Quick-Sort(A, L 1.
if (Right - Left < n ) 0 2.
Insertion_sort(A, Left Right , ); 3. else { 4.
Pivot = Partition(A, Left, Right); 5.
Quick-Sort(A, Left, Pivot –1); 6.
Quick-Sort(A, Pivot +1, Right); } NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 50
Bộ môn KHMT - ĐHBKHN 5.4.2. Thao tác chia
• Trong QS thao tác chia bao gồm 2 công việc:
– Chọn phần tử chốt p.
– Phân đoạn: Chia dãy đã cho ra thành hai dãy con: Dãy con trái (L) gồm
những phần tử không lớn hơn phần tử chốt, còn dãy con phải (R) gồm
các phần tử không nhỏ hơn phần tử chốt.
• Thao tác phân đoạn có thể cài đặt (tại chỗ) với thời gian (n).
• Hiệu quả của thuật toán phụ thuộc rất nhiều vào việc phần tử nào
được chọn làm phần tử chốt:
– Thời gian tính trong tình huống tồi nhất của QS là O(n2). Trường hợp
xấu nhất xảy ra khi danh sách là đã được sắp xếp và phần tử chốt được
chọn là phần tử trái nhất của dãy.
– Nếu phần tử chốt được chọn ngẫu nhiên, thì QS có độ phức tạp tính
toán là O(n log n). NGUYỄN ĐỨC NGHĨA 51
Bộ môn KHMT - ĐHBKHN Chọn phần tử chốt
• Việc chọn phần tử chốt có vai trò quyết định đối với hiệu quả
của thuật toán. Tốt nhất nếu chọn được phần tử chốt là phần tử
đứng giữa trong danh sách được sắp xếp (ta gọi phần tử như
vậy là trung vị/median). Khi đó, sau log n lần phân đoạn ta sẽ 2
đạt tới danh sách với kích thước bằng 1. Tuy nhiên, điều đó rất khó thực hi hần tử chốt sau đây:
– Chọn phần tử trái nhất (đứng đầu) làm phần tử chốt.
– Chọn phần tử phải nhất (đứng cuối) làm phần tử chốt.
– Chọn phần tử đứng giữa danh sách làm phần tử chốt.
– Chọn phần tử trung vị trong 3 phần tử đứng đầu, đứng giữa và đứng
cuối làm phần tử chốt (Knuth).
– Chọn ngẫu nhiên một phần tử làm phần tử chốt. NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 52
Bộ môn KHMT - ĐHBKHN Thuật toán phân đoạn
• Ta xây dựng hàm Partition(a, left, right) làm việc sau:
• Input: Mảng a[left .. right].
• Output: Phân bố lại các phần tử của mảng đầu vào và trả lại
chỉ số jpivot thoả mãn:
– a[jpivot] chứa giá trị ban đầu của a[left],
– a[i] ≤ a[jpivot], với mọi left ≤ i < pivot,
– a[j] ≥ a[jpivot]), với mọi pivot < j ≤ right. NGUYỄN ĐỨC NGHĨA 53
Bộ môn KHMT - ĐHBKHN
Phần tử chốt là phần tử đứng đầu
Partition(a, left, right) pivot được chọn là
i = left; j = right + 1; pivot = a[left]; phần tử đứng đầu
while i < j do i = i + 1;
while i right and a[i] < pivot do i = i + 1; j = j – 1;
while j left and a[j] > pivot do j = j – 1;
swap(a[i] , a[j]);
j là chỉ số (jpivot) cần trả lại,
swap(a[i], a[j]); swap(a[j], a[left]);
do đó cần đổi chỗ a[left] và a[j] return j; i
Sau khi chọn pivot, dịch các con trỏ i và j từ đầu và cuối mảng j
và đổi chỗ cặp phần tử thoả mãn a[i] > pivot và a[j] < pivot NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 54
Bộ môn KHMT - ĐHBKHN Ví dụ Vị trí: 0 1 2 3 4 5 6 7 8 9 Khoá (Key): 9 1 11 17 13 18 4 12 14 5 > > < lần 1while: 9 1 5 17 13 18 4 12 14 11 > < < < lần 2while: 9 1 5 4 13 18 17 12 14 11 < >< < lần 3while: 9 1 5 13 4 18 17 12 14 11 2 lần đổi chỗ: 4 1 5 9 13 18 17 12 14 11
Ví dụ: Phân đoạn với pivot là phần tử đứng đầu Chọn pivot: 7 2 8 3 5 9 6 Phân đoạn: Con trỏ 7 2 8 3 5 9 6 < > 2 nhỏ hơn pivot 7 2 8 3 5 9 6 đổi chỗ 6, 8 7 2 6 3 5 9 8 < > 3,5 nhỏ hơn 9 lớn hơn 7 2 6 3 5 9 8 Kết thúc phân đoạn 7 2 6 3 5 9 8 Đưa pivot vào vị trí 5 2 6 3 7 9 8 C 56 uuDuongThanCong.com
Phần tử chốt là phần tử đứng giữa
PartitionMid(a, left, right); pivot được chọn là
i = left; j = right; pivot = a[(left + right)/2]; phần tử đứng giữa repeat
while a[i] < pivot do i = i + 1;
while pivot < a[j] do j = j - 1;
if i <= j
swap(a[i], a[j]);
i = i + 1; j = j - 1;
until i > j; return j; •
Cài đặt thuật toán phân đoạn trong đó pivot được chọn là phần tử đứng
giữa (Đây cũng là cách cài đặt mà TURBO C lựa chọn). NGUYỄN ĐỨC NGHĨA 57
Bộ môn KHMT - ĐHBKHN
Phần tử chốt là phần tử đứng cuối
int PartitionR(int a[], int p, int r) {
void quickSort(int a[], int p, int r) { int x = a[r]; if (p < r) { int j = p - 1; int q = PartitionR(a, p, r);
for (int i = p; i < r; i++) { quickSort(a, p, q - 1); if (x >= a[i]) quickSort(a, q + 1, r); { j = j + 1 } } a[r] = a[j + 1]; a[j + 1] = x; return (j + 1); } NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 58
Bộ môn KHMT - ĐHBKHN Cài đặt QUICK SORT
void swap(int &a,int &b)
{ int t = a; a = b; b = t; }
int Partition(int a[], int left, int right) { int i, j, pivot;
i = left; j = right + 1; pivot = a[left]; while (i < j) {
i = i + 1; while ((i <= right)&&(a[i] < pivot)) i++;
j--; while ((j >= left)&& (a[j] > pivot)) j--; swap(a[i] , a[j]); }
swap(a[i], a[j]); swap(a[j], a[left]); return j; }
void quick_sort(int a[], int left, int right) { int pivot; if (left < right) {
pivot = Partition(a, left, right);
if (left < pivot) quick_sort(a, left, pivot-1);
if (right > pivot) quick_sort(a, pivot+1, right);} } NGUYỄN ĐỨC NGHĨA 59
Bộ môn KHMT - ĐHBKHN
Cài đặt Quick Sort (dễ đọc hơn?)
int Partition(int a[], int L, int R)
void quick_sort(int a[], int left, int right) { { int i, j, p; int p; i = L; j = R + 1; p = a[L]; if (left < right) while (i < j) { { i = i + 1; ;
while ((i <= R)&&(a[i]

if (left < pivot) j--; quick_sort(a, left, pivot-1);
while ((j >= L)&& (a[j]>p)) j--; if (right > pivot) swap(a[i] , a[j]);
quick_sort(a, pivot+1, right);} } }
swap(a[i], a[j]); swap(a[j], a[L]); return j; } NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 60
Bộ môn KHMT - ĐHBKHN Chương trình DEMO
/* CHUONG TRINH DEMO QUICK SORT */
/* include: stdlib.h; stdio.h; conio.h; process.h; include time.h */
void quick_sort(int a[], int left, int right);
void swap(int &a, int &b);
int Partition(int a[], int left, int right);
int a[1000]; int n; // n - so luong phan tu cua day can sap xep void main() { int i; clrscr();
printf("\n Give n = "); scanf("%i",&n); randomize();
for (i = 0; i < n; i++) a[i] = rand(); // Tao day ngau nhien
printf("\nDay ban dau la: \n");
for (i = 0; i < n; i++) printf("%8i ", a[i]);
quick_sort(a, 0, n-1); // Thuc hien quick sort
printf("\n Day da duoc sap xep.\n");
for (i = 0; i < n; i++) printf("%8i ", a[i]); a[n]=32767; for (i = 0; i < n; i++)
if (a[i]>a[i+1]) {printf(" ??????? Loi o vi tri: %6i ", i); getch(); }
printf("\n Correct!"); getch(); } NGUYỄN ĐỨC NGHĨA 61
Bộ môn KHMT - ĐHBKHN
30 19 24 28 41 34 15 43 20 12 36
T(q) O(n)
T(n-q) 19 24 28 15 20 12 30 41 34 43 36 15 12 19 24 28 20 34 36 41 43 12 15 20 24 28 34 36 12 15 20 24 28 34 36 12 15 19 20 24 28 34 36 41 43 O(1)
12 15 19 20 24 28 30 34 36 41 43
T (0)  T (1)  1
T (n)  T (q) T (n CuuD  q)
uongTha  O (n) nCong.com  O(1) 62
Thời gian tính của Quick-Sort •
Thời gian tính của Quick-Sort phụ thuộc vào việc phép phân chia là
cân bằng (balanced) hay không cân bằng (unbalanced), và điều
đó lại phụ thuộc vào việc phần tử nào được chọn làm chốt. 1.
Phân đoạn không cân bằng: thực sự không có phần nào cả, do
đó một bài toán con có kích thước n – 1 còn bài toán kia có kích thước 0. 2.
Phân đoạn hoàn hảo (Perfect partition): việc phân đoạn luôn
được thực hiện dưới dạng phân đôi, như vậy mỗi bài toán con
có kích thước cỡ n/2. 3.
Phân đoạn cân bằng: việc phân đoạn được thực hiện ở đâu đó
quanh điểm giữa, nghĩa là một bài toán con có kích thước n – k
còn bài toán kia có kích thước k.
Ta sẽ xét từng tình huống! NGUYỄN ĐỨC NGHĨA 63
Bộ môn KHMT - ĐHBKHN
Phân đoạn không cân bằng (Unbalanced partition) Công thức đệ qui là:
T(n) = T(n – 1) + T(0) + Θ(n) T ) 0 (  T ) 1 (  1 T n ( ) T n (  ) 1 n T (n  ) 1  T (n  ) 2  (n  ) 1 n T(n  ) 2  T(n  ) 3  (n  ) 2 1 ... n – 1 T ( ) 2  T ) 1 (  (2) 1 n – 2 T n ( )  T ) 1 (  n i i2 1 2O( 2 n ) 1 1 NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 64
Bộ môn KHMT - ĐHBKHN
Khi phần tử chốt được chọn là phần tử đứng đầu:
Tình huống tồi nhất xảy ra khi dãy đầu vào là đã được sắp xếp 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 2 3 4 5 6 7 8 9 10 11 3 4 5 6 7 8 9 10 11 4 5 6 7 8 9 10 11 T (0)  T ) 1 (  1 T n ( )  T n (  ) 1  n 65
Phân đoạn hoàn hảo - Perfect partition Công thức đệ qui:
T(n) = T(n/2) + T(n/2) + Θ(n)
T n  T 2 n  
T n   n log n It's Best Case! Theo định lý thợ ! NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 66
Bộ môn KHMT - ĐHBKHN
Phân tích tình huống tồi nhất Ta có công thức đệ qui:
T n   max T (q) T n q    n  1 qn
Mệnh đề: T(n) ≤ cn2 = O(n2)
Chứng minh: Qui nạp theo n.
• Base case: Rõ ràng bổ đề đúng cho n=1.
• Induction step: Giả sử bổ đề đúng với mọi n < n’, ta chứng minh
nó đúng cho n’. Ta có:
T n'  max T(q)  T n' q   n' 1 qn ' 2 2  cq  ( c n' ) qdn' (giả thiết qui nạp) 2 2
 2cq c(n ')  2cqn' dn' NGUYỄN ĐỨC NGHĨA 67
Bộ môn KHMT - ĐHBKHN
Phân tích tình huống tồi nhất
• Để hoàn thành chứng minh, ta cần chỉ ra rằng
2cq2 + c(n')2  2cqn' +dn' ≤ c(n')2,
• và bất đẳng thức này là tương đương với:
dn' ≤ 2cq(n'q)
• Do q(n’-q) có thể
xét hai tình huống: q < n/2 và n ≥ q ≥ n/2), nên ta có thể chọn c
đủ lớn để bất đẳng thức cuối cùng là đúng.
• Mệnh đề được chứng minh.
• Do trong tình huống phân đoạn không cân bằng QS có thời
gian tính Θ(n2), nên từ mệnh đề suy ra thời gian tính trong tình
huống tồi nhất của QS là O(n2). NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 68
Bộ môn KHMT - ĐHBKHN
Thời gian tính trung bình của QS QuickSort Average Case
• Giả sử rằng pivot được chọn ngẫu nhiên trong số các
phần tử của dãy đầu vào
• Tất cả các tình huống sau đây là đồng khả năng:
– Pivot là phần tử nhỏ nhất trong dãy
– Pivot là phần tử nhỏ nhì trong dãy
– Pivot là phần tử nhỏ thứ ba trong dãy …
– Pivot là phần tử lớn nhất trong dãy
• Điều đó cũng là đúng khi pivot luôn được chọn là phần
tử đầu tiên, với giả thiết là dãy đầu vào là hoàn toàn ngẫu nhiên 69
Thời gian tính trung bình của QS QuickSort Average Case
• Thời gian tính trung bình =
 (thời gian phân đoạn kích thước i)(xác suất phân đoạn có kích thước i)
• Trong tình huống ngẫu nhiên, tất cả các kích thước là đồng khả
năng - xác suất chính là 1/N
T (N )  T (i)  T (N i  1) cN N 1
E(T( N))  (1/ N) 
E(T( )i)  E(T(N i 1  ))  cNi0 N 1 
E(T( N))  (2 / N)  E(T( )i) cN i 0
• Giải công thức đệ qui này ta thu được
E(T(N)) = O(N log N). C 70 uuDuongThanCong.com NỘI DUNG 5.1. Bài toán sắp xếp
5.2. Ba thuật toán sắp xếp cơ bản
5.3. Sắp xếp trộn (Merge Sort)
5.4. Sắp xếp nhanh (Quick Sort)
5.5. Sắp xếp vun đống (Heap Sort)
5.6. Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp
5.7. Các phương pháp sắp xếp đặc biệt NGUYỄN ĐỨC NGHĨA 71
Bộ môn KHMT - ĐHBKHN
5.5. Sắp xếp vun đống (Heap Sort)
5.5.1. Cấu trúc dữ liệu đống (heap) 5.5.2. Sắp xếp vun đống
5.5.3. Hàng đợi có ưu tiên (priority queue) NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 72
Bộ môn KHMT - ĐHBKHN
5.5.1. The Heap Data Structure •
Định nghĩa: Đống (heap) là cây nhị phân gần hoàn chỉnh có hai tính chất sau:
– Tính cấu trúc (Structural property): tất cả các mức đều là đầy, ngoại
trừ mức cuối cùng, mức cuối được điền từ trái sang phải.
– Tính có thứ tự hay tính chất đống (heap property): với mỗi nút x Parent(x) ≥ x.
• Cây được cài đặt bởi mảng A[i] có độ dài length[A]. Số lượng
phần tử là heapsize[A] 8
Từ tính chất đống suy ra:
“Gốc chứa phần tử lớn nhất của đống!” 7 4 5 2 Như vậy có thể nói:
Đống là cây nhị phân được điền theo thứ tự Heap NGUYỄN ĐỨC NGHĨA 73
Bộ môn KHMT - ĐHBKHN
Biểu diễn đống bởi mảng
• Đống có thể cất giữ trong mảng A. – Gốc của cây là A[1]
– Con trái của A[i] là A[2*i]
– Con phải của A[i] là A[2*i + 1] – Cha của A[i – Heapsize[A] ≤ length[A]
• Các phần tử trong mảng con
A[(n/2+1) .. n] là các lá parent(i) = i/2 left-child(i) = 2i right-child(i) = 2i +1 NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 74
Bộ môn KHMT - ĐHBKHN Ví dụ đống 1 parent(i) = i/2 16 0 left-child(i) = 2i right-child(i) = 2i +1 2 3 14 10 1 4 5 6 7 2 8 7 9 3 8 9 10 3 2 4 1 1 2 3 4 5 6 7 8 9 10 16 14 10 8 7 9 3 2 4 1 NGUYỄN ĐỨC NGHĨA 75
Bộ môn KHMT - ĐHBKHN Hai dạng đống
• Đống max - Max-heaps (Phần tử lớn nhất ở gốc), có tính chất max-heap:
– với mọi nút i, ngoại trừ gốc: A[parent(i)] ≥ A[i]
• Đống min - Min-heaps (phần tử nhỏ nhất ở gốc), có tính chất min-heap:
– với mọi nút i, ngoại trừ gốc: A[parent(i)] ≤ A[i]
• Phần dưới đây ta sẽ chỉ xét đống max (max-heap). Đống min
được xét hoàn toàn tương tự. NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 76
Bộ môn KHMT - ĐHBKHN Bổ sung và loại bỏ nút Adding/Deleting Nodes
• Nút mới được bổ sung vào mức đáy (từ trái sang phải)
• Các nút được loại bỏ khỏi mức đáy (từ phải sang trái) NGUYỄN ĐỨC NGHĨA 77
Bộ môn KHMT - ĐHBKHN
Các phép toán đối với đống Operations on Heaps
• Khôi phục tính chất max-heap (Vun lại đống) – Max-Heapify
• Tạo max-heap từ một mảng không được sắp xếp – Build-M NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 78
Bộ môn KHMT - ĐHBKHN
Khôi phục tính chất đống •
Giả sử có nút i với giá trị bé hơn con của nó –
Giả thiết là: Cây con trái và Cây con phải của i đều là max-heaps •
Để loại bỏ sự vi phạm này ta tiến hành như sau: –
Đổi chỗ với con lớn hơn – Di chuyển xuống theo cây –
Tiếp tục quá trình cho đến khi nút không còn bé hơn con NGUYỄN ĐỨC NGHĨA 79
Bộ môn KHMT - ĐHBKHN Ví dụ A[2]  A[4]
A[2] vi phạm tính chất đống A[4] vi phạm A[4]  A[9]
Tính chất đống được khôi phục NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 80
Bộ môn KHMT - ĐHBKHN
Thuật toán khôi phục tính chất đống • Giả thiết:
Max-Heapify(A, i, n)
// n = heapsize[A] – Cả hai cây con trái
và phải của i đều là 1.
l left-child(i) max-heaps 2.
r right-child(i) – A[i] có thể bé hơn 3.
if (l ≤ n) and (A[l] > A[i]) các con của nó 4.
then largest l 5.
else largest i 6.
if (r ≤ n) and (A[r] > A[largest]) 7.
then largest r 8.
if largest != i 9.
then Exchange(A[i],A[largest])
10. Max-Heapify(A,largest,n) NGUYỄN ĐỨC NGHĨA 81
Bộ môn KHMT - ĐHBKHN
Thời gian tính của MAX-HEAPIFY • Ta nhận thấy rằng:
– Từ nút i phải di chuyển theo đuờng đi xuống phía dưới của cây. Độ dài
của đường đi này không vượt quá độ dài đường đi từ gốc đến lá, nghĩa
là khôngvượt quá h. – Ở mỗi mứ
– Do đó tổng số phép so sánh không vượt quá 2h.
– Vậy, thời gian tính là O(h) hay O(log n).
• Kết luận: Thời gian tính của MAX-HEAPIFY là O(log n)
• Nếu viết trong ngôn ngữ chiều cao của đống, thì thời gian này là O(h) NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 82
Bộ môn KHMT - ĐHBKHN
Xây dựng đống (Building a Heap)
• Biến đổi mảng A[1 … n] thành max-heap (n = length[A])
• Vì các phần tử của mảng con A[(n/2+1) .. n] là các lá
• Do đó để tạo đống ta chỉ cần áp dụng MAX-HEAPIFY đối với
các phần tử từ 1 đến n/2 Alg: Build-Max-Heap(A) 1 4 1. n = length[A] 2 3 1 3 2.
for i ← n/2 downto 1 4 5 6 7 2 16 9 10 3.
do Max-Heappify(A, i, n) 8 9 10 14 8 7 A: 4 1 3 2 16 9 10 14 8 7 NGUYỄN ĐỨC NGHĨA 83
Bộ môn KHMT - ĐHBKHN Ví dụ: A: 4 1 3 2 16 9 10 14 8 7 i = 5 i = 4 i = 3 1 1 1 4 4 4 2 3 2 3 2 3 1 3 1 3 1 3 4 5 6 7 4 5 6 7 4 5 6 7 2 16 9 10 2 16 9 10 14 16 9 10 8 9 10 8 9 10 8 9 10 14 8 7 i = 2 i = 1 1 1 1 4 4 16 2 3 2 3 2 3 1 10 16 10 14 10 4 5 6 7 4 5 6 7 4 5 6 7 14 16 9 3 14 7 9 3 8 7 9 3 8 9 10 8 9 10 8 9 10 2 8 7 2 8 1 2 4 1 NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 84
Bộ môn KHMT - ĐHBKHN
Ví dụ: Build-Min-Heap size = 26 87 43 68 6 77 33 9 11 19 99 6 23 89 2 14 1 5 27 35 7 42 12 71 3 67 22
Ví dụ: Build-Min-Heap size = 26 87 43 68 6 77 33 9 13 11 19 99 6 23 89 2 14 Bắt đầu từ phần 1 5 27 35 7 42 12 71 3 67 22 tử ở vị trí n/2 CuuDuongThanCong.com Build-Min-Heap size = 26 87 43 68 6 77 33 9 13 11 19 99 6 23 89 2 14 1 5 27 35 7 42 12 71 3 67 22 Vun lại đống Build-Min-Heap size = 26 87 43 68 6 77 33 9 13 11 19 99 6 23 22 2 14 1 5 27 35 7 42 12 71 3 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 87 43 68 6 77 33 9 13 11 19 99 6 23 22 2 14 1 5 27 35 7 42 12 71 3 67 89 Vun lại đống Build-Min-Heap size = 26 87 43 68 6 77 33 9 13 11 19 99 6 3 22 2 14 1 5 27 35 7 42 12 71 23 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 87 43 68 6 77 33 9 13 11 19 99 6 3 22 2 14 1 5 27 35 7 42 12 71 23 67 89 Vun lại đống Build-Min-Heap size = 26 87 43 68 6 77 33 9 13 11 19 99 6 3 22 2 14 1 5 27 35 7 42 12 71 23 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 87 43 68 6 77 33 9 13 11 19 7 6 3 22 2 14 1 5 27 35 99 42 12 71 23 67 89 Vun lại đống Build-Min-Heap size = 26 87 43 68 6 77 33 9 13 11 19 7 6 3 22 2 14 1 5 27 35 99 42 12 71 23 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 87 43 68 6 77 33 9 13 11 19 7 6 3 22 2 14 1 5 27 35 99 42 12 71 23 67 89 Vun lại đống Build-Min-Heap size = 26 87 43 68 6 77 33 9 13 1 19 7 6 3 22 2 14 11 5 27 35 99 42 12 71 23 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 87 43 68 6 77 33 9 13 1 19 7 6 3 22 2 14 11 5 27 35 99 42 12 71 23 67 89 Vun lại đống Build-Min-Heap size = 26 87 43 68 6 77 33 2 13 1 19 7 6 3 22 9 14 11 5 27 35 99 42 12 71 23 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 87 43 68 6 77 33 2 13 1 19 7 6 3 22 9 14 11 5 27 35 99 42 12 71 23 67 89 Vun lại đống Build-Min-Heap size = 26 87 43 68 6 77 3 2 13 1 19 7 6 33 22 9 14 11 5 27 35 99 42 12 71 23 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 87 43 68 6 77 3 2 13 1 19 7 6 33 22 9 14 11 5 27 35 99 42 12 71 23 67 89 Vun lại đống Build-Min-Heap size = 26 87 43 68 6 77 3 2 13 1 19 7 6 23 22 9 14 11 5 27 35 99 42 12 71 33 67 89 CuuDuongThanCong.com Build-Min-Heap size = 26 87 43 68 6 77 3 2 13 1 19 7 6 23 22 9 14 11 5 27 35 99 42 12 71 33 67 89 Vun lại đống Build-Min-Heap size = 26 87 43 68 6 6 3 2 13 1 19 7 77 23 22 9 14 11 5 27 35 99 42 12 71 33 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 87 43 68 6 6 3 2 13 1 19 7 77 23 22 9 14 11 5 27 35 99 42 12 71 33 67 89 Vun lại đống Build-Min-Heap size = 26 87 43 68 6 6 3 2 13 1 19 7 12 23 22 9 14 11 5 27 35 99 42 77 71 33 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 87 43 68 6 6 3 2 13 1 19 7 12 23 22 9 14 11 5 27 35 99 42 77 71 33 67 89 Vun lại đống Build-Min-Heap size = 26 87 43 68 1 6 3 2 13 6 19 7 12 23 22 9 14 11 5 27 35 99 42 77 71 33 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 87 43 68 1 6 3 2 13 6 19 7 12 23 22 9 14 11 5 27 35 99 42 77 71 33 67 89 Vun lại đống Build-Min-Heap size = 26 87 43 68 1 6 3 2 13 5 19 7 12 23 22 9 14 11 6 27 35 99 42 77 71 33 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 87 43 68 1 6 3 2 13 5 19 7 12 23 22 9 14 11 6 27 35 99 42 77 71 33 67 89 Vun lại đống Build-Min-Heap size = 26 87 43 2 1 6 3 68 13 5 19 7 12 23 22 9 14 11 6 27 35 99 42 77 71 33 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 87 43 2 1 6 3 68 13 5 19 7 12 23 22 9 14 11 6 27 35 99 42 77 71 33 67 89 Vun lại đống Build-Min-Heap size = 26 87 43 2 1 6 3 9 13 5 19 7 12 23 22 68 14 11 6 27 35 99 42 77 71 33 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 87 43 2 1 6 3 9 13 5 19 7 12 23 22 68 14 11 6 27 35 99 42 77 71 33 67 89 Vun lại đống Build-Min-Heap size = 26 87 1 2 43 6 3 9 13 5 19 7 12 23 22 68 14 11 6 27 35 99 42 77 71 33 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 87 1 2 43 6 3 9 13 5 19 7 12 23 22 68 14 11 6 27 35 99 42 77 71 33 67 89 Vun lại đống Build-Min-Heap size = 26 87 1 2 5 6 3 9 13 43 19 7 12 23 22 68 14 11 6 27 35 99 42 77 71 33 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 87 1 2 5 6 3 9 13 43 19 7 12 23 22 68 14 11 6 27 35 99 42 77 71 33 67 89 Vun lại đống Build-Min-Heap size = 26 87 1 2 5 6 3 9 13 6 19 7 12 23 22 68 14 11 43 27 35 99 42 77 71 33 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 87 1 2 5 6 3 9 13 6 19 7 12 23 22 68 14 11 43 27 35 99 42 77 71 33 67 89 Vun lại đống Build-Min-Heap size = 26 1 87 2 5 6 3 9 13 6 19 7 12 23 22 68 14 11 43 27 35 99 42 77 71 33 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 1 87 2 5 6 3 9 13 6 19 7 12 23 22 68 14 11 43 27 35 99 42 77 71 33 67 89 Vun lại đống Build-Min-Heap size = 26 1 5 2 87 6 3 9 13 6 19 7 12 23 22 68 14 11 43 27 35 99 42 77 71 33 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 1 5 2 87 6 3 9 13 6 19 7 12 23 22 68 14 11 43 27 35 99 42 77 71 33 67 89 Vun lại đống Build-Min-Heap size = 26 1 5 2 6 6 3 9 13 87 19 7 12 23 22 68 14 11 43 27 35 99 42 77 71 33 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 1 5 2 5 6 3 9 13 87 19 7 12 23 22 68 14 11 43 27 35 99 42 77 71 33 67 89 Vun lại đống Build-Min-Heap size = 26 1 5 2 5 6 3 9 13 11 19 7 12 23 22 68 14 87 43 27 35 99 42 77 71 33 67 89 Vun lại đống CuuDuongThanCong.com Build-Min-Heap size = 26 1 5 2 5 6 3 9 13 11 19 7 12 23 22 68 14 87 43 27 35 99 42 77 71 33 67 89 Kết thúc
Thời gian tính của Buil-Max-Heap Alg: Build-Max-Heap(A) 1. n = length[A] 2.
for i ← n/2 downto 1 O(n) 3. do
 Thời gian tính là: O(n log n)
• Đánh giá này là không sát ! NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 130
Bộ môn KHMT - ĐHBKHN
Thời gian tính của Buid-Max-Heap
• Heapify đòi hỏi thời gian O(h)  chi phí của Heapify ở nút i
là tỷ lệ với chiều cao của nút i trên cây h hT (n)  n h   2i (h
i)  O(n) i i i0 i0 Chiều cao Mức Số lượng nút h = 3 (log n) 0 i = 0 20 h = 2 i = 1 21 1 h = 1 i = 2 2 22 h = 0 i = 3 (log n) 3 23
h = h – i chiều cao của đống gốc tại mức i i n = 2i số lượng nút ở mức i i NGUYỄN ĐỨC NGHĨA 131
Bộ môn KHMT - ĐHBKHN
Thời gian tính của Build-Max-Heap h T n ( )  n h
(Chi phí Heapify tại mức i) × (số lượng nút trên mức này) i i i0 h i
 2 hi Thay giá trị của n và h tính được ở trên i i i 0 h h i  
Nhân cả tử và mẫu với 2 và viết 2 1 h i  0 2 i hk h 2  k Đổi biến: 2 k = h - i k 0    k n
Thay tổng hữu hạn bởi tổng vô hạn k k 2 0 và h = log nO(n) Tổng trên là nhỏ hơn 2
Thời gian tính của Build-Max-Heap: T(n) = O(n) NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 132
Bộ môn KHMT - ĐHBKHN
5.5.2. Sắp xếp vun đống - Heapsort
• Sử dụng đống ta có thể phát triển thuật toán sắp xếp mảng.
• Sơ đồ của thuật toán được trình bày như sau:
– Tạo đống max-heap từ mảng đã cho
– Đổi chỗ gốc (phần tử lớn nhất) với phần tử cuối cùng trong mảng
– Loại bỏ nút cuối cùng bằng cách giảm kích thước của đống đi 1
– Thực hiện Max-Heapify đối với gốc mới
– Lặp lại quá trình cho đến khi đống chỉ còn 1 nút NGUYỄN ĐỨC NGHĨA 133
Bộ môn KHMT - ĐHBKHN Ví dụ: A=[7, 4, 3, 1, 2] Max-Heapyfy(A, 1 1, 2) Max-Heapyfy(A, 1, 1) NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 134
Bộ môn KHMT - ĐHBKHN
Algorithm: HeapSort(A) 1. Build-Max-Heap(A) O(n) 2.
for i ← length[A] downto 2 3.
do exchange A[1] ↔ A[i] n-1 lần lặp 4. Max-Heapify(A, 1, i - 1) O(log n) •
Thời gian tính: O(n log n) •
Có thể chứng minh thời gian tính là Θ(n log n) NGUYỄN ĐỨC NGHĨA 135
Bộ môn KHMT - ĐHBKHN
5.5.3. Hàng đợi có ưu tiên - Priority Queues
• Cho tập S thường xuyên biến động, mỗi phần tử x được gán với
một giá trị gọi là khoá (hay độ ưu tiên). Cần một cấu trúc dữ
liệu hỗ trợ hiệu quả các thao tác chính sau:
– Insert(S, x) – Bổ sung phần tử x vào S – Max(S) – t
– Extract-Max(S) – loại bỏ và trả lại phần tử lớn nhất
– Increase-Key(S,x,k) – tăng khoá của x thành k
• Cấu trúc dữ liệu đáp ứng các yêu cầu đó là hàng đợi có ưu tiên. •
Hàng đợi có ưu tiên có thể tổ chức nhờ sử dụng cấu trúc dữ
liệu đống để cất giữ các khoá.
• Chú ý: Có thể thay "max" bởi "min" . NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 136
Bộ môn KHMT - ĐHBKHN
Các phép toán đối với hàng đợi có ưu tiên
Operations on Priority Queues
• Hàng đợi có ưu tiên (max) có các phép toán cơ bản sau:
– Insert(S, x): bổ sung phần tử x vào tập S
– Extract-Max(S): loại bỏ và trả lại phần tử của S với khoá lớn nhất
– Maximum(S): trả lại phần tử của S với khoá lớn nhất
– Increase-Key(S, x, k): tăng giá trị của khoá của phần tử x
lên thành k (Giả sử k ≥ khoá hiện tại của x) NGUYỄN ĐỨC NGHĨA 137
Bộ môn KHMT - ĐHBKHN
Các phép toán đối với hàng đợi có ưu tiên (min)
Operations on Priority Queues
• Hàng đợi có ưu tiên (min) có các phép toán cơ bản sau:
– Insert(S, x): bổ sung phần tử x vào tập S
– Extract-Min(S): loại bỏ và trả lại phần tử của S với khoá nhỏ nhất
– Minimum(S): trả lại phần tử của S với khoá nhỏ nhất
– Deacrease-Key(S, x, k): giảm giá trị của khoá của phần tử
x xuống còn k (Giả sử k  khoá hiện tại của x) NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 138
Bộ môn KHMT - ĐHBKHN
Phép toán HEAP-MAXIMUM
Chức năng: Trả lại phần tử lớn nhất của đống Alg: Heap-Maximum(A) 1. return A[1] Thời gian tính: O(1) Heap A: Heap-Maximum(A) trả lại 7 NGUYỄN ĐỨC NGHĨA 139
Bộ môn KHMT - ĐHBKHN Heap-Extract-Max
Chức năng: Trả lại phần tử lớn nhất và loại bỏ nó khỏi đống Thuật toán: –
Hoán đổi gốc với phần tử cuối cùng –
Giảm kích thước của đống đi 1 – Gọi Ma Đống A:
Gốc là phần tử lớn nhất NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 140
Bộ môn KHMT - ĐHBKHN
Ví dụ: Heap-Extract-Max 16 1 14 10 max = 16 14 10 8 7 9 3 8 7 9 3 2 4 1 2 4
Kích thước đống giảm đi 1 14
Thực hiện Max-Heapify(A, 1, n-1) 8 10 4 7 9 3 2 1 NGUYỄN ĐỨC NGHĨA 141
Bộ môn KHMT - ĐHBKHN Heap-Extract-Max
Alg: Heap-Extract-Max(A, n) 1. if n < 1 2. then e 3. max ← A[1] 4. A[1] ← A[n] 5.
Max-Heapify(A, 1, n-1) // Vun lại đống 6. return max
Thời gian tính: O(log n) NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 142
Bộ môn KHMT - ĐHBKHN Heap-Increase-Key
• Chức năng: Tăng giá trị khoá của phần tử i trong đống • Thuật toán:
– Tăng khoá của A[i] thành giá trị mới
– Nếu tính chất max-heap bị vi phạm: di chuyển theo đường
đến gốc để tìm chỗ thích hợp cho khoá mới bị tăng này 16 14 10 8 7 9 3 i Key [i] ← 15 2 4 1 NGUYỄN ĐỨC NGHĨA 143
Bộ môn KHMT - ĐHBKHN
Ví dụ: Heap-Increase-Key 16 16 14 10 14 10 8 7 9 3 8 7 9 3 i i 2 4 1 K ey [i ] ← 15 16 16 i 14 10 15 10 i 15 7 9 3 14 7 9 3 2 8 1 2 8 1 NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 144
Bộ môn KHMT - ĐHBKHN Heap-Increase-Key
Alg: Heap-Increase-Key(A, i, key) 1. if key < A[i] 2.
then error “khoá mới nhỏ hơn khoá hiện tại” 3. A[i] ← key 4.
while i > 1 and A[parent(i)] < A[i] 5.
do hoán đổi A[i] ↔ A[parent(i)] 16 6. i ← parent(i) 14 10 •
Thời gian tính: O(log n) 8 7 9 3 i 2 4 1 Key [i] ← 15 NGUYỄN ĐỨC NGHĨA 145
Bộ môn KHMT - ĐHBKHN
Ví dụ: Heap-Increase-Key (1) 1 16 2 3 14 10 4 5 6 7 8 7 9 3 8 9 10 2 4 1 increase 4 to 15 NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 146
Bộ môn KHMT - ĐHBKHN
Ví dụ: Heap-Increase-Key (2) 1 16 2 3 14 10 4 5 6 7 8 7 9 3 8 9 10 2 15 1 thay 4 bởi 15 NGUYỄN ĐỨC NGHĨA 147
Bộ môn KHMT - ĐHBKHN
Ví dụ: Heap-Increase-Key (3) 1 16 2 3 4 5 6 7 15 7 9 3 8 9 10 2 8 1
đi ngược lên để sửa vi phạm NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 148
Bộ môn KHMT - ĐHBKHN
Ví dụ: Heap-Increase-Key (4) 1 16 2 3 15 10 4 5 6 7 14 7 9 3 8 9 10 2 8 1 đã đặt đúng vị trí NGUYỄN ĐỨC NGHĨA 149
Bộ môn KHMT - ĐHBKHN Max-Heap-Insert
• Chức năng: Chèn một phần tử mới vào max-heap 16 • Thuật toán: 14 10
– Mở rộng max-heap với một nút 8 7 9 3 mới có khoá là -
– Gọi Heap-Increase-Key để tăng 16
khoá của nút mới này thành giá 14 10
trị của phần tử mới và vun lại 8 7 9 3 đống 2 4 1 15 NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 150
Bộ môn KHMT - ĐHBKHN
Ví dụ: Max-Heap-Insert Chèn giá trị 15: Tăng khoá thành 15 - Bắt đầu với -
Gọi Heap-Increase-Key với A[11] = 15 16 16 14 10 14 10 8 7 9 3 8 7 9 3 2 4 1 - 2 4 1 15 16 Vun lại đống 16 với phần tử 14 10 mới bổ sung 15 10 8 15 9 3 8 14 9 3 2 4 1 7 2 4 1 7 NGUYỄN ĐỨC NGHĨA 151
Bộ môn KHMT - ĐHBKHN Max-Heap-Insert
Alg: Max-Heap-Insert(A, key, n) 1. heap-size[A] ← n + 1 2. A[n + 1] ← - 3.
Heap-Increase-Key(A, n + 1, key) 14 10 8 7 9 3 2 4 1 -
Running time: O(log n) NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 152
Bộ môn KHMT - ĐHBKHN Tổng kết
• Chúng ta có thể thực hiện các phép toán sau đây với đống: Phép toán Thời gian tính – Max-Heapify O(log n) – Build-Max-Heap O(n) – Heap-Sort
O(n log n) – Max-Heap-Insert O(log n) – Heap-Extract-Max O(log n) – Heap-Increase-Key O(log n) – Heap-Maximum O(1) NGUYỄN ĐỨC NGHĨA 153
Bộ môn KHMT - ĐHBKHN Câu hỏi
• Giả sử các số trong max-heap là phân biệt, phần tử lớn thứ hai nằm ở đâu?
• Ans: Con lớn hơn trong hai con của gốc NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 154
Bộ môn KHMT - ĐHBKHN
Mã Huffman: Thuật toán procedure Huffman(C, f); begin n  |C|; Q  C;
for i:=1 to n-1 do begin
x, y  2 chữ cái có tần suất nhỏ nhất trong Q; (* Thao tác 1 *)
Tạo nút p với hai con x, y; f(p) := f(x) + f(y); Q  Q \ {x, y}  {p} (* Thao tác 2 *) end; end; • Cà C i iđặt trự r c c titếp: – Thao tác 1: O(n) – Thao tác 2: O(1) =>
= Thời igian O(n2) 1/28/2013
Mã Huffman: Thuật toán procedure Huffman(C, f); begin n  |C|; Q  C;
for i:=1 to n-1 do begin
x, y  2 chữ cái có tần suất nhỏ nhất trong Q; (* Thao tác 1 *) Tạo nút p f(p) := f(x) + f(y); Q  Q \ {x, y}  {p} (* Thao tác 2 *) end; end; • Cà
C i iđặt sử dụng priority queue Q:
– Thao tác 1 và 2: O(log n) =>
= Thời igian O(n log n ) 1/28/2013 CuuDuongThanCong.com
Có thể sắp xếp nhanh đến mức độ nào?
• Heapsort, Mergesort, và Quicksort có thời gian O(n log n) là
các thuật toán có thời gian tính tốt nhất trong các thuật toán trình bày ở trên
• Liệu có thể phát triển được thuật toán tốt hơn không?
• Câu trả lời là: "Không, nếu như phép toán cơ bản là phép so sánh". NGUYỄN ĐỨC NGHĨA 157
Bộ môn KHMT - ĐHBKHN NỘI DUNG 5.1. Bài toán sắp xếp
5.2. Ba thuật toán sắp xếp cơ bản
5.3. Sắp xếp trộn (Merge Sort)
5.4. Sắp xếp nhanh (Quick Sort)
5.5. Sắp xếp vun đống (Heap Sort)
5.6. Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp
5.7. Các phương pháp sắp xếp đặc biệt NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 158
Bộ môn KHMT - ĐHBKHN Cây quyết định
• Cây quyết định là cây nhị phân thoả mãn:
– Mỗi nút  một phép so sánh "a < b"
• cũng có thể coi tương ứng với một không gian con các trình tự
– Mỗi cạnh  rẽ nhánh theo câu trả lời (true hoặc false)
– Mỗi lá  1 trình tự sắp xếp
– Cây quyết định có bao nhiêu lá, nếu có N phần tử phân biệt cần sắp xếp?
• N!, tức là tất cả các trình tự có thể
• Đối với mỗi bộ dữ liệu, chỉ có 1 lá chứa trình tự sắp xếp cần tìm NGUYỄN ĐỨC NGHĨA 159
Bộ môn KHMT - ĐHBKHN
Ví dụ: Cây quyết định với N=3 "a < b?"
a < b < c, b < c < a, các trình tự có thể
c < a < b, a < c < b,
b < a < c, c < b < a "a < c?" "b < c?" true false a < b < c b < c < a c < a < c < b c < b < a true false true false "b < c?" c < a < b "b < c?" c < b < a a < b < c b < c < a a < c < b b < a < c true false true false trình tự cần tìm a < b < c a < c < b b < c < a b < a < c
Các lá chứa tất cả các trình tự có thể NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 160
Bộ môn KHMT - ĐHBKHN
Cây quyết định và sắp xếp
• Mỗi thuật toán đều có thể mô tả bởi cây quyết định
– Tìm lá nhờ di chuyển theo cây (tức là thực hiện phép so sánh)
– Mỗi quyết định sẽ giảm không gian tìm kiếm đi một nửa
• Thời gian tính trong tình huống tồi nhất  số phép so
sánh nhiều nhất phải thực hiện
– số phép so sánh nhiều nhất cần thực hiện chính là độ dài
đường đi dài nhất trên cây quyết định, tức là độ cao của cây NGUYỄN ĐỨC NGHĨA 161
Bộ môn KHMT - ĐHBKHN
Cận dưới của chiều cao
• Cây nhị phân có chiều cao h có nhiều nhất bao nhiêu lá? L ≤ 2h
• Cây quyết định có nhiều nhất bao nhiêu lá? L = N!
• Cây quyết định với L lá có độ cao ít nhất là: h ≥ log L 2
• Vậy cây quyết định có độ cao: h ≥ log (N!) 2 NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 162
Bộ môn KHMT - ĐHBKHN
log(N!) là (
NlogN) log( !
N )  logN  ( N  ) 1 ( N  ) 2 ( ) 2  ) 1 ( 
 log N  log(N  ) 1  log(N  ) 2  chỉ chọn N/2   log 2  log1 số hạng đầu N
 log N  log( N  ) 1  log( N  ) 2   log 2 mỗi số hạng được N N chọn là  logN/2  log 2 2 N N N  (log N  log ) 2  log N  2 2 2  (  N log N) NGUYỄN ĐỨC NGHĨA 163
Bộ môn KHMT - ĐHBKHN
Cận dưới cho độ phức tạp của bài toán sắp xếp
• Thời gian tính của mọi thuật toán chỉ dựa trên phép
so sánh là (N log N)
• Độ phức tạp tính toán của bài toán sắp xếp chỉ dựa
trên phép so sánh là (N log N)
• Ta có thể phát triển thuật toán tốt hơn hay không nếu
không hạn chế là chỉ được sử dụng phép so sánh? NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 164
Bộ môn KHMT - ĐHBKHN NỘI DUNG
5.1. Bài toán sắp xếp
5.2. Ba thuật toán sắp xếp cơ bản
5.3. Sắp xếp trộn (Merge Sort)
5.4. Sắp xếp vun đống (Heap Sort)
5.5. Sắp xếp nhanh (Quick Sort)
5.6. Cận dưới cho độ phức tạp tính toán của bài toán sắp xếp
5.7. Các phương pháp sắp xếp đặc biệt NGUYỄN ĐỨC NGHĨA 165
Bộ môn KHMT - ĐHBKHN
5.7. Các phương pháp sắp xếp đặc biệt 5.7.1. Mở đầu
5.7.2. Sắp xếp đếm (Counting Sort)
5.7.3. Sắp xếp theo cơ số (Radix Sort)
5.7.4. Sắp xếp đóng gói (Bucket Sort) NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 166
Bộ môn KHMT - ĐHBKHN
Mở đầu: Sắp xếp trong thời gian tuyến tính Linear-time sorting
• Ta có thể làm tốt hơn sắp xếp chỉ sử dụng phép so sánh?
• Với những thông tin bổ sung (hay là giả thiết) về đầu vào,
chúng ta có thể làm tốt hơn sắp xếp chỉ dựa vào phép so sánh.
• Thông tin bổ sung/Giả thiết:
– Các số nguyên nằm trong khoảng [0..k] trong đó k = O(n).
– Các số thực phân bố đều trong khoảng [0,1)
• Ta trình bày ba thuật toán có thời gian tuyến tính:
– Sắp xếp đếm (Counting-Sort)
– Sắp xếp theo cơ số (Radix-Sort)
– Sắp xếp đóng gói (Bucket-sort)
• Để đơn giản cho việc trình bày, ta xét việc sắp xếp các số nguyên không âm. 167
5.7.2. Sắp xếp đếm (Counting sort)
• Input: n số nguyên trong khoảng [0..k] trong đó k là số
nguyên và k = O(n). •
Ý tưởng: với mỗi phần tử x của dãy đầu vào ta xác định hạng
(rank) của nó như là số lượng phần tử nhỏ hơn x. • Một khi ta í r+1.
• Ví dụ: Nếu có 6 phần tử nhỏ hơn 17, ta có thể xếp 17 vào vị trí thứ 7.
• Lặp: khi có một loạt phần tử có cùng giá trị, ta sắp xếp chúng
theo thứ tự xuất hiện trong dãy ban đầu (để có được tính ổn định của sắp xếp). CuuDuongThanCong.com 168 Cài đặt
void countSort(int a[],int b[],int c[],int k) {
// k - giá trị phần tử lớn nhất
// Đếm: b[i] - số phần tử có giá trị i
for (int i=0; i <= k; i++) b[i] = 0; for (i=0; i
// Tính hạng: b[i] hạng của phần tử có giá trị i
for (i = 1; i <= k; i++) b[i] += b[i - 1]; // Sắp xếp
for (i = n-1; i >= 0; i--) { c[b[a[i]] - 1] = a[i]; b[a[i]] = b[a[i]] - 1; } } NGUYỄN ĐỨC NGHĨA 169
Bộ môn KHMT - ĐHBKHN Chương trình demo
/* include int * b; int amax = 0; conio.h, process.h, time.h */ // Tinh phan tu lon nhat amax int a[10000], c[10000]; int n; for (i = 0; i < n; i++) void print(int a[], int n) {
if (a[i] > amax) amax = a[i];
for (int i = 0; i < n; i++) printf("%8i", a[i]); b = new int[amax]; printf("\n"); }
printf("\n Day ket qua:\n");print(c,n);
void countSort(int a[], int b[], int c[], int amax); // Verify result array void main() { c[n]=32767;
int i, k; // gia tri lon nhat co the cua mang A for (i = 0; i < n; i++) clrscr(); randomize(); if (c[i]>c[i+1]) {
printf("\ n n = "); scanf("%i",&n);
printf(" ??????? Loi o vi tri: %6i ", i);
printf("\ n max = "); scanf("%i",&k);
for (i = 0; i < n; i++) a[i] = rand() % k; getch(); }
printf("\n Day ban dau:\n"); print(a,n);
printf("\n Correct!"); getch(); } NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 170
Bộ môn KHMT - ĐHBKHN
Phân tích độ phức tạp của sắp xếp đếm
void countSort(int a[],int b[],int c[],int k) {
// Đếm: b[i] - số phần tử có giá trị i
for (int i=0; i <= k; i++) b[i] = 0; for (i=0; i
// Tính hạng: b[i] hạng của phần tử có giá trị i
for (i = 1; i <= k; i++) b[i] += b[i - 1]; // Sắp xếp
for (i = n-1; i >= 0; i--) { c[b[a[i]] - 1] = a[i]; b[a[i]] = b[a[i]] - 1; } } •
Vòng lặp for đếm b[i] - số phần tử có giá trị i, đòi hỏi thời gian Θ(n+k). •
Vòng lặp for tính hạng đòi hỏi thời gian Θ(n). •
Vòng lặp for thực hiện sắp xếp đòi hỏi thời gian Θ(k). •
Tổng cộng, thời gian tính của thuật toán là Θ(n+k) •
Do k = O(n), nên thời gian tính của thuật toán là Θ(n), nghĩa là, trong trường hợp này nó là
một trong những thuật toán tốt nhất. •
Điều đó là không xảy ra nếu giả thiết k = O(n) là không được thực hiện. Thuật toán sẽ làm
việc rất tồi khi k >> n. •
Sắp xếp đếm không có tính tại chỗ. 171
5.7.3. Sắp xếp theo cơ số (Radix sort)
• Giả thiết: Đầu vào gồm n số nguyên, mỗi số có d chữ số.
• Ý tưởng của thuật toán: Do thứ tự sắp xếp các số cần tìm
cũng chính là thứ tự từ điển của các xâu tương ứng với chúng,
nên để sắp xếp ta sẽ tiến hành d bước sau: Bước 1. Sắp xếp số chữ số thứ
Bước 2. Sắp xếp các số trong dãy thu được theo chữ số thứ 2 (sử dụng sắp xếp ổn định) ...
Bước d. Sắp xếp các số trong dãy thu được theo chữ số thứ d (sử dụng sắp xếp ổn định)
• Giả sử các số được xét trong hệ đếm cơ số k. Khi đó mỗi chữ
số chỉ có k giá trị , nên ở mỗi bước ta có thể sử dụng sắp xếp
đếm với thời gian tính O(n+k). CuuDuongThanCong.com 172 Ví dụ 329 720 720 329 457 355 329 355 657 436 436 436 839 457 839 457 436 657 355 657 720 329 457 720 355 839 657 839 173 Radix Sort
Việc sắp xếp bao gồm nhiều bước, bắt đầu từ chữ số hàng đơn vị,
tiếp đến là chữ số hàng chục, hàng trăm, v.v... Ví dụ:
23, 45, 7, 56, 20, 19, 88, 77, 61, 13, 52, 39, 80, 2, 99 Bước 1: 99 80 2 13 77 39 20 61 52 23 45 56 7 88 19 Bước 2: 7 23 56 88 19 20 2 39 45 52 61 77 80 99 13 Thứ tự cần tìm CuuDuongThanCong.com
Sơ đồ thuật toán Radix-Sort Radix-Sort(A, d)
1. for i  1 to d do 2.
Sử dụng sắp xếp ổn định để sắp xếp A theo chữ số thứ i •
Phân tích độ phức tạp: •
Thời gian tính: Nếu bước 2 sử dụng sắp xếp đếm thì thời gian
tính của một lần lặp là Θ(n+k), do đó thời gian tính của thuật
toán Radix Sort là T(n) = Θ(d(n+k)). Thời gian này sẽ là
Θ(n) nếu d là hằng số và k = O(n) •
Chú ý: Để thực hiện sắp xếp ở mỗi lần lặp của thuật toán,
phải sử dụng thuật toán sắp xếp ổn định, nếu không sẽ không có kết quả đúng. 175
Thuật toán sắp xếp theo cơ số nhị phân •
Ta xét các số nguyên không âm 32-bit và ta sẽ chuyển chúng về các số có
bốn chữ số trong hệ đếm cơ số 256. • Giả sử
p = a ×231+ a ×230+ ... + a ×22+ a ×21+ a ×20 31 30 2 1 0
trong đó a là bằng 0 hoặc 1. i • Khi đó trong
p = b ×2563+ b ×2562+ b ×2561+ b ×2560 3 2 1 0 trong đó
b = a 27+ a 26+ a 25+ a 24+ a 23+ a 22+ a 21+ a 20, 3 31 30 29 28 27 26 25 24
b = a 27+ a 26+ a 25+ a 24+ a 23+ a 22+ a 21+ a 20, 2 23 22 21 20 19 18 17 16
b = a 27+ a 26+ a 25+ a 24+ a 23+ a 22+ a 21+ a 20, 1 15 14 13 12 11 10 9 8
b = a 27+ a 26+ a 25+ a 24+ a 23+ a 22+ a 21+ a 20. 0 7 6 5 4 3 2 1 0 NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 176
Bộ môn KHMT - ĐHBKHN Tính các chữ số
• Nếu số nguyên n nằm trong phạm vi [0,231 ), ta có thể
tính các chữ số b , b , b , b của nó nhờ sử dụng các 0 1 2 3
phép toán & (bitwise) và >> (dịch phải - right shift)
được cung cấp sẵn trong C (các phép toán này thực
hiện rất hiệu quả) như sau: b = n & 255 0
b = (n >> 8) & 255 1
b = (n >> 16) & 255 2
b = (n >> 24) & 255 3 NGUYỄN ĐỨC NGHĨA 177
Bộ môn KHMT - ĐHBKHN Cài đặt trên C
void radixsort(long a[], int n){
/* Tính chỉ số vị trí bắt đầu của mỗi cụm */ int i, j, shift; first_ind[0]=0; long temp[1000]; for (i=1; i<256; i++)
int bin_size[256], first_ind[256];
first_ind[i]=first_ind[i-1]+bin_size[i-1]; for (shift=0; shift temp
/* Tính kích thước mỗi cụm và sao chép các */
phần tử của mảng a vào mảng temp */
for (j=0; jfor (i=0; i<256; i++) bin_size[i]=0;
i=(temp[j]>>shift)&255;
for (j=0; ja[first_ind[i]]=temp[j]; i=(a[j]>>shift)&255; first_ind[i]++; } bin_size[i]++; } // end for shift temp[j]=a[j]; } // end radixsort } NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 178
Bộ môn KHMT - ĐHBKHN Chương trình chính #include int main () { #include long data[1000]; int i, N; #include
printf("\ Nhap so luong phan tu n = "); #include scanf("%i",&N); // Randomdata
for ( i=0; ivoid print(long a[], int n) {
printf("\n Day dau vao:\n"); print(data, N); for (int i = 0; i < n; i++) radixsort (data, N); printf("%8i", a[i]);
printf("\n Day duoc sap thu tu:\n"); print(data, N); printf("\n"); data[N]=9999999; }
for ( i=0; iif (data[i]>data[i+1]) printf("\n ?????? ERROR:\n"); getch(); } NGUYỄN ĐỨC NGHĨA 179
Bộ môn KHMT - ĐHBKHN
Chọn cơ số như thế nào? Khoá gồm b bit: … …
b/r chữ số chữ số gồm
Mỗi chữ số trong khoảng 0 -- 2r –1
b/r bước, mỗi bước đòi hỏi thời gian (n+2r ) (áp dụng Sắp xếp đếm).
Thời gian tính là ((b/r) (n + 2r )).
Nếu b ≤ log n, chọn r = b (n)
Nếu b > log n, chọn r = log n
(bn/log n) NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 180
Bộ môn KHMT - ĐHBKHN Radix-Sort tổng quát
• Cho n số, mỗi số có b bit và số r ≤ b. Khi đó Radix-Sort đòi hỏi
thời gian Θ((b/r)(n+2r)):
– Chọn d=b/r chữ số, mỗi chữ số gồm r bit có giá trị trong khoảng [0..2r–1].
– Vì thế ở mỗi bước có thể sử dụng Counting-Sort với k=2r –1, đòi hỏi thời gian Θ(n+k),
– Tất cả phải thực hiện d bước, do đó thời gian tổng cộng là Θ(d(n+2r)), hay
Θ((b/r)(n+2r)).
• Với các giá trị của n và b cho trước, ta có thể chọn r ≤ b để đạt
cực tiểu của Θ((b/r)(n+2r)).
• Nếu b ≤ log n, chọn r = log n ta thu được thuật toán với thời gian Θ(n).
• Nếu b > log n, chọn r = log n ta thu được thuật toán với thời gian
(bn/log n). 181
5.7.4. Sắp xếp phân cụm (Bucket sort)
Giả thiết: Đầu vào gồm n số thực có phân bố đều trong khoảng
[0..1) (các số có xác suất xuất hiện như nhau)
Ý tưởng của thuật toán:
• Chia đoạn [0..1) ra làm n cụm (buckets) 0, 1/n
• Đưa mỗi phần tử a vào đúng cụm của nó i/n ≤ a < (i+1)/n. j j
• Do các số là phân bố đều nên không có quá nhiều số rơi vào cùng một cụm.
• Nếu ta chèn chúng vào các cụm (sử dụng sắp xếp chèn) thì các
cụm và các phần tử trong chúng đều được sắp xếp theo đúng thứ tự. CuuDuongThanCong.com 182
Ví dụ: Sắp xếp phân cụm,
n=10, các cụm là 0, 0.1, 0.2, ..., 0.9 Bổ sung vào .78 0 Sắp xếp mỗi cụm .12 các cụm .17 1 .12 .17 .17 .39 2 .21 .23 .26 .21 .26 3 .39 .23 .72 4 .26 .94 5 .39 . 21 Nối các .12 6 .68 .68 cụm .23 7 .72 .78 .72 .68 8 .78 9 .94 .94 183 Ví dụ A[ ] 0
n số được phân vào n đoạn con bằng nhau của [0, 1). .78 .17 1 .12 .17 2 .39 .21 .23 .26 3 .26
Bước 2: Nối các danh sách 4 .72 Từ trên xuống dưới 5 .94 Từ trái sang phải 6 .21 .68 .12 7 .72 .78 8
Bước 1: thực hiện insertion sort .23 trong mỗi danh sách 9 .68 .94 CuuDuongThanCong.com
Sơ đồ thuật toán Bucket-Sort
A[0..n-1] là mảng đầu vào
B[0], B[1], …, B[n –1] là các Bucket-Sort(A) danh sách cụm 1. n = length(A) 2.
for i = 0 to n-1 3.
do Bổ sung A[i] vào danh sách B[n*A[i] ] 4.
for i = 0 to n –1 5.
do Insertion-Sort(B[i]) 6.
Nối các danh sách B[0], B[1], … B[n –1] theo thứ tự 185
Phân tích thời gian tính của Bucket-Sort
• Tất cả các dòng, ngoại trừ dòng 5 (Insertion-Sort), đòi hỏi thời
gian O(n) trong tình huống tồi nhất.
• Trong tình huống tồi nhất, O(n) số được đưa vào cùng một
cụm, do đó thuật toán có thời gian tính O(n2) trong tình huống tồi nhất.
• Tuy nhiên, trong tình huống trung bình, chỉ có một số lượng
hằng số phần tử của dãy cần sắp xếp rơi vào trong mỗi cụm và
vì thế thuật toán có thời gian tính trung bình là O(n) (ta công nhận sự kiện này).
• Mở rộng: sử dụng các sơ đồ chỉ số hoá khác nhau để phân cụm các phần tử. CuuDuongThanCong.com 186 Tổng kết:
Các thuật toán sắp xếp dựa trên phép so sánh Name Average Worst In place Stable Bubble sort — O(n²) Yes Yes Selection sort O(n²) O(n²) Yes No Insertion sort
O(n + d) O(n²) Yes Yes Merge sort
O(n log n)
O(n log n) No Yes Heapsort
O(n log n)
O(n log n) Yes No Quicksort
O(n log n) O(n²) No No NGUYỄN ĐỨC NGHĨA 187
Bộ môn KHMT - ĐHBKHN QUESTIONS? NGUYỄ C N ĐỨ uuD C NG uongT HĨ haA nCong.com 188
Bộ môn KHMT - ĐHBKHN