Giải thuật Sắp xếp

2.2 BÀI TOÁN SẮP XẾP
2.2.1 Tầm quan trọng của bài toán sắp xếp
Sắp xếp một danh sách các đối tượng theo một thứ tự nào đó là một bài toán thường
được vận dụng trong các ứng dụng tin học. Ví dụ ta cần sắp xếp danh sách thí sinh
theo tên với thứ tự Alphabet, hoặc sắp xếp danh sách sinh viên theo điểm trung bình
với thứ tự từ cao đến thấp. Một ví dụ khác là khi cần tìm kiếm một đối tượng trong
một danh sách các đối tượng bằng giải thuật tìm kiếm nhị phân thì danh sách các
đối tượng này phải được sắp xếp trước đó.
Tóm lại sắp xếp là một yêu cầu không thể thiếu trong khi thiết kế các phần mềm.
Do đó việc nghiên cứu các phương pháp sắp xếp là rất cần thiết để vận dụng trong
khi lập trình.
2.2.2 Sắp xếp trong và sắp xếp ngoài
Sắp xếp trong là sự sắp xếp dữ liệu được tổ chức trong bộ nhớ trong của máy
tính, ở đó ta có thể sử dụng khả năng truy nhập ngẫu nhiên của bộ nhớ và do vậy sự
thực hiện rất nhanh.
Sắp xếp ngoài là sự sắp xếp được sử dụng khi số lượng đối tượng cần sắp xếp lớn
không thể lưu trữ trong bộ nhớ trong mà phải lưu trữ trên bộ nhớ ngoài. Cụ thể là
ta sẽ sắp xếp dữ liệu được lưu trữ trong các tập tin.
Chương này tập trung giải quyết vấn đề sắp xếp trong còn sắp xếp ngoài sẽ được
nghiên cứu trong chương IV.
2.2.3 Tổ chức dữ liệu và ngôn ngữ cài đặt
Các đối tượng cần được sắp xếp là các mẩu tin gồm một hoặc nhiều trường. Một
trong các trường được gọi là khóa (key), kiểu của nó là một kiểu có quan hệ thứ tự
(như các kiểu số nguyên, số thực, chuỗi ký tự ).
Danh sách các đối tượng cần sắp xếp sẽ là một mảng của các mẩu tin vừa nói ở trên.
Mục đích của việc sắp xếp là tổ chức lại các mẩu tin sao cho các khóa của chúng
được sắp thứ tự tương ứng với quy luật sắp xếp.
Ðể trình bày các ví dụ minh họa chúng ta sẽ dùng PASCAL làm ngôn ngữ thể hiện
và sử dụng khai báo sau:

w
e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D
F
-
X
C
h
a

Giải thuật Sắp xếp

PROCEDURE Swap(var x,y:RecordType);
VAR temp : RecordType;
BEGIN
temp := x;
x := y;
y := temp;
END;
Cần thấy rằng thủ tục Swap lấy O(1) thời gian vì chỉ thực hiện 3 lệnh gán nối tiếp
nhau.
2.3 CÁC PHƯƠNG PHÁP SẮP XẾP ÐƠN GIẢN
Các giải thuật đơn giản thường lấy O(n
2
) thời gian để sắp xếp n đối tượng và các
giải thuật này thường chỉ dùng để sắp các danh sách có ít đối tượng.
Với mỗi giải thuật chúng ta sẽ nghiên cứu các phần: giải thuật, ví dụ, chương trình
và phân tích đánh giá.
2.3.1 Sắp xếp chọn (Selection Sort)
2.3.1.1 Giải thuật
Ðây là phương pháp sắp xếp đơn giản nhất được tiến hành như sau:
• Ðầu tiên chọn phần tử có khóa nhỏ nhất trong n phần tử từ a[1] đến a[n]
và hoán vị nó với phần tử a[1].
• Chọn phần tử có khóa nhỏ nhất trong n-1phần tử từ a[2] đến a[n] và hoán
vị nó với a[2].
• Tổng quát ở bước thứ i, chọn phần tử có khoá nhỏ nhất trong n-i+1 phần
tử từ a[i] đến a[n] và hoán vị nó với a[i].
• Sau n-1 bước này thì mảng đã được sắp xếp.
Phương pháp này được gọi là phương pháp chọn bởi vì nó lặp lại quá trình chọn
phần tử nhỏ nhất trong số các phần tử chưa được sắp.

e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D
F
-
X
C
h
a
n


Khóa
a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]
Bước
Ban đầu 5 6 2 2 10 12 9 10 9 3
2
Bước 1 6 5 2 10 12 9 10 9 3
2
Bước 2 5 6 10 12 9 10 9 3
3
Bước 3 6 10 12 9 10 9 5
5
Bước 4 10 12 9 10 9 6
6
Bước 5 12 9 10 9 10
9
Bước 6 12 10 9 10
9
Bước 7 10 12 10
10
Bước 8 12 10
10
Bước 9 12
Kết quả 2 2 3 5 6 9 9 10 10 12

Hình 2-1: Sắp xếp chọn
2.3.1.2 Chương trình:
PROCEDURE SelectionSort;
VAR
i,j,LowIndex: integer;

).
2.3.2 Sắp xếp xen (Insertion Sort)
2.3.2.1 Giải thuật
Trước hết ta xem phần tử a[1] là một dãy đã có thứ tự.
Nguyễn Văn Linh Trang
21
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.
d

e
r
w
w
w
.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
.
.
Giải thuật Sắp xếp

• Bước 1, xen phần tử a[2] vào danh sách đã có thứ tự a[1] sao cho a[1],
a[2] là một danh sách có thứ tự.
• Bước 2, xen phần tử a[3] vào danh sách đã có thứ tự a[1], a[2] sao cho
a[1], a[2], a[3] là một danh sách có thứ tự.
• Tổng quát, bước i, xen phần tử a[i+1] vào danh sách đã có thứ tự
a[1],a[2], a[i] sao cho a[1], a[2], a[i+1] là một danh sách có thứ tự.

2 2 5 6

Bước 4
2 2 5 6 10

Bước 5
2 2 5 6 10 12

Bước 6
2 2 5 6 9 10 12

Bước 7
2 2 5 6 9 10 10 12

Bước 8
2 2 5 6 9 9 10 10 12

Bước 9
2 2 3 5 6 9 9 10 10 12

Hình 2-2: Sắp xếp xen
2.3.2.2 Chương trình
PROCEDURE InsertionSort;
VAR
i,j: integer;
Nguyễn Văn Linh Trang
22
Click to buy NOW!
P
D

.
c
o
m
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

V
i
e
w
e
r
w
w
w
.
d
o
c

ta có
2
1)-n(n
T(n) =
∑
=
=
n
2i
1)-(i
tức là O(n
2
).
2.3.3 Sắp xếp nổi bọt (Bubble Sort)
2.3.3.1 Giải thuật
Chúng ta tưởng tượng rằng các mẩu tin được lưu trong một mảng dọc, qua quá trình
sắp, mẩu tin nào có khóa “nhẹ” sẽ được nổi lên trên. Chúng ta duyệt tòan mảng, từ
dưới lên trên. Nếu hai phần tử ở cạnh nhau mà không đúng thứ tự tức là nếu phần tử
“nhẹ hơn” lại nằm dưới thì phải cho nó “nổi lên” bằng cách đổi chỗ hai phần tử này
cho nhau. Cụ thể là:
• Bước 1: Xét các phần tử từ a[n] đến a[2], với mỗi phần tử a[j], so sánh
khoá của nó với khoá của phần tử a[j-1] đứng ngay trước nó. Nếu khoá
của a[j] nhỏ hơn khoá của a[j-1] thì hoán đổi a[j] và a[j-1] cho nhau.
• Bước 2: Xét các phần tử từ a[n] đến a[3], và làm tương tự như trên.
• Sau n-1 bước thì kết thúc.
Ví dụ 2-3: Sắp xếp mảng gồm 10 mẩu tin đã cho trong ví dụ 2-1.
Bước 1: Xét a[10] có khoá là 3, nhỏ hơn khoá của a[9] nên ta hoán đổi a[10] và a[9]
cho nhau. Khoá của a[9] bây giờ là 3 nhỏ hơn khoá của a[8] nên ta hoán đổi a[9] và
a[8] cho nhau. Khoá của a[8] bây giờ là 3 nhỏ hơn khoá của a[7] nên ta hoán đổi
a[8] và a[7] cho nhau. Khoá của a[7] bây giờ là 3 nhỏ hơn khoá của a[6] nên ta hoán

.
d
o
c
u
-
t
r
a
c
k
.
c
o
m
Click to buy NOW!
P
D
F
-
X
C
h
a
n
g
e

V
i