ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA CÔNG NGHỆ THÔNG TIN

BÀI THU HOẠCH MÔN HỌC PHƢƠNG PHÁP
NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC
LỚP CAO HỌC KHOA HỌC MÁY TÍNH KHÓA 22
Giảng viên: GS.TSKH. Hoàng Văn Kiếm
ĐỀ TÀI
NGUYÊN LÝ SÁNG TẠO ỨNG DỤNG
TRONG MỘT SỐ THUẬT TOÁN SẮP XẾP NỘI
Học viên: Trần Huy Quang
Mã số: 12 11 058

TP.HCM, 12-2012 MỤC LỤC
THUẬT TOÁN SẮP XẾP 4
I. Sắp xếp theo phương pháp chọn 5
1. Phương pháp chọn trực tiếp – Selection Sort 5
2. Phương pháp vun đống – Heap Sort 6
3. Đánh giá 9
II. Sắp xếp theo phương pháp chèn 10
1. Phương pháp chèn trực tiếp – Insertion Sort 10
2. Phương pháp độ dài bước giảm dần - Shell Sort 11
3. Đánh giá 13
III. Phương pháp sắp xếp phân hoạch - Quick Sort 14
1. Ý tưởng 14

24. Nguyên lý sử dụng trung gian 20
25. Nguyên lý tự phục vụ 20
26. Nguyên lý sao chép (Copy) 20
27. Nguyên lý “rẻ” thay cho “đắt” 20
28. Thay thế sơ đồ cơ học 20
29. Sử dụng các kết cấu khí và lỏng 21
30. Sử dụng vỏ dẻo và màng mỏng 21
31. Sử dụng các vật liệu nhiều lỗ 21
32. Nguyên lý thay đổi màu sắc 21
33. Nguyên lý đồng nhất 21
34. Nguyên lý loại bỏ hoặc tái sinh từng phần 21
35. Thay đổi các thông số lý hóa của đối tượng 22
36. Sử dụng chuyển pha 22
37. Sử dụng sự nở nhiệt 22
38. Sử dụng các chất oxy hóa 22
39. Sử dụng môi trường trơ 22
40. Sử dụng các vật liệu hợp thành (composite) 22
TÀI LIỆU THAM KHẢO 23
4

THUẬT TOÁN SẮP XẾP
Sắp xếp là quá trình bố trí lại các phần tử của một tập đối tượng theo một thứ tự
được ấn định, chẳng hạn tăng dần hay giảm dần đối với một dãy số. Với một cấu trúc đã
được sắp xếp thì rất thuận tiện khi thực hiện các tác vụ như tìm kiếm, duyệt cấu trúc…
Có hai loại thuật toán sắp xếp: Sắp xếp nội và Sắp xếp ngoại.
Sắp xếp nội
- Toàn bộ dữ liệu được đưa vào bộ nhớ trong.
- Kích thước dữ liệu cần sắp xếp không lớn lắm.
- Thời gian sắp xếp được thực hiện rất nhanh.
Sắp xếp ngoại

5

I. Sắp xếp theo phƣơng pháp chọn
1. Phƣơng pháp chọn trực tiếp – Selection Sort
a) Ý tưởng
Chọn phần tử nhỏ nhất trong N phần tử ban đầu, đưa phần tử này về vị trí đúng ở
đầu dãy hiện hành. Lúc này ta có dãy con đầu a
1
đã có thứ tự, nên không cần quan tâm
đến phần tử này nữa.
Xét dãy con sau chỉ còn N-1 phần tử cần sắp xếp, lặp lại thao tác trên để đưa phần
tử nhỏ nhất về đầu dãy hiện hành. Ta được dãy con đầu a
1
, a
2
đã có thứ tự, chỉ cần sắp
xếp dãy con sau có N-2 phần tử còn lại.
Lặp lại như trên cho đến khi dãy con cần sắp xếp chỉ còn một phần tử, ta được dãy
kết quả có thứ tự.
b) Thuật toán
Bước 1: i := 1
Bước 2: Tìm phần tử a
min
nhỏ nhất trong dãy hiện hành a
i
, a
i+1
, …, a
N


45
40
55
90
85
35
i=3
10
25
35
40
55
90
85
45
i=4
10
25
35
40
55
90
85
45
i=5
10
25
35
40
45


6

d) Độ phức tạp của thuật toán
- Số phép so sánh: tại mỗi lượt thứ i, cần thực hiện N-i phép so sánh để tìm phần
tử nhỏ nhất trong dãy con chưa có thứ tự. Số phép so sánh không phụ thuộc vào
tình trạng của dãy ban đầu, do đó tổng số phép so sánh là n(n-1)/2.
- Số phép gán: tại mỗi lượt, cần thực hiện ba phép gán để hoán vị a
min
với a
i
, do
đó cần 3n(n-1)/2 phép gán. Tuy nhiên điều này phụ thuộc vào tình trạng ban
đầu của dãy số, nếu dãy ban đầu đã có thứ thự thì không cần thực hiện phép gán
nào.
- Độ phức tạp của thuật toán là T(N) = O(N
2
).
2. Phƣơng pháp vun đống – Heap Sort
a) Ý tưởng
Sử dụng một cấu trúc dữ liệu gọi là Heap cho phép tích lũy các thông tin về sự so
sánh giữa các phần tử trong quá trình sắp xếp.
Cấu trúc Heap
Là một cây nhị phân gần đầy đủ, cài đặt bằng mảng một chiều a
l
a
l+1
…a
r
, với các Cấu trúc heap được cài đặt bằng một mảng một chiều:
30
26
22
21
12
19
15
16
14
8

30
26
22
21
12
19
15
16
14
8
0
1
2
3

a
l
a
l+1
…a
r
Với l=0 và r=N-1
Giai đoạn 2: Sắp xếp dãy số dựa trên heap
Bước 1: Hoán vị phần tử lớn nhất - nút gốc của heap với phần tử cuối dãy
Bước 2: Loại bỏ phần tử lớn nhất ra khỏi heap: r=r-1
Hiệu chỉnh phần còn lại của dãy là a
l
a
l+1
…a
r-1
thành heap
Bước 3: Nếu r>l: lặp lại Bước 2
Ngược lại: Dừng
Dựa theo tính chất 4 của heap, thực hiện Giai đoạn 1 bằng cách bắt đầu từ heap
mặc nhiên là dãy a
m+1
, a
m+2
,…, a
N-1
(với m=N/2). Lần lượt thêm vào đầu heap các phần
tử a
m
, a

6
4
5
l=3
12
2
8
15
1
6
4
5
12
2
8
15
1
6
4
5
l=2
12
2
8
15
1
6
4
5
8

1
6
4
2
15
12
8
5
1
6
4
2
Dãy kết quả
15
12
8
5
1
6
4
2
Giai đoạn 2: Sắp xếp dãy số dựa trên heap
Heap ban đầu
15
12
8
5
1
6
4

5
6
2
1
4
12
15
r=5
4
5
6
2
1
8
12
15
Hiệu chỉnh lại heap
6
5
4
2
1
8
12
15
r=4
1
5
4
2

15
r=2
1
2
4
5
6
8
12
15
Hiệu chỉnh lại heap
2
1
4
5
6
8
12
15
r=1
1
2
4
5
6
8
12
15
r=l: Dừng
1

mức i+1, do đó phần tử ở mức 0 tức là nút gốc của cây luôn là phần tử lớn nhất trong
dãy. Khi loại phần tử gốc ra khỏi cây, cần phải cập nhật lại cây để đảm bảo tính chất
của heap, tuy nhiên việc cập nhật chỉ xảy ra một cách cục bộ đối với những nhánh liên
quan đến phần tử vừa loại bỏ, còn các nhánh khác vẫn giữ nguyên. Như vậy bước tiếp
theo của thuật toán có thể sử dụng lại kết quả của sự so sánh ở bước hiện tại.
- Nguyên lý linh động
Dãy số được biểu diễn một cách tự nhiên bằng cấu trúc mảng một chiều, nhưng với
heap, dãy số có thể biểu diễn dưới dạng cây phân cấp. Với đặc trưng của cấu trúc cây
gồm nhiều nhánh, dãy số được chia thành nhiều thành phần độc lập dưới dạng các
nhánh và có khả năng dịch chuyển đối với nhau, mỗi khi cập nhật heap trong quá trình
sắp xếp.
- Nguyên lý chuyển sang chiều khác
Ở mỗi bước sắp xếp, Selection Sort hoạt động trên toàn bộ chiều dài của dãy con
còn lại nên số lượng phép so sánh luôn nhiều nhất. Hạn chế đó là do cấu trúc của mảng
một chiều. Trong khi Heap Sort sử dụng cấu trúc heap là cấu trúc cây - nhiều chiều, tại
mỗi bước, việc so sánh chỉ xảy ra trong nhánh liên quan nên có thể giảm thiểu số phép
so sánh.

10

- Thay thế sơ đồ cơ học
Phương pháp Heap Sort sử dụng cấu trúc cây phân cấp thay cho mảng một chiều
với các phần tử cố định. Như vậy các phần tử đồng nhất trong dãy số đã được chuyển
sang cấu trúc không đồng nhất, mỗi phần tử được phân cấp qua giá trị của nó.
- Nguyên lý loại bỏ hoặc tái sinh từng phần
Cấu trúc heap có nút gốc luôn là phần tử lớn nhất trong dãy hiện hành, nếu loại bỏ
phần tử này khỏi cây, có nghĩa là đưa nó về vị trí đúng thì sau đó không cần quan tâm
đến nó nữa. Sau khi loại bỏ nút gốc, heap cần phải phục hồi với những phần tử còn lại,
tuy nhiên chi phí cho thao tác này không lớn, do việc cập nhật chỉ xảy ra cục bộ trên
những nhánh liên quan trong cây.

và a
k
nếu a
k-1
≤ a
i
< a
k
.
- Dời các phần tử a
k
, a
k+1
, …, a
i-1
về phía sau một vị trí và chèn a
i
vào vị trí k,
ta được dãy a
1
, a
2
, …, a
i-1
có thứ tự.
b) Thuật toán
Bước 1: i := 2
Bước 2: x := a
i


2
8
5
1
6
4
15
i=1
12
2
8
5
1
6
4
15
i=2
2
12
8
5
1
6
4
15
i=3
2
8
12
5

15
i=7
1
2
4
5
6
8
12
15
i=8
1
2
4
5
6
8
12
15
Dãy kết quả
1
2
4
5
6
8
12
15
d) Độ phức tạp của thuật toán
- Trong mỗi lần lặp, cần thực hiện một phép so sánh và hai phép gán. Tổng số

Dãy con thứ nhất: a
h
, a
2h
, a
3h
, …
Thực hiện sắp xếp các phần tử trong cùng dãy con ta có các phần tử được đưa về vị
trí đúng tương đối – có thứ tự trong dãy con đang xét. Sau đó giảm khoảng cách h để
tạo thành các dãy con mới, như vậy tạo cơ hội so sánh một phần tử với nhiều phần tử
12

khác trước đó không nằm cùng dãy con. Sắp xếp những dãy con mới này. Lặp lại cho
đến khi h=1, ta được dãy kết quả có thứ tự.
Cách lựa chọn khoảng cách h và số bước sắp xếp là k thỏa:
h
i
> h
i+1
, h
k
=1, với i=1 k
Khoảng cách giữa các phần tử trong một dãy con ở bước sau phải nhỏ hơn bước
trước. Sau k bước, khoảng cách bằng 1 (lúc này mỗi dãy con chỉ có một phần tử).
Theo Knuth đề nghị: h
i
= (h
i-1
- 1)/3, h
k

Chọn k=3 và các khoảng cách h
1
=5, h
2
=3, h
3
=1
- h=5

12
2
8
5
1
6
4
15
Sắp xếp các dãy con theo phương pháp Chèn trực tiếp

6
2
8
5
1
12
4
15
- h=3

6


1
2
4
5
6
8
12
15
- Dừng do h=1
d) Độ phức tạp của thuật toán
- Hiệu quả thuật toán phụ thuộc vào các dãy con với các độ dài được chọn.
- Khi chọn theo công thức Knuth: h
i
= (h
i-1
-1)/2, h
k
=1, k=log
2
n-1, thuật toán có
độ phức tạp là T(N) = O(N
1.2
).
3. Đánh giá
Hai thuật toán Insertion Sort và Shell Sort cùng dựa trên ý tưởng chèn một phần tử
vào một dãy có thứ tự. Tuy nhiên độ phức tạp của thuật toán Shell Sort là O(N
1.2
) nhỏ
hơn rất nhiều so với độ phức tạp O(N

, phân
hoạch dãy này thành ba dãy con liên tiếp:
Dãy con 1: a
k
< x với k=1…i
Dãy con 2: a
k
= x với k=i…j (đã được sắp thứ tự)
Dãy con 3: a
k
> x với k=j…N
Nếu dãy con 1 và 3 chỉ có một phần tử thì dãy a
1
, a
2
, …, a
N
đã được sắp xếp.
Ngược lại, dãy con 1 và 3 có nhiều hơn một phần tử, tiếp tục phân hoạch dãy con 1
và 3 thành các dãy con tương tự như trên.
Phần tử x được chọn có tác động rất nhiều đến hiệu quả của thuật toán, vì nó quyết
định số lần phân hoạch dãy. Số lần phân hoạch sẽ ít nhất nếu chọn được phần tử x có độ
lớn trung bình của dãy. Tuy nhiên việc chọn được phần tử x như vậy là rất khó, nên
người ta thường chọn phần tử ở giữa dãy làm mốc phân hoạch.
Khi đó, với l=1 và r=N thì a
k
là phần tử mốc, với k=(l+r)/2.
2. Thuật toán
Bước 1: Phân hoạch dãy a
l

, a
i+1
, …, a
r

3. Minh họa
Cho dãy 8 phần tử: 12 2 8 5 1 6 4 15
- Phân hoạch đoạn l=1, r=8, x=a
4
=5
15 12
2
8
5
1
6
4
15

4
2
1
5
8
6
12
15

6
=6

1
2
4
5
8
6
12
15

1
2
4
5
6
8
12
15
1
2
4
5
6
8
12
15
- Phân hoạch đoạn l=7, r=8, x=a
7

2
N).
Độ phức tạp trung bình của thuật toán: O(Nlog
2
N).
5. Đánh giá
Như cái tên Quick Sort, thuật toán có chi phí trong trường hợp tốt nhất chỉ là log
2
N.
Điều này đạt được nhờ kết hợp kỹ thuật chia để trị cùng với đệ quy. Có thể nhận thấy
những nguyên lý sáng tạo trong thiết kế thuật toán này như sau.
- Nguyên lý phân nhỏ
Dãy ban đầu được phân nhỏ thành các dãy con với những đặc trưng riêng biệt phục
vụ cho quá trình sắp xếp. Sau đó đến lượt các dãy con được xử lý độc lập, với cùng một
cách thức như trên, nghĩa là tăng mức độ phân nhỏ các dãy con. Cho đến khi không thể
phân nhỏ các dãy con được nữa thì dãy ban đầu đã được sắp thứ tự.
- Nguyên lý “tách riêng”
Trong quá trình sắp xếp, phép so sánh là thao tác được thực hiện nhiều nhất, đặc
biệt là so sánh khóa x với các phần tử khác trong dãy. Sau khi phân hoạch, các phần tử
có giá trị bằng với khoá x được tách riêng ra, sau đó thì không cần quan tâm đến nữa.
như vậy giúp giảm những phép so sánh không cần thiết.
- Nguyên lý phẩm chất cục bộ
Dãy số cần sắp thứ tự là một cấu trúc đồng nhất – mảng một chiều, được chuyển
thành đối tượng không đồng nhất với mỗi phần có chức năng khác nhau, cụ thể là so
với phần tử khóa x, tạo điều kiện thuận lợi cho bước tiếp theo trong quá trình sắp xếp.
17

PHỤ LỤC: CÁC NGUYÊN LÝ SÁNG TẠO
1. Nguyên lý phân nhỏ
- Chia đối tượng thành các phần độc lập.

- Bù trừ trọng lượng của đối tượng bằng tương tác với môi trường như sử dụng
các lực thủy động, khí động…
9. Nguyên lý gây ứng suất sơ bộ
- Gây ứng suất trước đối với đối tượng để chống lại ứng suất không cho phép
hoặc không mong muốn khi đối tượng làm việc (hoặc gây ứng suất trước để
khi làm việc sẽ dùng ứng suất ngược lại).
10. Nguyên lý thực hiện sơ bộ
- Thực hiện trước sự thay đổi cần có, hoàn toàn hoặc từng phần đối với đối
tượng.
- Cần sắp xếp đối tượng trước, sao cho chúng có thể hoạt động từ vị trí thuận
lợi nhất, không mất thời gian dịch chuyển.
11. Nguyên lý dự phòng
- Bù đắp độ tin cậy không lớn của đối tượng bằng cách chuẩn bị các phuơng
tiện báo động, ứng cứu, an toàn.
12. Nguyên lý đẳng thế
- Thay đổi điều kiện làm việc để không phải nâng lên hay hạ xuống các đối
tượng.
13. Nguyên lý đảo ngƣợc
- Thay vì hành động như yêu cầu của bài toán, hành động ngược lại (ví dụ
không làm nóng mà làm lạnh đối tượng).
- Làm phần chuyển động của đối tượng (hay mội trường bên ngoài) thành
đứng yên và ngược lại phần đứng yên thành chuyển động.
14. Nguyên lý cầu (tròn) hóa
- Chuyển những phần thẳng của đối tượng thành cong, mặt phẳng thành mặt
cầu, kết cấu hình hộp thành kết cấu hình cầu.
- Sử dụng các con lăn, viên bi, vòng xoắn.
- Chuyển sang chuyển động quay, sử dụng lực ly tâm.
15. Nguyên lý linh động
- Cần thay đổi các đặc trưng của đối tượng hay môi trường bên ngoài sao cho
chúng tối ưu trong từng giai đoạn làm việc.

- Khắc phục vận hành không tải và trung gian.
- Chuyển chuyển động tịnh tiến qua lại thành chuyển động quay.

20

21. Nguyên lý “vƣợt nhanh”
- Vượt qua những giai đoạn có hại hoặc nguy hiểm với vận tốc lớn.
- Vượt nhanh để có được hiệu ứng cần thiết.
22. Nguyên lý biến hại thành lợi
- Sử dụng những tác nhân có hại (ví dụ tác động có hại của môi trường) để thu
được hiệu ứng có lợi.
- Khắc phục tác nhân có hại bằng cách kết hợp nó với tác nhân có hại khác.
- Tăng cường tác nhân có hại đến mức nó không còn có hại nữa.
23. Nguyên lý quan hệ phản hồi
- Thiết lập quan hệ phản hồi.
- Nếu đã có quan hệ phản hồi, hãy thay đổi nó.
24. Nguyên lý sử dụng trung gian
- Sử dụng đối tượng trung gian, chuyển tiếp.
25. Nguyên lý tự phục vụ
- Đối tượng phải tự phục vụ bằng cách thực hiện các thao tác phụ trợ, sửa
chữa.
- Sử dụng phế liệu, chất thải, năng lượng dư.
26. Nguyên lý sao chép (Copy)
- Thay vì sử dụng cái không được phép, phức tạp, đắt tiền, không tiện lợi hoặc
dễ vỡ, sử dụng bản sao.
- Thay thế đối tượng hay hệ các đối tượng bằng bản sao quang học (ảnh, hình
vẽ) với tỉ lệ cần thiết.
- Nếu không thể sử dụng bản sao quang học ở vùng biểu kiến (vùng ánh sáng
nhìn thấy được bằng mắt thường), chuyển sang sử dụng các bản sao hồng
ngoại hoặc tử ngoại.

33. Nguyên lý đồng nhất
- Những đối tượng, tương tác với các đối tượng cho trước, phải được làm từ
cùng một vật liệu (hoặc từ vật liệu gần về các tính chất) với các vật liệu chế
tạo đối tượng cho trước.
34. Nguyên lý loại bỏ hoặc tái sinh từng phần
- Phần đối tượng đã hoàn thành nhiệm vụ hoặc trở nên không cần thiết phải tự
phân hủy (hoà tan, bay hơi…) hoặc phải biến dạng.
- Các phần mất mát của đối tượng phải được phục hồi trực tiếp trong quá trình
22

làm việc.
35. Thay đổi các thông số lý hóa của đối tƣợng
- Thay đổi trạng thái của đối tượng.
- Thay đổi nồng độ hay độ đậm đặc.
- Thay đổi độ dẻo.
- Thay đổi nhiệt độ, thể tích.
36. Sử dụng chuyển pha
- Sử dụng các hiện tượng, nảy sinh trong các quá trình chuyển pha như thay
đổi thể tích, tỏa hay hấp thu nhiệt lượng…
37. Sử dụng sự nở nhiệt
- Sử dụng sự nở (hay co) nhiệt của các vật liệu.
- Nếu đã dùng sự nở nhiệt, sử dụng với vật liệu có các hệ số nở nhiệt khác
nhau.
38. Sử dụng các chất oxy hóa
- Thay không khí thường bằng không khí giàu Oxy.
- Thay không khí giàu Oxy bằng chính Oxy.
- Dùng các bức xạ ion hóa tác động lên không khí hoặc oxy.
- Thay oxy giàu Ôzôn (hoặc ôxy bị ion hoá) bằng chính ôzôn.
39. Sử dụng môi trƣờng trơ
- Thay môi trường thông thường bằng môi trường trung hòa.