Chương 6: Sắp xếp
Các phương pháp sắp xếp cơ bản Đánh giá các phương pháp Quick_Sort Heap_Sort
Bạn đang xem trước 20 trang tài liệu Chương 6: Sắp xếp, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
Chương 6:
Sắp xếp
Giảng viên: Ths. Nguyễn Thị Khiêm Hòa
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
2
Nội dung
Các phương pháp sắp xếp cơ bản
Đánh giá các phương pháp
Quick_Sort
Heap_Sort
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
3
Mục tiêu
Trình bày các thuật toán thông dụng cho việc sắp xếp
trong (sắp xếp trên bộ nhớ trong - RAM)
Minh họa các thuật toán
Đánh giá thuật toán
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
4
Đặt vấn đề
Trong công việc hàng ngày cũng như các bài toán quản lý
kinh tế cần tìm kiếm dữ liệu
Dễ dàng
Nhanh chóng
Ví dụ: danh sách sinh viên, từ điển …
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
5
Sắp xếp (Sorting)
Định nghĩa
Sắp xếp là quá trình tổ chức lại một tập hợp k đối
tượng theo một trật tự nào đó
Hai mô hình sắp xếp
Sắp xếp trong (internal), các phần tử cần sắp xếp
được lưu sẵn trong RAM
Sắp xếp ngoài (external), một số các phần tử cần sắp
xếp lưu trong RAM, còn lại được lưu ở bộ nhớ ngoài
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
6
Các phương pháp sắp xếp cơ bản
Phương pháp sắp xếp kiểu lựa chọn
Phương pháp sắp xếp chèn
Phương pháp sắp xếp đổi chỗ
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
7
Phương pháp sắp xếp kiểu lựa chọn
(Selection Sort)
Ý tưởng:
Tìm phần tử nhỏ nhất đem về đầu dãy
Loại phần tử này ra khỏi dãy
Tiếp tục tìm phần tử nhỏ nhất của dãy còn lại.
Thuật toán:
Ở bước thứ i ta chọn trong Ai, Ai+1, …, An phần tử có
khóa nhỏ nhất và đổi chỗ với Ai.
Sau n lượt ta có dãy A được sắp thứ tự
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
8
Ví dụ:
Cho dãy số:
Phương pháp sắp xếp kiểu lựa chọn
(Selection Sort)
i = 1234567
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
9
Phương pháp sắp xếp kiểu lựa chọn
(Selection Sort)
public void SelectionSort()
{
int min,vt;
for (int i = 0; i < idx-1; i++)
{
min = A[i];
vt = i;
for (int j = i + 1; j < idx; j++)
{
if (A[j] < min)
{
min = A[j];
vt = j;
}
}
if (vt != i)
{
A[vt] = A[i];
A[i] = min;
}
}
}
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
10
Phương pháp sắp xếp chèn (Insertion Sort)
Thuật toán:
Dãy ban đầu A1,A2,…,An xem như đã có đoạn gồm 1
phần tử A1 đã được sắp.
Thêm A2 vào A1 sẽ có đoạn A1A2 đã được sắp.
Thêm A3 vào A1A2 sẽ có đoạn A1A2 A3 đã được sắp.
Tiếp tục cho đến khi thêm xong An vào đoạn
A1,A2,…,An-1 sẽ có dãy A1,A2,…,An đã được sắp xếp.
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
11
Phương pháp sắp xếp chèn (Insertion Sort)
Ví dụ:
Cho dãy số:
i = 2
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
12
Phương pháp sắp xếp chèn (Insertion Sort)
i = 3
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
13
Phương pháp sắp xếp chèn (Insertion Sort)
i = 4
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
14
Phương pháp sắp xếp chèn (Insertion Sort)
i = 5
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
15
Phương pháp sắp xếp chèn (Insertion Sort)
i = 6
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
16
Phương pháp sắp xếp chèn (Insertion Sort)
i = 7
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
17
Phương pháp sắp xếp chèn (Insertion Sort)
i = 8
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
18
Phương pháp sắp xếp chèn (Insertion Sort)
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
19
Phương pháp sắp xếp chèn (Insertion Sort)
public void Insertion_Sort()
{
for (int i = 1; i < idx; i++)
{
int x = A[i];
int j = i - 1;
while ((j >= 0)&&(A[j] > x))
{
A[j + 1] = A[j];
j--;
}
A[j + 1] = x;
}
}
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
20
Phương pháp sắp xếp đổi chỗ (Bubble Sort)
Ý tưởng:
Xét từ cuối dãy ngược về vị trí i
Nếu hai phần tử kế cận ngược thứ tự thì đổi chỗ
cho nhau
Thực hiện đến khi không còn phần tử để xét.
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
21
Thuật toán:
Bước 1: i = 1;
Bước 2: j = n;
Trong khi j > i thực hiện:
Nếu Aj < Aj-1 : đổi chổ Aj và Aj-1
j = j - 1
Bước 3: i = i +1
Nếu i > n-1: Hết dãy -> Dừng
Ngược lại: lặp lại bước 2.
Phương pháp sắp xếp đổi chỗ (Bubble Sort)
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
22
Phương pháp sắp xếp đổi chỗ (Bubble Sort)
Ví dụ:
Cho dãy số:
i = 1 j = 75432
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
23
Phương pháp sắp xếp đổi chỗ (Bubble Sort)
i = 2 j = 653
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
24
Phương pháp sắp xếp đổi chỗ (Bubble Sort)
i = 3 j = 64
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
25
Phương pháp sắp xếp đổi chỗ (Bubble Sort)
i = 4 j = 75
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
26
Phương pháp sắp xếp đổi chỗ (Bubble Sort)
i = 5 j = 6
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
27
Phương pháp sắp xếp đổi chỗ (Bubble Sort)
i = 6 j = 7
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
28
Phương pháp sắp xếp đổi chỗ (Bubble Sort)
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
29
Phương pháp sắp xếp đổi chỗ (Bubble Sort)
public void Buble_Sort()
{
for (int i = 0; i < idx - 1; i++)
{
for(int j = idx - 1; j > i; j--)
if(A[j] < A[j-1])
{
int tmp = A[j];
A[j] = A[j - 1];
A[j-1] = tmp;
}
}
}
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
30
Phương pháp sắp xếp đổi chỗ cải tiến
(Shaker_Sort)
Nhận xét:
Phương pháp Buble_Sort không nhận diện được
tình trạng đã được sắp xếp của dãy ban đầu
=> Không hạn chế được phạm vi sắp xếp.
Phần tử nhẹ nổi lên trên nhưng phần tử nặng
không chìm xuống.
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
31
Phương pháp sắp xếp đổi chỗ cải tiến
(Shaker_Sort)
Ý tưởng:
Ghi nhận những đoạn đã sắp xếp bằng cách ghi
nhớ vị trí đã xảy ra hoán vị để thu hẹp phạm vi
sắp xếp.
Cài đặt
Bài tập cho sinh viên
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
32
So sánh ba phương pháp sắp xếp
Phương pháp sắp xếp chọn
Ở bước thứ i, có (n-i) lần so sánh, với i=1…n-1
(n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n2)
Thời gian thực hiện giải thuật T(n) ~ O(n2)
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
33
So sánh ba phương pháp sắp xếp
Với phương pháp chèn thì số lần so sánh phụ thuộc
vào dãy ban đầu. Trường hợp tốt nhất là dãy đã sắp,
mỗi lượt chỉ cần 1 lần so sánh nên:
11
1
1
min
nC
n
i
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
34
So sánh ba phương pháp sắp xếp
Trường hợp xấu nhất là dãy sắp ngược thứ tự, mỗi
lượt thứ i cần Ci =(i-1) lần so sánh nên:
Suy ra:
2
)1(
)1(
1
1
max
nn
iC
n
i
4
2
2
21
1
nni
C
n
i
tb
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
35
So sánh ba phương pháp sắp xếp
Phương pháp sắp xếp nổi bọt:
Ở bước thứ i, có n-i phép so sánh
Thời gian thực hiện giải thuật T(n) ~ O(n2)
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
36
So sánh ba phương pháp sắp xếp
Theo kết quả đánh giá thì phương pháp chèn tỏ ra
hiệu quả hơn hai phương pháp kia. Tuy nhiên với n
khá lớn thì chi phí về thời gian thực hiện cả ba
phương pháp đều có chi phí về thời gian tương
đương:
T(n) = O(n2)
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
37
Phương pháp sắp xếp dựa trên phân hoạch
(Quick_Sort)
Ý tưởng:
Chọn một phần tử trong dãy làm khoá
Đưa các phần tử nhỏ hơn khoá về bên trái của khoá,
các phần tử lớn hơn đưa về bên phải của khoá.
Tiếp tục thực hiện phân hoạch với các dãy con cho
đến khi dãy được sắp xếp
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
38
Phương pháp sắp xếp dựa trên phân hoạch
(Quick_Sort)
Thuật toán:
Bước 1: Chọn phần tử giữa có khoá x làm mốc để
phân hoạch
Bước 2: Đi từ hai đầu của dãy, phát hiện cặp A[i]>x
và A[j]<x, đổi chỗ (A[i],A[j]). Tiếp tục cho đến khi i≥j.
Ta có 2 dãy con.
Bước 3: Thực hiện bước 1 và 2 cho từng dãy con
nếu số phần tử của dãy con lớn hơn 1.
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
39
Ví dụ:
Cho dãy số:
Phương pháp sắp xếp dựa trên phân hoạch
(Quick_Sort)
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
40
Phương pháp sắp xếp dựa trên phân hoạch
(Quick_Sort)
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
41
Phương pháp sắp xếp dựa trên phân hoạch
(Quick_Sort)
private void QuickSort(int left, int right)
{ int x = A[(left + right) / 2];
int i = left; int j = right;
do
{ while (A[i] < x)
i++;
while (A[j] > x)
j--;
if (i <= j)
{ Hoan_vi(A[i],A[j]);
i++;
j--;
}
} while (i <= j);
if (i < right)
QuickSort(i, right);
if (j > left)
QuickSort(left, j);
}
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
42
Phương pháp sắp xếp dựa trên phân hoạch
(Quick_Sort)
Nhận xét:
Khi chọn khoá nhầm phần tử nhỏ nhất (hoặc lớn
nhất) sẽ dẫn đến trường hợp xấu nhất của
phương pháp.
Khi số lượng phần tử thấp nên chọn phương pháp
sắp xếp đơn giản.
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
43
Phương pháp sắp xếp dựa trên phân hoạch
(Quick_Sort)
Đánh giá:
Gọi T(n) là thời gian thực hiện thuật toán với dãy n
phần tử. P(n) là thời gian để phân đoạn dãy n khoá
thành 2 dãy con
T(n) = P(n) + T(l..j) + T(i..r)
Trường hợp tốt nhất: mỗi bước phân thành 2 đoạn
có chiều dài bằng nhau:
T(n) = P(n) + 2T(n/2) ~ O(nlog2n)
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
44
Phương pháp sắp xếp dựa trên phân hoạch
(Quick_Sort)
Đánh giá:
Trường hợp xấu nhất: mỗi bước phân mảng r phần
tử thành 2 đoạn có chiều dài bằng 1 và r-1:
T(n) = P(n) + T(n-1) + T(1) ~ O(n2)
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
45
Phương pháp sắp xếp trên Heap (Heap_Sort)
Đặt vấn đề:
SelectionSort: Không tận dụng được thông tin của
bước trước đó khi tìm phần tử nhỏ nhất
Quick_Sort: Trong trường hợp xấu nhất tốn chi phí
O(n2)
Phương pháp Heap_Sort
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
46
Phương pháp sắp xếp trên Heap (Heap_Sort)
Định nghĩa:
Cây nhị phân Heap: Là cây nhị phân có khoá của nút
cha lớn hơn hoặc bằngkhoá hai nút con
Nút gốc có giá trị lớn nhất
Nút lá là một Heap
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
47
Phương pháp sắp xếp trên Heap (Heap_Sort)
Định nghĩa:
Dãy A, n phần tử được gọi là Heap nếu:
Ai ≥ A2i và Ai ≥ A2i+1
(Ai, A2i), (Ai, A2i+1) là các cặp phần tử liên đới
Phần tử đầu dãy là phần tử lớn nhất
Mọi dãy an/2+1, …, an là một Heap
Nếu dãy A là một Heap thì khi cắt bỏ một số phần
tử ở hai đầu dãy thì dãy còn lại vẫn là một Heap
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
48
Phương pháp sắp xếp trên Heap (Heap_Sort)
Thuật toán:
Bước 1: Hiệu chỉnh dãy A0 .. An-1 thành
một Heap
Bước 2: Hoán vị A0 và An-1
Bước 3: Lặp lại bước 1 và 2 với n giảm dần cho
đến khi n=1
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
49
Phương pháp sắp xếp trên Heap (Heap_Sort)
Ví dụ:Cho dãy số 12, 2, 8, 5, 1, 6, 4, 15, 9, 7
1
2
12 8 5 1 6 4 152
2 8
5 1 6 4
1
5
9 7
9 7
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
50
Phương pháp sắp xếp trên Heap (Heap_Sort)
1
2
12 8 5 1 6 4 152
2 8
5 1 6 4
1
5
9 7
9 7
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
51
Phương pháp sắp xếp trên Heap (Heap_Sort)
1
2
12 8 5 7 6 4 152
2 8
5
1
6 4
1
5
9
7
9 1
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
52
Phương pháp sắp xếp trên Heap (Heap_Sort)
1
2
12 8 15 7 6 4 52
2 8
1
5
7 6 4
5 9 1
9 1
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
53
Phương pháp sắp xếp trên Heap (Heap_Sort)
1
2
2
81
5
7 6 4
5 9 1 12 8 2 7 6 4 515 9 1
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
54
Phương pháp sắp xếp trên Heap (Heap_Sort)
1
2
9
81
5
7 6 4
5 2 1 12 8 9 7 6 4 515 2 1
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
55
Phương pháp sắp xếp trên Heap (Heap_Sort)
1
5
9
81
2
7 6 4
5 2 1
15 8 9 7 6 4 512 2 1
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
56
Phương pháp sắp xếp trên Heap (Heap_Sort)
1
9
81
2
7 6 4
5 2 1
5
1 8 9 7 6 4 512 2 15
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
57
Phương pháp sắp xếp trên Heap (Heap_Sort)
1
2
5
89
7 6 4
1 2 1
5
12 8 5 7 6 4 19 2 15
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
58
Phương pháp sắp xếp trên Heap (Heap_Sort)
2
5
89
7 6 4
1 1
2
1
5
2 8 5 7 6 4 19 12 15
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
59
Phương pháp sắp xếp trên Heap (Heap_Sort)
9
5
87
2 6 4
1 1
2
1
5
9 8 5 2 6 4 17 12 15
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
60
Phương pháp sắp xếp trên Heap (Heap_Sort)
1
5
87
2 6 4
9 1
2
1
5
1 8 5 2 6 4 97 12 15
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
61
Phương pháp sắp xếp trên Heap (Heap_Sort)
8
5
67
2 1 4
9 1
2
1
5
8 6 5 2 1 4 97 12 15
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
62
Phương pháp sắp xếp trên Heap (Heap_Sort)
4
5
67
2 1 8
9 1
2
1
5
4 6 5 2 1 8 97 12 15
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
63
Phương pháp sắp xếp trên Heap (Heap_Sort)
7
4
65
2 1 8
9 1
2
1
5
7 6 4 2 1 8 95 12 15
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
64
Phương pháp sắp xếp trên Heap (Heap_Sort)
1
4
65
2 7 8
9 1
2
1
5
1 6 4 2 7 8 95 12 15
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
65
Phương pháp sắp xếp trên Heap (Heap_Sort)
6
4
15
2 7 8
9 1
2
1
5
6 1 4 2 7 8 95 12 15
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
66
Phương pháp sắp xếp trên Heap (Heap_Sort)
2
4
15
6 7 8
9 1
2
1
5
2 1 4 6 7 8 95 12 15
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
67
Phương pháp sắp xếp trên Heap (Heap_Sort)
5
2
14
6 7 8
9 1
2
1
5
5 1 2 6 7 8 94 12 15
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
68
Phương pháp sắp xếp trên Heap (Heap_Sort)
2
5
14
6 7 8
9 1
2
1
5
2 1 5 6 7 8 94 12 15
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
69
Phương pháp sắp xếp trên Heap (Heap_Sort)
4
5
12
6 7 8
9 1
2
1
5
4 1 5 6 7 8 92 12 15
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
70
Phương pháp sắp xếp trên Heap (Heap_Sort)
1
5
42
6 7 8
9 1
2
1
5
1 4 5 6 7 8 92 12 15
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
71
Phương pháp sắp xếp trên Heap (Heap_Sort)
1
5
42
6 7 8
9 1
2
1
5
1 4 5 6 7 8 92 12 15
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
72
Phương pháp sắp xếp trên Heap (Heap_Sort)
1
5
42
6 7 8
9 1
2
1
5
1 4 5 6 7 8 92 12 15
1 3 4 5 6 7 82 9 10
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
73
Phương pháp sắp xếp trên Heap (Heap_Sort)
public void Heap_Sort()
{
int right = idx - 1;
Create_Heap();
while (right > 0)
{
int tmp = A[0];
A[0] = A[right];
A[right] = tmp;
right--;
Shift(0, right);
}
}
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
74
Phương pháp sắp xếp trên Heap (Heap_Sort)
private void Create_Heap()
{
int left =(idx-1)/2;
while (left >= 0)
{
Shift(left, idx - 1);
left--;
}
}
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
75
Phương pháp sắp xếp trên Heap (Heap_Sort)
private void Shift(int left, int right)
{
int i = left;
int j = 2 * i + 1;
int x = A[i];
while (j <= right)
{
if (j < right)
if (A[j] < A[j + 1])
j++;
if (A[j] < x)
break;
A[i] = A[j];
i = j;
j = 2 * i + 1;
}
A[i] = x;
}
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
76
Đánh giá:
Việc đánh giá giải thuật HeapSort rất phức tạp nhưng
đã chứng minh được độ phức tạp trong trường hợp
xấu nhất:
T(n) = O(nlog2n)
Phương pháp sắp xếp trên Heap (Heap_Sort)
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
77
Bài tập
Cài đặt các thuật toán sắp xếp cho mảng số
nguyên 20000 phần tử được đọc từ file. Đo
thời gian thực hiện của từng thuật toán. Vẽ
biểu đồ so sánh kết quả nhận được.
Thực hiện
90 min
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
78
Q&A
