ĐẠI HỌC QUỐC GIA TPHCM
TRƯỜNG ĐẠI HỌC
CÔNG NGHỆ THÔNG TIN
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
CHƯƠNG II
TÌM KIẾM VÀ SẮP XẾP
Nguyễn Trọng Chỉnh
1
[email protected]
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
PHƯƠNG PHÁP MERGE SORT
PHƯƠNG PHÁP RADIX SORT (Sinh viên tự đọc)
2
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
* Ý tưởng:(Quick sort - sắp xếp dựa trên phân hoạch)
Giả sử dãy A có n phần tử có thứ tự tăng dần.
- Phần tử chốt (pivot) ak, k = 0,..,n-1 có giá trị khóa
không nhỏ hơn các phần tử của dãy đã có thứ tự
a0,..,ak-1 và có giá trị khóa không lớn hơn các phần tử
của dãy đã có thứ tự ak+1,..an-1.
- Để sắp xếp, chọn một phần tử ak bất kỳ trong A, chia
dãy A thành hai dãy a0,..,ak-1 có giá trị không lớn hơn
ak và dãy ak+1,..,an-1 có giá trị không nhỏ hơn, sắp xếp
hai dãy này theo cách như trên.
3
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
* Giải thuật: Sử dụng giải thuật đệ quy như sau:
Đầu vào: dãy al,al+1,..,ar chưa có thứ tự.
Đầu ra: dãy al, al+1,..,ar có thứ tự tăng dần.
- B1: Nếu l < r thì k (l + r)/2, x ak, i l, j r; ngược lại
qua B6.
- B2: Nếu ai > x, qua B3; ngược lại i i+1, qua B2.
- B3: Nếu aj < x, qua B4; ngược lại j j - 1, qua B3.
- B4: Nếu i < j thì hoán đổi ai và aj.
- B5: Thực hiện Quick Sort cho dãy al, al+1,..,ar=j và al=i, ai+1,..,ar
- B6: Kết thúc.
4
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
* Cài đặt:
void QuickSort(int *a, int l, int r) {
int i, j, x;
if (l >= r) return;
x = a[(l+r)/2]; i = l; j = r;
while(i < j) {
while (a[i] < x) i++; while (a[j] > x) j--;
if (i <= j) {hoandoi(a[i], a[j]); i++; j--; }
}
QuickSort(a, l, j); QuickSort(a, i, r);
}
5
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
l=0
Tìm i
7
x=1
5
8
i=0
l=0
Tìm j
7
7
i=0
4
2
6
5
8
1
4
2
6
8
1
3
j=7
r=7
x=1
5
3
j=7
r=7
x=1
i=0
l=0
Tìm j
1
r=7
4
2
6
j=6
3
6
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
l=0
Tìm j
7
x=1
5
8
i=0
l=0
Tìm j
7
7
i=0
4
2
6
3
j=5
x=1
5
8
1
r=7
4
2
6
3
j=4
i=0
l=0
Tim j
1
r=7
x=1
5
8
1
j=3
r=7
4
2
6
3
7
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
l=0
5
8
i=1
Tìm i
1
x=1
j=2
l=0
1
5
8
1
2
6
7
3
r=7
j=2
l=0
Tìm j
4
x=1
i=1
Tìm j
7
r=7
4
2
6
x=1
5
i = 1, j = 1
8
7
3
r=7
4
2
6
3
8
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
l=0
r=0
chia dãy
con
l=1
1
5
x=1
8
7
r=7
4
2
6
3
i=1
j=0
l=0
r=0
Xếp dãy trái
Xếp dãy phải
Tìm i
1
l=1
5
i=1
x=4
8
7
4
r=7
2
6
3
9
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
l=1
Tìm j
5
x=4
8
7
i=1
l=1
Tìm i
3
4
r=7
2
x=4
8
7
4
2
6
x=4
8
i=2
5
j=6
l=1
3
3
j=7
r=7
i=2
Tìm j
6
7
4
r=7
2
6
j=6
5
10
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
l=1
Tìm j
3
x=4
8
7
4
i=2
3
2
7
4
2
5
r=7
j=4
x=4
l=1
3
6
x=4
i=3
Tìm j
2
j=5
l=1
Tìm i
r=7
4
7
i=3
j=4
8
6
5
r=7
8
6
5
11
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
l=1
Tìm i
2
4
7
i=4
x=2
j=3
r=3
3
2
4
l=1
xếp dãy
trái
l=4
l=1
chia dãy
con
r=3
x=2
r=3
3
2
4
3
i=1
r=7
8
6
5
j=3
12
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
l=1
Tìm j
x=2
r=3
3
2
4
i=1
l=1 x=2
Tìm j
3
2
j=3
r=3
4
i=1 j=2
l=1 l=2 r=3
r=1
chia dãy
con
2
3
j=1
i=2
4
13
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
l=1
xếp dãy
trái
r=1
2
l=2
x=3
Tìm i
3
4
l=2
x=3
xếp dãy
phải
r=3
r=3
3
4
i=2
14
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
l=2
x=3
4
j=3
l=2
x=3
Tìm j
3
i=2
Tìm j
r=3
r=3
3
4
i=2
j=3
15
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
l=2
3
chia dãy
con
j=1
Xếp dãy
phải
r=3
4
i=3
l=3
r=3
4
l=4
Xếp dãy
phải
x=8
7
8
r=7
6
5
16
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
l=4
Tìm i
x=8
7
8
r=7
6
i=4
l=4 x=8
Tìm j
7
8
l=4
Tìm i
8
j=7
r=7
i=5
x=8
7
i=5
5
6
5
j=7
r=7
6
5
j=7
17
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
l=4
Tìm i
x=8
7
5
r=7
6
8
i=6
j=6
l=4
Tìm i
x=8
7
5
r=7
6
8
j=6 i=7
l=4
Tìm j
x=8
7
5
r=7
6
8
j=6 i=7
18
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORTl = 7
l=4
Chia dãy
con
7
r=6
5
6
r=7
8
j=6 i=7
l=4
Xếp dãy
trái
7
l=4
Tìm i
7
i=4
x=5 r=6
5
6
x=5 r=6
5
6
19
GIẢI THUẬT SẮP XẾP
PHƯƠNG PHÁP QUICK SORT
l=4
Tìm i
7
x=5 r=6
5
6
i=4
l=4
Tìm j
7
i=4
l=4
Tìm j
x=5 r=6
5
6
j=6
x=5 r=6
7
5
i=4
j=5
6
20