Thư viện tri thức trực tuyến
Kho tài liệu với 50,000+ tài liệu học thuật
© 2023 Siêu thị PDF - Kho tài liệu học thuật hàng đầu Việt Nam
Sắp xếp - Sorting
Nội dung xem thử
Mô tả chi tiết
1
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 1
! 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
Sắp xếp - Sorting
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 2
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”
2
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 3
Sắp xếp 1 mảng các số nguyên
! Giả sử có 1
mảng gồm 6
số nguyên.
Ta cần sắp
xếp các phần
tử của mảng
theo thứ tự
tăng dần
[1] [2] [3] [4] [5] [6]
0
10
20
30
40
50
60
70
[1] [2] [3] [4] [5] [6] [0] [1] [2] [3] [4] [5]
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 4
[1] [2] [3] [4] [5] [6]
0
10
20
30
40
50
60
70
[1] [2] [3] [4] [5] [6]
Thuật toán “Chọn trực tiếp”
(Selection sort Algorithm)
! Bắt đầu bằng
cách tìm
phần tử nhỏ
nhất
[1] [2] [3] [4] [5] [6]
0
10
20
30
40
50
60
70
[1] [2] [3] [4] [5] [6] [0] [1] [2] [3] [4] [5]
3
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 5
[1] [2] [3] [4] [5] [6]
0
10
20
30
40
50
60
70
[1] [2] [3] [4] [5] [6]
Selection sort Algorithm
! Hoán vị
phần tử nhỏ
nhất tìm
được với
phần tử đầu
tiên của
mảng
[1] [2] [3] [4] [5] [6]
0
10
20
30
40
50
60
70
[1] [2] [3] [4] [5] [6] [0] [1] [2] [3] [4] [5]
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 6
[1] [2] [3] [4] [5] [6]
0
10
20
30
40
50
60
70
[1] [2] [3] [4] [5] [6]
Selection sort Algorithm
! 1 phần của
mảng đã
được sắp xếp
[1] [2]
0
10
20
30
40
50
60
70
[1] [2]
Phần đã sắp Phần chưa sắp
[0] [1] [2] [3] [4] [5]
4
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 7
[1] [2] [3] [4] [5] [6]
0
10
20
30
40
50
60
70
[1] [2] [3] [4] [5] [6]
0
10
20
30
40
50
60
70
[1] [2] [3] [4] [5] [6]
Selection sort Algorithm
! Tìm phần tử
nhỏ nhất
trong phần
chưa được
sắp
[0] [1] [2] [3] [4] [5]
Phần đã sắp Phần chưa sắp
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 8
[1] [2] [3] [4] [5] [6]
0
10
20
30
40
50
60
70
[1] [2] [3] [4] [5] [6]
0
10
20
30
40
50
60
70
[1] [2] [3] [4] [5] [6]
Selection sort Algorithm
! Hoán vị
phần tử nhỏ
nhất trong
phần chưa
được sắp với
phần tử đầu
tiên trong
phần này [0] [1] [2] [3] [4] [5]
Phần đã sắp Phần chưa sắp
5
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 9
[1] [2] [3] [4] [5] [6]
0
10
20
30
40
50
60
70
[1] [2] [3] [4] [5] [6]
0
10
20
30
40
50
60
70
[1] [2] [3] [4] [5] [6]
Selection sort Algorithm
! Phần đã
được sắp xếp
của mảng
được tăng
thêm 1 phần
tử
[0] [1] [2] [3] [4] [5]
Phần đã sắp Phần chưa sắp
Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 10
[1] [2] [3] [4] [5] [6]
0
10
20
30
40
50
60
70
[1] [2] [3] [4] [5] [6]
0
10
20
30
40
50
60
70
[1] [2] [3] [4] [5] [6]
Selection sort Algorithm
! Tiếp tục
tương tự ... Phần tử
nhỏ nhất
[0] [1] [2] [3] [4] [5]
Phần đã sắp Phần chưa sắp