1
CHƯƠNG 5
CÁC THUẬT TOÁN SẮP XẾP
2/77
NỘI DUNG

Khái niệm sắp xếp

Các thuật sắp xếp đơn giản

Các thuật toán sắp xếp nhanh
3/77
5.1 KHÁI NIỆM SẮP XẾP

Đặt vấn đề

Cho dãy số

Cho danh sách tên học sinh

81 52 73 21 44
81 73 52 44 21
Hùng
Thắng
An
Bình
Hoàng
An
Bình
Hoàng
Hùng

Thuật toán sắp xếp lựa chọn (Selectsort)

Thuật toán sắp xếp chèn (Insertsort)

Thuật toán sắp xếp nổi bọt (Bubblesort)
7/77

Ý tưởng thuật toán

Dựa vào thuật toán tìm MAX, MIN

Ở lần duyệt thứ i, với 0<=i<n-1 tìm ra phần
tử nhỏ nhất đổi chỗ cho phần tử thứ i.

Sau n-1 lượt dãy được sắp xếp

Ví dụ Cho mảng a có 5 số nguyên (n=5)
5.2.1 THUẬT TOÁN SẮP XẾP LỰA CHỌN
a0 a1 a2 a3 a4
3 -1 7 5 -4
8/77
5.2.1 THUẬT TOÁN SẮP XẾP LỰA CHỌN
3 -1 5 7 -4
-4 -1 5 7 3
-4 -1 5 7 3
-4 -1 5 7 3
Lần 1
Lần 2
9/77
5.2.1 THUẬT TOÁN SẮP XẾP LỰA CHỌN

5.2.1 THUẬT TOÁN SẮP XẾP LỰA CHỌN
12/77

Ý tưởng thuật toán
5.2.2 THUẬT TOÁN SẮP XẾP CHÈN
3
4
7
9
3
4
6
7
9
3
4
6
7
9
13/77

Ý tưởng thuật toán :

Ở lần duyệt thứ i, với 0<i<n đặt phần tử ở vị trí i
vào đúng thứ tự của nó so với i phần tử trước đã
được sắp xếp.

Sau n-1 lượt dãy được sắp xếp
5.2.2 THUẬT TOÁN SẮP XẾP CHÈN
14/77

tg
-1
Lần 1
17/77
5.2.2 THUẬT TOÁN SẮP XẾP CHÈN
-1 3 7 -4 5
-1 3 7 -4 5
tg
7
-1 3 7 5
-1 3 7 -4 5
tg
- 4
-4 -1 3 7 5
Lần 3
Lần 2
18/77
5.2.2 THUẬT TOÁN SẮP XẾP CHÈN
tg
5
-4 -1 3 5 7
-4 -1 3 7 5
-4 -1 3 7
Lần 4
19/77

Ví dụ 2

Cho mảng số nguyên như sau



Cho mảng a 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
5.2.3 THUẬT TOÁN SẮP XẾP NỔI BỌT
a0 a1 a2 a3 a4
3 -1 7 -4 5
23/77
5.2.3 THUẬT TOÁN SẮP XẾP NỔI BỌT
a0 a1 a2 a3 a4
3 -1 7 -4 5
3 -1 7 -4 5
3 -1 -4 7 5
3 -4 -1 7 5
-4 3 -1 7 5
Lần 1
24/77
5.2.3 THUẬT TOÁN SẮP XẾP NỔI BỌT
-4 3 -1 7 5
-1 3 5 7
3 5 7
5 7
-4 -1 3 5 7
Lần 1
Lần 2
Lần 3
Lần 4
25/77

Ví dụ 2: