Xem mẫu
- Sắp xếp - Sorting
Trình bày các thuật toán
!
thông dụng cho việc sắp
xếp nội (sắp xếp trên bộ
nhớ trong - Mảng)
Minh họa các thuật toán
!
Đánh giá thuật toán
!
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 1
Nội dung trình bày
Thuật toán “Selection sort”
!
Thuật toán “Insertion sort”
!
Thuật toán “Shell sort”
!
Thuật toán “Heap sort”
!
Thuật toán “Merge sort”
!
Thuật toán “Quick sort”
!
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 2
1
- Sắp xếp 1 mảng các số nguyên
Giả sử có 1
!
mảng gồm 6 70
số nguyên. 60
Ta cần sắp 50
xếp các phần 40
tử của mảng 30
theo thứ tự 20
tăng dần 10
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 3
Thuật toán “Chọn trực tiếp”
(Selection sort Algorithm)
Bắt đầu bằng
!
cách tìm 70
phần tử nhỏ 60
nhất 50
40
30
20
10
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 4
2
- Selection sort Algorithm
Hoán vị
!
phần tử nhỏ 70
nhất tìm 60
được với 50
phần tử đầu 40
tiên của 30
mảng 20
10
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 5
Selection sort Algorithm
Phần đã sắp Phần chưa sắp
70
1 phần của 60
!
mảng đã 50
được sắp xếp 40
30
20
10
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 6
3
- Selection sort Algorithm
Phần đã sắp Phần chưa sắp
70
Tìm phần tử 60
!
nhỏ nhất 50
trong phần 40
chưa được 30
sắp 20
10
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 7
Selection sort Algorithm
Phần đã sắp Phần chưa sắp
70
Hoán vị
! 60
phần tử nhỏ 50
nhất trong 40
phần chưa 30
được sắp với 20
phần tử đầu
10
tiên trong
0
phần này [1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 8
4
- Selection sort Algorithm
Phần đã sắp Phần chưa sắp
70
Phần đã
! 60
được sắp xếp 50
của mảng 40
được tăng 30
thêm 1 phần 20
tử
10
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 9
Selection sort Algorithm
Phần đã sắp Phần chưa sắp
70
Tiếp tục
! 60
tương tự ... Phần tử
50
nhỏ nhất
40
30
20
10
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 10
5
- Selection sort Algorithm
Phần đã sắp Phần chưa sắp
70
Tiếp tục
! 60
ị
tương tự ... nv
á
50
Ho hần
p
với đầu
40
tử
30
20
10
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 11
Selection sort Algorithm
Phần đã sắp
Phần đã sắp Phần chưa sắp
tăng thêm
70
Tiếp tục
! 60
tương tự ... 50
40
30
20
10
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 12
6
- Selection sort Algorithm
Phần đã sắp Phần chưa sắp
Quá trình lần
!
lượt thêm từng 70
phần tử vào 60
phần đã sắp… 50
Phần đã sắp
! 40
chứa các phần 30
tử nhỏ nhất, sắp 20
tăng dần 10
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 13
Selection sort Algorithm
Phần đã sắp Phần chưa …
Thuật toán
!
dừng khi chỉ 70
còn 1 phần tử 60
(đó là phần tử 50
lớn nhất). 40
30
20
10
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 14
7
- Selection sort Algorithm
Toàn bộ mảng
!
đã được sắp thứ 70
tự. 60
Tổng quát: chọn 50
!
phần tử nhỏ nhất 40
và đưa nó về vị 30
trí đầu của phần 20
chưa được sắp 10
trong mảng. 0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 15
Selection sort Algorithm
(Minh họa chương trình)
void SelectionSort (int a[ ], int n )
{
// vị trí của phần tử nhỏ nhất (trong phần chưa sắp)
int min;
// biến tạm dùng khi hoán vị
int tmp;
for (int i = 0; i < n; i++ ) {
// tìm phần tử nhỏ nhất trong phần chưa sắp
min = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[min] ) min = j;
// hoán vị phần tử nhỏ nhất được tìm thấy với phần tử đầu
if (a[min] < a[i]) { tmp = a[i]; a[i] = a[min]; a[min] = tmp; }
} // end of for i
}
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 16
8
- Đánh giá thuật toán
(Selection sort Algorithm)
Trong mọi trường hợp, số phép so sánh là:
!
(n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n2)
Số phép hoán vị:
!
Trường hợp xấu nhất: O(n)
!
Trường hợp tốt nhất (mảng đã sắp tứ tự tăng
!
dần): 0
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 17
Thuật toán “Chèn trực tiếp”
(Insertion sort Algorithm)
Thuật toán
!
“Chèn trực 70
tiếp” cũng 60
chia mảng 50
thành 2 40
phần: phần 30
đã được sắp 20
và phần 10
chưa được 0
sắp [1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 18
9
- Insertion sort Algorithm
Phần đã sắp Phần chưa sắp
Phần đã sắp 70
!
lúc đầu chỉ 60
có 1 phần 50
tử đầu tiên 40
của mảng 30
(không cần 20
thiết là phần 10
tử nhỏ nhất) 0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 19
Insertion sort Algorithm
Phần đã sắp Phần chưa sắp
70
Mở rộng
!
60
phần đã sắp
bằng cách 50
40
thêm vào
phần tử đầu 30
20
tiên trong
phần chưa 10
được sắp… 0
[1] [2] [3] [4] [5] [5] [6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 20
10
- Insertion sort Algorithm
Phần đã sắp Phần chưa sắp
...và đặt nó 70
!
vào vị trí 60
thích hợp, 50
sao cho phần 40
đã sắp vẫn 30
giữ nguyên 20
tính thứ tự 10
(tăng dần). 0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 21
Insertion sort Algorithm
Phần đã sắp Phần chưa sắp
Trong ví dụ 70
!
này, phần tử 60
mới được 50
đặt vào vị trí 40
đầu của 30
phần đã sắp. 20
10
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 22
11
- Insertion sort Algorithm
Phần đã sắp Phần chưa sắp
Đôi khi 70
!
60
chúng ta
“gặp may”, 50
phần tử mới 40
không cần 30
phải di 20
chuyển. 10
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 23
Insertion sort Algorithm
Phần đã sắp Phần chưa sắp
… và lại 70
!
“gặp may” 60
thêm 1 lần 50
nữa.. 40
30
20
10
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 24
12
- Insertion sort Algorithm
Làm sao để chèn 1 phần tử ?
Copy phần Phần đã sắp Phần chưa sắp
!
tử mới vào 1 70
biến trung
60
gian…
50
40
30
20
10
10
0
0 [1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 25
Insertion sort Algorithm
Làm sao để chèn 1 phần tử ?
…Dịch
!
chuyển các 70
phần tử
60
trong phần
50
đã sắp sang
40
phải…
30
20
10 10
0 0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 26
13
- Insertion sort Algorithm
Làm sao để chèn 1 phần tử ?
…để tạo 1
!
chỗ trống 70
cho phần tử
60
mới…
50
40
30
20
10
10
0
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 27
Insertion sort Algorithm
Làm sao để chèn 1 phần tử ?
…tiếp tục
!
dịch chuyển 70
các phần
60
tử...
50
40
30
20
10
10
0
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 28
14
- Insertion sort Algorithm
Làm sao để chèn 1 phần tử ?
…tiếp tục
!
dịch chuyển 70
các phần
60
tử...
50
40
30
20
10
10
0
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 29
Insertion sort Algorithm
Làm sao để chèn 1 phần tử ?
...cho đến
!
khi tìm thấy 70
vị trí thích
60
hợp cho
50
phần tử
40
mới...
30
20
10
10
0
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 30
15
- Insertion sort Algorithm
Làm sao để chèn 1 phần tử ?
Copy phần Phần đã sắp Phần chưa…
!
tử mới vào 70
lại mảng, tại
60
vị trí này.
50
40
30
20
10 10
0 0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 31
Insertion sort Algorithm
Làm sao để chèn 1 phần tử ?
Phần đã sắp Phần chưa…
Phần tử cuối
!
cùng cũng 70
phải “chèn”. 60
Copy nó vào 50
1 biến trung 40
gian... 30
20
20
10
10
0
0 [1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 32
16
- Insertion sort Algorithm
Câu hỏi ?
Có bao nhiêu
phép dịch 70
chuyển xảy 60
ra ? 50
40
30
20 20
10 10
0 0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 33
Insertion sort Algorithm
Câu hỏi ?
Có 4 phép
!
dịch chuyển 70
… 60
50
40
30
20 20
10 10
0 0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 34
17
- Insertion sort Algorithm
!… Copy
phần tử trở 70
lại mảng. 60
50
40
30
20
20
10
10
0
0
[1] [2] [3] [4] [5] [5][6]
[0] [1] [2] [3] [4]
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 35
Insertion sort Algorithm
(Minh họa chương trình)
void InsertionSort (int a[ ], int n)
{
int saved; // biến trung gian lưu lại giá trị phần tử cần chèn
for (int i = 1; i < n; i++ ) {
// lưu lại giá trị phần tử cần chèn
saved = a[i];
// dịch chuyển các phần tử trong phần đã sắp sang phải
for (int j = i; j > 0 && saved < a[j-1]; j--)
a[j] = a[j-1];
// chèn phần tử vào đúng vị trí
a[j] = saved;
} // end of for i
}
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 36
18
- Đánh giá thuật toán
(Insertion sort Algorithm)
Trường hợp xấu nhất có:
!
1 + 2 + 3 + … + (n-1) = n(n-1)/2 = O(n2)
phép so sánh và dịch chuyển
Trường hợp tốt nhất (mảng đã có thứ tự
!
tăng dần): O(n) phép so sánh và 0 phép dịch
chuyển
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 37
Nhận xét chung
(Selection & Insertion sort)
“Chèn trực tiếp” và “Chọn trực tiếp” đều có
!
chi phí cho trường hợp xấu nhất là O(n2)
Do đó, không thích hợp cho việc sắp xếp các
!
mảng lớn
Dễ cài đặt, dễ kiểm lỗi
!
“Chèn trực tiếp” tốt hơn “Chọn trực tiếp”,
!
nhất là khi mảng đã có thứ tự sẵn
Cần có những thuật toán hiệu quả hơn cho
!
việc sắp xếp các mảng lớn
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 38
19
- Thuật toán “Shell sort”
(Shell sort Algorithm)
Được đề xuất vào năm 1959 bởi Donald
!
Shell trên tạp chí Communication of the
ACM
Thuật toán này cải tiến hiệu quả của thuật
!
toán “Chèn trực tiếp”
Phá vỡ rào cản chi phí O(n2) của những
!
thuật toán sắp xếp trước đó
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 39
Shell sort Algorithm
Ý tưởng:
!
Chia dãy ban đầu thành h dãy con
!
a0, a0+h, a0+2h, …
a1, a1+h, a1+2h, …
a2, a2+h, a2+2h, …
…
Sắp xếp từng dãy con bằng cách sử dụng
!
phương pháp “Chèn trực tiếp”
Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM
Spring 2004 40
20
nguon tai.lieu . vn
