CH NG 3ƯƠ
CÁC THU T TOÁN S P X PẬ Ắ Ế
MỤC TIÊU

Khái niệm sắp xếp

Phát biểu bài toán sắp xếp

Sắp xếp trong và sắp xếp ngoài

Các phương pháp sắp xếp đơn giản

Phương pháp đổi chỗ liên tiếp

Phương pháp lựa chọn

Phương pháp chèn

Phương pháp phân đoạn – Quick Sort

Phương pháp vun đống – Heap Sort

Phương pháp sắp xếp trộn
KHÁI NIỆM SẮP XẾP

Đặt vấn đề

Cho dãy số

Cho danh sách tên học sinh


Đầu vào: 7 3 8 1 5

Đầu ra: 1 3 5 7 8
Đầu vào: Dãy n đối tượng, mỗi đối
tượng có một khóa sắp xếp

Đầu ra: Dãy n đối tượng được sắp
xếp theo trật tự của khóa.
BÀI
TOÁN
SẮP XẾP TRONG VÀ SẮP XẾP NGOÀI

Sắp xếp trong:

Dãy đối tượng được sắp có mặt đầy đủ ở bộ
nhớ trong (RAM).

Sắp xếp một mảng số, hoặc một danh sách
tuyến tính – Sắp tại chỗ

Sắp xếp ngoài:

Dãy đối tượng được sắp chưa có mặt đầy ở bộ
nhớ trong

Sắp xếp dữ liệu được lưu trong tệp.
CÁC THUẬT TOÁN SẮP XẾP HAY GẶP

Ba thuật toán sắp xếp đơn giản


5 -1 7 3 -4
-1 5 7 3 -4
-1 5 7 3 -4
-1 5 3 7 -4
-1 5 3 -4 7

Nhận xét

Sau lần duyệt vừa rồi ta thấy phần tử lớn nhất được
chuyển về cuối dãy, nghĩa là nó đứng đúng vị trí

Các phần tử còn lại vẫn chưa đúng thứ tự

Làm thế nào đây?
THUẬT TOÁN SẮP XẾP NỔI BỌT
X0 X1 X2 X3 X4
-1 5 3 -4 7
-1 5 3 -4 7
-1 3 5 -4 7
-1 3 -4 5 7

Đến đây ta được hai phần tử đứng đúng vị trí, các
phần tử còn lại thì không.

Vậy phải làm mấy lần nữa?

Hai lần nữa, ta được dãy sắp theo chiều tăng dần

Ôi chà… dễ ợt…!
THUẬT TOÁN SẮP XẾP NỔI BỌT

Mỗi lần duyệt so sánh các
cặp phần tử kế tiếp nếu trái
chiều thì đổi chỗ

Ứng dụng

Viết chương trình thực hiện các việc sau

Nhập vào một dãy n số nguyên (0<n<100, n nhập
từ bàn phím)

In dãy vừa nhập ra màn hình

Sắp xếp dãy theo chiều tăng dần bằng thuật toán
nổi bọt

In dãy vừa sắp ra màn hình

Yêu cầu: Mỗi công việc được viết bằng một thủ
tục
THUẬT TOÁN SẮP XẾP NỔI BỌT

Bài tập: Viết chương trình thực hiện các việc sau

Nhập vào một danh sách học sinh (0<n<100, n nhập
từ bàn phím), mỗi học sinh gồm các thông tin: Mã học
sinh, họ và tên, năm sinh và điểm trung bình.

Sắp xếp danh sách theo chiều tăng dần của tên học
sinh bằng thuật toán nổi bọt

3 -1 5 7 -4
-4 -1 5 7 3
-4 -1 5 7 3
-4 -1 5 7 3
Làm
mấy
lần?
THUẬT TOÁN SẮP XẾP LỰA CHỌN
-4 -1 5 7 3
-4 -1 3 7 5
-4 -1 3 7 5
-4 -1 3 5 7

Ví dụ 2

Cho dãy số nguyên như sau

Yêu cầu: Dựa vào ý tưởng trên, minh họa việc sắp
xếp dãy số theo chiều giảm dần.
THUẬT TOÁN SẮP XẾP LỰA CHỌN
X0 X1 X2 X3 X4 X5
53 -21 67 15 82 -14

Giải thuật
THUẬT TOÁN SẮP XẾP LỰA CHỌN
void sort(int X[ ], int n)
{
for (int i=0; i<n-1; i++)
{
int m=i;

Yêu cầu: Mỗi công việc được viết bằng một thủ
tục
THUẬT TOÁN SẮP XẾP LỰA CHỌN

Bài toán gợi ý tưởng:
THUẬT TOÁN SẮP XẾP CHÈN
3
4
7
9
3
4
6
7
9
3
4
6
7
9

Ví dụ

Cho dãy X có 5 số nguyên (n=5) như sau

Yêu cầu sắp xếp dãy số theo chiều tăng dần
THUẬT TOÁN SẮP XẾP CHÈN
X0 X1 X2 X3 X4
3 -1 7 -4 5
