Lecturer: PhD. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
Cấu trúc dữ liệu và giải thuật
Bài 6. Sắp xếp nhanh -Quick Sorts
Ngo Huu Phuc, Le Quy Don Technical University
1
Bài 6. Quick Sorts
Nội dung:
6.1. Thuật toán QuickSort (6)
6.2. Ví dụ về QuickSort (7)
6.3. Hoạt động của QuickSort (6)
6.4. Hiệu quả của QuickSort (6)
Tham khảo:
1. Intro to Algorithms Chapter 8 QuickSort.htm
2. Lecture 5 –quicksort.htm
3. Quick Sort.htm
4. Bài giảng của TS Nguyễn Nam Hồng
Ngo Huu Phuc, Le Quy Don Technical University
2
6.1. Thuật toán QuickSort (1/6)
Giải thuật Quick-sort là
phương pháp sắp xếp dựa
trên chiến lược chia để trị.
Giải thuật gồm các bước:
Phép chia: chọn ngẫu nhiên
một phần tử xlàm khóa,
chia tập dữ liệu Sban đầu
thành 3 phần:
L chứa các phần tử nhỏ hơn x
E chứa các phần tử bằng x
G chứa các phần tử lớn hơn x
Bước lặp: sắp xếp 2 tập L
và G
Hiệu chỉnh lại các tập L, E
và G
Ngo Huu Phuc, Le Quy Don Technical University
3
x
x
LGE
x
6.1. Thuật toán QuickSort (2/6)
Các bước cơ bản của thuật toán:
Chia tập dữ liệu ban đầu thành 2 tập con:
sao cho, tất cả các phần tử bên trái nhỏ hơn tất
cả các phần tử bên phải.
Sắp xếp 2 tập con một cách độc lập và nối chúng
lại với nhau:
như vậy, ta được dãy đã sắp xếp.
Ngo Huu Phuc, Le Quy Don Technical University
4
6.1. Thuật toán QuickSort (3/6)
Với mỗi tập con trên, mỗi tập chia thành 02 tập
con nếu có thể
như vậy, ta có tối đa 04 tập con.
tập các phần tử nhỏ nhất ở bên trái cùng, tập
các phần tử lớn nhất ở bên phải cùng.
Lặp lại quá trình trên cho đến khi tập chỉ có 1
phần tử
nối tất cả các tập với nhau ta được dãy đã sắp
xếp.
Ngo Huu Phuc, Le Quy Don Technical University
5