Bài giảng Thiết kế và đánh giá thuật toán - Chặn dưới sắp xếp - Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán
Chặn Dưới Sắp Xếp
TS. Lê Nguyên Khôi
Trường Đại Học Công Nghệ - ĐHQGHN
Nội Dung

 Chặn trên (upper bound - 
)

 Chặn dưới (lower bound - )

 Sắp xếp trong thời gian tuyến tính

 Sắp xếp đếm (Counting sort)

 Sắp xếp cơ số (Radix sort)

 Sắp xếp giỏ (Bucket sort)
1
Chặn Trên

 Bài toán X: dữ liệu đầu vào 	xây dựng
thuật toán chạy trong thời gian 
(())

 (): thể hiện độ phức tạp (hay độ khó) 
để giải bài toán X

 Mục tiêu: xác định   càng nhỏ càng tốt

 Chặn trên (
) giúp xác định giải bài toán
X khó cỡ nào
2
Chặn Dưới

 Giải bài toán X, bất cứ thuật toán nào
cũng chạy trong thời gian (())

 Mục tiêu: xác định   càng lớn càng tốt

 Chặn dưới () giúp xác định thuật toán
giải bài toán X đã đủ tốt chưa

 Ví dụ:

 Thuật toán chạy trong thời gian 
( log  )

 Chặn dưới ( log ) để giải bài toán

 Cải tiến thuật toán để thu hẹp khoảng log 
3
Chặn Của Sắp Xếp

 Chặn trên 
  / dưới ()

 Nổi bọt (bubble sort)

 Chèn (insertion sort)

 Lựa chọn (selection sort)

 Chặn trên 
  log  / dưới ( log )

Gộp (merge sort)

 Cây thứ tự bộ phận (heap sort)

 Nhanh (quick sort) – trường hợp trung bình
4
Chặn Dưới Sắp Xếp

 Các thuật toán sắp xếp vừa đề cập:

 Đều dựa trên so sánh giữa các phần tử

 Chặn dưới ( log )

 Sắp xếp so sánh (comparison-based sort)

 Không khác biệt về độ phức tạp

 Khác biệt về thời gian chạy theo một hằng số

 Một số thuật toán không dựa trên so 
sánh giữa các phần tử

 Không áp dụng chặn dưới ( log )
5
Chặn Dưới Sắp Xếp – Chứng Minh

 Sử dụng mô hình Cây Quyết Định

 Cây nhị phân

 Nút trong ứng với phép so sánh 2 phần tử

 Nhánh trái ứng với kết quả nhỏ hơn bằng

 Nhánh phải ứng với kết quả lớn hơn

 Lá ứng với lời giải (thứ tự các phần tử)
6
Cây Quyết Định
Sắp xếp 〈, ,  , 〉
Nút trong :  với ,  ∈ 1, 2, ,  thể hiện so sánh  với 
Cây con trái thể hiện các bước so sánh nếu   
Cây con phải thể hiện các bước so sánh nếu   
Lá thể hiện hoán vị thứ tự
7










Cây Quyết Định – Ví Dụ
Sắp xếp , ,   6,8,5
Thăm các nút: 1: 2 , 2: 3 , 1: 3 ⇒ (312)
So sánh: 6 % 8 , 8  5 , 6 % 5 ⇒ (5 % 6 % 8)
8










Cây Quyết Định – Ví Dụ
Sắp xếp , ,   6,8,5
Mỗi lá là một hoán vị & 1 , & 2 , , & 
thể hiện thứ tự '()  '   ⋯  ' 
Có 3 phần tử, số lượng hoán vị (lá) là 3!  6 lá
9










Cây Quyết Định – Mô Hình
Có thể sử dụng cây quyết định để mô 
phỏng quá trình thực hiện của bất ký thuật 
toán sắp xếp so sánh nào:

 Một cây cho mỗi dữ liệu đầu vào cỡ . 

 Cây chứa thông tin các bước so sánh.

 Thời gian chạy của thuật toán là độ dài 
đường đi từ gốc đến lá.

 Thời gian chạy xấu nhất là độ cao cây
10
Cây Quyết Định – Chặn Dưới Sắp Xếp

 Định lý:

 Bất cứ cây quyết định có thể sắp xếp  phần
tử có độ cao ( log )

 Chứng minh:

 Cây quyết định độ cao ℎ, với + lá

Mỗi hoán vị của ! nằm tại một lá nào đó

Do đó ! ≤ +

 Cây nhị phân độ cao ℎ có nhiều nhất 2, lá.

 Do đó ! ≤ + ≤ 2,.
ℎ ≥ log ! = ( log )
11
Cây Quyết Định – Chặn Dưới Sắp Xếp
Hệ Quả:

 Sắp xếp cây thứ tự bộ phận và sắp xếp
gộp là thuật toán sắp xếp so sánh tối ưu
12
Sắp Xếp Trong Thời Gian Tuyến Tính

 Sắp xếp không dựa trên so sánh giữa
các phần tử

 Không áp dụng chặn dưới   log 

 Ví dụ

 Sắp xếp đếm (Counting sort)

 Sắp xếp cơ số (Radix sort)

 Sắp xếp giỏ (Bucket sort)
13
Sắp Xếp Đếm (Counting Sort)

 Giả thiết

 Phần tử là số nguyên trong khoảng [1, /]

 Khi / = 
  , thời gian chạy 1 

 Ý tưởng

 Với mỗi phần tử 2, xác định số phần tử < 2

 Ví dụ:

có 17 phần tử nhỏ hơn 2

2 sẽ được xếp vào vị trí thứ 18

 Nếu có các phần tử trùng nhau, không thể
xếp vào cùng vị trí
14
Sắp Xếp Đếm – Mã Giả
for  ← 1 to / do
4[] 	← 0
for  ← 1 to  do
4[6[]] 	← 4[6[]] 	+ 	1
for  ← 2 to / do
4[] 	← 4[] 	+ 	4[– 1]
for  ←  downto 1 do
9[4[6[]]] 	← 6[]
4[6[]] 	← 4[6[]]	– 1
15
Sắp Xếp Đếm – Phân Tích
for  ← 1 to / do 1(/)
4[] 	← 0
for  ← 1 to  do 1()
4[6[]] 	← 4[6[]] 	+ 	1
for  ← 2 to / do 1(/)
4[] 	← 4[] 	+ 	4[– 1]
for  ←  downto 1 do 1()
9[4[6[]]] 	← 6[]
4[6[]] 	← 4[6[]]	– 1 = 1( + /)
16
Sắp Xếp Đếm – Minh Họa

 Input: 6[1	. . ], với 6[] ∈ {1, 2,  , /}

 Output: 9[1	. . ], được sắp xếp

 Bộ nhớ phụ 4 1	. .  đếm số phần tử

4  =  tương ứng phần tử có giá trị 
xuất hiện  lần

 Minh họa: 6 = 4, 1, 3, 4, 3
17
6 = 4, 1, 3, 4, 3
Sắp Xếp Đếm – Minh Họa
18
Sắp Xếp Đếm – Bài Tập
6  6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2
19
Sắp Xếp Ổn Định

 Đảm bảo thứ tự ban đầu của các phần tử
bằng nhau

 Sắp xếp đếm là sắp xếp ổn định

 Thuật toán sắp xếp nào có tính chất này?

Sắp xếp chèn

Sắp xếp lựa chọn

Sắp xếp gộp

Sắp xếp nhanh
20
Sắp Xếp Cơ Số (Radix Sort)

 Sắp xếp theo từng cơ số

 Bắt đầu từ cơ số ít quan trọng nhất

 Sử dụng sắp xếp ổn định để sắp xếp mỗi
cơ số
21
Sắp Xếp Cơ Số – Minh Họa
22
Sắp Xếp Cơ Số – Thời Gian Chạy

 Phụ thuộc việc lựa chọn thuật toán nào
để sắp xếp cơ số.

 Chọn sắp xếp đếm: 1 >  + /
23
Sắp Xếp Giỏ (Bucket Sort)

 Giả thiết dữ liệu trong khoảng [0, 1)

 Tạo ngẫu nhiên

 Phân bố đồng đều

 Độc lập với nhau

 Ý tưởng

 Chia khoảng dữ liệu thành  phần bằng nhau

 Phân bố  dữ liệu vào các giỏ

 Sắp xếp từng giỏ

 Liệt kê phần tử trong giỏ
24
Sắp Xếp Giỏ

 Trường hợp tốt nhất, mỗi dữ liệu được
phân vào một giỏ

 Trường hợp khác, sắp xếp từng giỏ sử
dụng sắp xếp chèn

 Dữ liệu không phân bố đồng đều

 Xác định khoảng của mỗi giỏ

 Sau khi phân bố  dữ liệu vào giỏ, cỡ mỗi giỏ
tương đương nhau
25