Bài giảng Câu trúc dữ liệu và giải thuật - Chương 2: Tìm kiến và sắp xếp nội

Thuật Tốn Sắp Xếp
1. Đổi chỗ trực tiếp – Interchange Sort
2. Chọn trực tiếp – Selection Sort
3. Nổi bọt – Bubble Sort
4. Shaker Sort
5. Chèn trực tiếp – Insertion Sort
6. Chèn nhị phân – Binary Insertion Sort
7. Shell Sort
8. Heap Sort
9. Quick Sort
10. Merge Sort
11. Radix Sort
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
20
Các Thuật Tốn Sắp Xếp
1. Đổi chỗ trực tiếp – Interchange Sort
2. Chọn trực tiếp – Selection Sort
3. Nổi bọt – Bubble Sort
4. Shaker Sort
5. Chèn trực tiếp – Insertion Sort
6. Chèn nhị phân – Binary Insertion Sort
7. Shell Sort
8. Heap Sort
9. Quick Sort
10. Merge Sort
11. Radix Sort
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
21
Đổi Chỗ Trực Tiếp – Interchange Sort
 Ý tưởng: Xuất phát từ đầu dãy, tìm tất các 
các nghịch thế chứa phần tử này, triệt tiêu 
chúng bằng cách đổi chỗ 2 phần tử trong cặp 
nghịch thế. Lặp lại xử lý trên với phần tử kế 
trong dãy.
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
22
Các Bước Tiến Hành
 Bước 1: i = 0; // bắt đầu từ đầu dãy 
 Bước 2: j = i+1; //tìm các nghịch thế với a[i] 
 Bước 3: 
Trong khi j < N thực hiện 
Nếu a[j]<a[i] //xét cặp a[i], a[j]
Swap(a[i],a[j]); 
j = j+1;
 Bước 4: i = i+1; 
Nếu i < N-1: Lặp lại Bước 2. 
Ngược lại: Dừng. 
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
23
Đổi Chỗ Trực Tiếp – Interchange Sort
 Cho dãy số a: 
12 2 8 5 1 6 4 15 
j=1i=0
i=0 j=4
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
24
Đổi Chỗ Trực Tiếp – Interchange Sort
i=1 j=2
i=1 j=3
i=1 j=4
5C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
25
Đổi Chỗ Trực Tiếp – Interchange Sort
i=2 j=6
i=2 j=4
i=2 j=3
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
26
Đổi Chỗ Trực Tiếp – Interchange Sort
i=3 j=4
i=3 j=5
i=3 j=6
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
27
Đổi Chỗ Trực Tiếp – Interchange Sort
i=5 j=6
i=4 j=6
i=4 j=5
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
28
Đổi Chỗ Trực Tiếp – Interchange Sort
i=6 j=7
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
29
Cài Đặt Đổi Chỗ Trực Tiếp
void InterchangeSort(int a[], int N )
{
int i, j;
for (i = 0 ; i<N-1 ; i++)
for (j =i+1; j < N ; j++)
if(a[j ]< a[i]) // Thỏa 1 cặp nghịch thế
Swap(a[i], a[j]);
}
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
30
Minh Họa Thuật Tốn
2 8 5 1 6 4 1512
1 2 3 4 5 6 70
1
i
j
6C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
31
Minh Họa Thuật Tốn
12 8 5 2 6 4 151
1 2 3 4 5 6 70
2
0
i
j
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
32
Minh Họa Thuật Tốn
2 12 8 5 6 4 151
1 2 3 4 5 6 70
4
0
i
j
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
33
Minh Họa Thuật Tốn
2 4 12 8 6 5 151
1 2 3 4 5 6 70
5
0
i
j
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
34
Minh Họa Thuật Tốn
2 4 5 6 8 12 151
2 3 4 5 6 7 81
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
35
Độ Phức Tạp Của Thuật Tốn
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
36
Các Thuật Tốn Sắp Xếp
1. Đổi chỗ trực tiếp – Interchange Sort
2. Chọn trực tiếp – Selection Sort
3. Nổi bọt – Bubble Sort
4. Shaker Sort
5. Chèn trực tiếp – Insertion Sort
6. Chèn nhị phân – Binary Insertion Sort
7. Shell Sort
8. Heap Sort
9. Quick Sort
10. Merge Sort
11. Radix Sort
7C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
37
Chọn Trực Tiếp – Selection Sort
 Ý tưởng:
 Chọn phần tử nhỏ nhất trong N phần tử trong 
dãy hiện hành ban đầu.
 Đưa phần tử này về vị trí đầu dãy hiện hành
 Xem dãy hiện hành chỉ cịn N-1 phần tử của 
dãy hiện hành ban đầu
 Bắt đầu từ vị trí thứ 2;
 Lặp lại quá trình trên cho dãy hiện hành... 
đến khi dãy hiện hành chỉ cịn 1 phần tử 
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
38
Các Bước Của Thuật Tốn Chọn Trực Tiếp
 Bước 1: i = 0; 
 Bước 2: Tìm phần tử a[min] nhỏ nhất trong 
dãy hiện hành từ a[i] đến a[N] 
 Bước 3 : Đổi chỗ a[min] và a[i] 
 Bước 4 : Nếu i < N-1 thì 
i = i+1; Lặp lại Bước 2; 
Ngược lại: Dừng. 
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
39
Chọn Trực Tiếp – Selection Sort
 Cho dãy số a: 
12 2 8 5 1 6 4 15 
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
40
Chọn Trực Tiếp – Selection Sort
i=0
i=1
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
41
Chọn Trực Tiếp – Selection Sort
i=2
i=3
i=4
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
42
Chọn Trực Tiếp – Selection Sort
i=6
i=5
8C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
43
Cài Đặt Thuật Tốn Chọn Trực Tiếp
void SelectionSort(int a[],int n )
{
int min,i,j; // chỉ số phần tử nhỏ nhất trong dãy hiện hành 
for (i=0; i<n-1 ; i++) //chỉ số đầu tiên của dãy hiện hành
{
min = i;
for(j = i+1; j <N ; j++)
if (a[j ] < a[min]) 
min = j; // lưu vtrí phần tử hiện nhỏ nhất 
Swap(a[min],a[i]);
}
}
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
44
Minh Họa Thuật Tốn Chọn Trực Tiếp
2 8 5 1 6 4 1512
i
min
1 2 3 4 5 6 70
Vị trí nhỏ nhất(0,7) Swap(a[0], a[4])
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
45
Minh Họa Thuật Tốn Chọn Trực Tiếp
2 8 5 12 6 4 151
i
min
1 2 3 4 5 6 70
Vị trí nhỏ nhất(1,7) Swap(a[1], a[1])
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
46
Minh Họa Thuật Tốn Chọn Trực Tiếp
2 8 5 12 6 4 151
i
min
1 2 3 4 5 6 70
Vị trí nhỏ nhất(2,7) Swap(a[2], a[6])
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
47
Minh Họa Thuật Tốn Chọn Trực Tiếp
2 4 5 12 6 8 151
i
min
1 2 3 4 5 6 70
Vị trí nhỏ nhất(3, 7) Swap(a[3], a[3])
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
48
Minh Họa Thuật Tốn Chọn Trực Tiếp
2 4 5 12 6 8 151
i
min
1 2 3 4 5 6 70
Vị trí nhỏ nhất(4, 7) Swap(a[4], a[5])
9C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
49
Minh Họa Thuật Tốn Chọn Trực Tiếp
2 4 5 6 12 8 151
i
min
1 2 3 4 5 6 70
Vị trí nhỏ nhất(5,7) Swap(a[5], a[6])
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
50
Minh Họa Thuật Tốn Chọn Trực Tiếp
2 4 5 6 8 12 151
i
min
1 2 3 4 5 6 70
Vị trí nhỏ nhất(6, 7)
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
51
Độ Phức Tạo Của Thuật Tốn
 Ðánh giá giải thuật
1
1
( 1)
số lần so sánh ( )
2
n
i
n n
n i



  
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
52
Các Thuật Tốn Sắp Xếp
1. Đổi chỗ trực tiếp – Interchange Sort
2. Chọn trực tiếp – Selection Sort
3. Nổi bọt – Bubble Sort
4. Shaker Sort
5. Chèn trực tiếp – Insertion Sort
6. Chèn nhị phân – Binary Insertion Sort
7. Shell Sort
8. Heap Sort
9. Quick Sort
10. Merge Sort
11. Radix Sort
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
53
Nổi Bọt – Bubble Sort
 Ý tưởng:
 Xuất phát từ cuối dãy, đổi chỗ các cặp phần 
tử kế cận để đưa phần tử nhỏ hơn trong cặp 
phần tử đĩ về vị trí đúng đầu dãy hiện hành, 
sau đĩ sẽ khơng xét đến nĩ ở bước tiếp theo, 
do vậy ở lần xử lý thứ i sẽ cĩ vị trí đầu dãy là 
i. 
 Lặp lại xử lý trên cho đến khi khơng cịn cặp 
phần tử nào để xét.
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
54
Nổi Bọt – Bubble Sort
 Bước 1 : i = 0; // lần xử lý đầu tiên 
 Bước 2 : j = N-1;//Duyệt từ cuối dãy ngược về vị trí i 
Trong khi (j > i) thực hiện: 
Nếu a[j]<a[j-1] 
Doicho(a[j],a[j-1]);
j = j-1;
 Bước 3 : i = i+1; // lần xử lý kế tiếp
Nếu i >=N-1: Hết dãy. Dừng
Ngược lại : Lặp lại Bước 2. 
10
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
55
Nổi Bọt – Bubble Sort
 Cho dãy số a: 
2 12 8 5 1 6 4 15 
i=0 j=6
i=0 i=4
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
56
Nổi Bọt – Bubble Sort
i=0 j=1
i=0 j=2
i=0 j=3
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
57
Nổi Bọt – Bubble Sort
i=1 j=3
i=1 j=4
i=1 j=5
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
58
Nổi Bọt – Bubble Sort
i=2 j=5
i=2 j=4
i=3 j=6 C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
59
Nổi Bọt – Bubble Sort
i=5
i=4 j=6
i=3 j=5
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
60
Cài Đặt Thuật Tốn Nổi Bọt
void BubbleSort(int a[],int n)
{
int i, j;
for (i = 0 ; i<n-1 ; i++)
for (j =n-1; j >i ; j --)
if(a[j]< a[j-1])// nếu sai vị trí thì đổi chỗ
Swap(a[j], a[j-1]);
}
11
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
61
Minh Họa Thuật Tốn
2 8 5 1 6 4 1512
1 2 3 4 5 6 70
i
j
1
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
62
Minh Họa Thuật Tốn
12 2 8 5 4 6 151
1 2 3 4 5 6 70
i
j
2
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
63
Minh Họa Thuật Tốn
2 12 4 8 5 6 151
1 2 3 4 5 6 70
i
j
4
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
64
Minh Họa Thuật Tốn
2 4 12 8 5 6 151
1 2 3 4 5 6 70
i
j
5
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
65
Minh Họa Thuật Tốn
2 4 5 12 8 6 151
1 2 3 4 5 6 70
i
j
6
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
66
Minh Họa Thuật Tốn
2 4 5 6 12 8 151
1 2 3 4 5 6 70
i
j
8
12
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
67
Minh Họa Thuật Tốn
2 4 5 6 8 12 151
2 3 4 5 6 7 81
i
j
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
68
Độ Phức Tạp Của Thuật Tốn Nổi Bọt
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
69
Các Thuật Tốn Sắp Xếp
1. Đổi chỗ trực tiếp – Interchange Sort
2. Chọn trực tiếp – Selection Sort
3. Nổi bọt – Bubble Sort
4. Shaker Sort
5. Chèn trực tiếp – Insertion Sort
6. Chèn nhị phân – Binary Insertion Sort
7. Shell Sort
8. Heap Sort
9. Quick Sort
10. Merge Sort
11. Radix Sort
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
70
Chèn Trực Tiếp – Insertion Sort
 Giả sử cĩ một dãy a0 , a1 ,... ,an-1 trong đĩ i phần 
tử đầu tiên a0 , a1 ,... ,ai-1 đã cĩ thứ tự. 
 Tìm cách chèn phần tử ai vào vị trí thích hợp của 
đoạn đã được sắp để cĩ dãy mới a0 , a1,... ,ai trở 
nên cĩ thứ tự. Vị trí này chính là vị trí giữa hai 
phần tử ak-1 và ak thỏa ak-1 < ai < ak (1≤k≤i). 
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
71
Chèn Trực Tiếp – Insertion Sort
 Bước 1: i = 1; //giả sử cĩ đoạn a[1] đã được sắp
 Bước 2: x = a[i]; Tìm vị trí pos thích hợp trong
đoạn a[1] đến a[i-1] để chèn a[i] vào
 Bước 3: Dời chỗ các phần tử từ a[pos] đến a[i-1] 
sang phải 1 vị trí để dành chổ cho a[i] 
 Bước 4: a[pos] = x; //cĩ đoạn a[1]..a[i] đã được sắp
 Bước 5: i = i+1; 
Nếu i < n : Lặp lại Bước 2 
Ngược lại : Dừng
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
72
Chèn Trực Tiếp – Insertion Sort
 Cho dãy số :
12 2 8 5 1 6 4 15 
i=1
i=2
13
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
73
Chèn Trực Tiếp – Insertion Sort
i=3
i=4
i=5
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
74
Chèn Trực Tiếp – Insertion Sort
i=6
i=7
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
75
Cài Đặt Thuật Tốn Chèn Trực Tiếp
void InsertionSort(int d, int n )
{ int pos, i;
int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử.
for(i=1 ; i<n ; i++) //đoạn a[0] đã sắp
{
x = a[i]; pos = i-1;
// tìm vị trí chèn x
while((pos >= 0)&&(a[pos] > x))
{//kết hợp dời chỗ các phần tử sẽ đứng sau x trong dãy 
mới
a[pos+1] = a[pos];
pos--;
}
a[pos+1] = x]; // chèn x vào dãy
}
}
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
76
Minh Họa Thuật Tốn Insertion Sort
2 8 5 1 6 4 1512
1 2 3 4 5 6 70
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
77
2 8 5 1 6 4 1512
i
x
1 2 3 4 5 6 70
pos
2
Minh Họa Thuật Tốn Insertion Sort
Insert a[1] into (0,0)
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
78
12 8 5 1 6 4 152
i
x
1 2 3 4 5 6 70
pos
Minh Họa Thuật Tốn Insertion Sort
Insert a[2] into (0, 1)
8
14
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
79
8 12 5 1 6 4 152
i
x
1 2 3 4 5 6 70
pos
Minh Họa Thuật Tốn Insertion Sort
Insert a[3] into (0, 2)
5
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
80
5 8 12 1 6 4 152
i
x
1 2 3 4 5 6 70
pos
Minh Họa Thuật Tốn Insertion Sort
Insert a[4] into (0, 3)
1
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
81
2 5 8 12 6 4 151
i
x
1 2 3 4 5 6 70
pos
Minh Họa Thuật Tốn Insertion Sort
Insert a[5] into (0, 4)
6
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
82
2 5 6 8 12 4 151
i
x
1 2 3 4 5 6 70
pos
Minh Họa Thuật Tốn Insertion Sort
Insert a[6] into (0, 5)
4
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
83
2 4 5 6 8 12 151
i
x
1 2 3 4 5 6 70
pos
Minh Họa Thuật Tốn Insertion Sort
Insert a[8] into (0, 6)
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
84
2 4 5 6 8 12 151
pos
1 2 3 4 5 6 70
Minh Họa Thuật Tốn Insertion Sort
15
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
85
Độ Phức Tạp Của Insertion Sort
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
86
Các Thuật Tốn Sắp Xếp
1. Đổi chỗ trực tiếp – Interchange Sort
2. Chọn trực tiếp – Selection Sort
3. Nổi bọt – Bubble Sort
4. Shaker Sort
5. Chèn trực tiếp – Insertion Sort
6. Chèn nhị phân – Binary Insertion Sort
7. Shell Sort
8. Heap Sort
9. Quick Sort
10. Merge Sort
11. Radix Sort
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
87
Quick Sort 
 Ý tưởng:
 Giải thuật QuickSort sắp xếp dãy a1, a2 ..., aN dựa trên
việc phân hoạch dãy ban đầu thành 3 phần :
• Phần 1: Gồm các phần tử cĩ giá trị bé hơn 
x
• Phần 2: Gồm các phần tử cĩ giá trị bằng x
• Phần 3: Gồm các phần tử cĩ giá trị lớn 
hơn x
với x là giá trị của một phần tử tùy ý trong dãy ban 
đầu.
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
88
Quick Sort - Ý Tưởng
 Sau khi thực hiện phân hoạch, dãy ban đầu được phân
thành 3 đoạn:
• 1. ak ≤ x , với k = 1 .. j
• 2. ak = x , với k = j+1 .. i-1
• 3. ak  x , với k = i..N
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
89
 Đoạn thứ 2 đã cĩ thứ tự. 
 Nếu các đoạn 1 và 3 chỉ cĩ 1 phần tử : đã cĩ thứ tự
 khi đĩ dãy con ban đầu đã được sắp. 
Quick Sort – Ý Tưởng
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
90
 Đoạn thứ 2 đã cĩ thứ tự. 
 Nếu các đoạn 1 và 3 cĩ nhiều hơn 1 phần tử thì dãy 
ban đầu chỉ cĩ thứ tự khi các đoạn 1, 3 được sắp. 
 Để sắp xếp các đoạn 1 và 3, ta lần lượt tiến hành việc 
phân hoạch từng dãy con theo cùng phương pháp 
phân hoạch dãy ban đầu vừa trình bày 
Quick Sort – Ý Tưởng
16
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
91
Giải Thuật Quick Sort
 Bước 1: Nếu left ≥ right //dãy cĩ ít hơn 2 phần tử
Kết thúc; //dãy đã được sắp xếp
 Bước 2: Phân hoạch dãy aleft  aright thành các đoạn: 
aleft.. aj, aj+1.. ai-1, ai.. aright
Đoạn 1  x 
Đoạn 2: aj+1.. ai-1 = x 
Đoạn 3: ai.. aright  x
 Bước 3: Sắp xếp đoạn 1: aleft.. aj
 Bước 4: Sắp xếp đoạn 3: ai.. aright
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
92
Giải Thuật Quick Sort
 Bước 1 : Chọn tùy ý một phần tử a[k] trong dãy là 
giá trị mốc ( l ≤ k ≤ r): 
x = a[k]; i = l; j = r; 
 Bước 2 : Phát hiện và hiệu chỉnh cặp phần tử 
a[i], a[j] nằm sai chỗ : 
 Bước 2a : Trong khi (a[i]<x) i++; 
 Bước 2b : Trong khi (a[j]>x) j--; 
 Bước 2c : Nếu i< j Đoicho(a[i],a[j]); 
 Bước 3 : Nếu i < j: Lặp lại Bước 2.
Ngược lại: Dừng
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
93
Quick Sort – Ví Dụ
 Cho dãy số a: 
12 2 8 5
1 6 4 15 
Phân hoạch đoạn l =0, r = 7: x = a[3] = 5
12 2 8 5 1 6 4 15
l=0 r=7
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
94
Quick Sort – Ví Dụ
l=0 r=7
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
95
Quick Sort – Ví Dụ
 Phân hoạch đoạn l =0, r = 2:
x = a[2] = 2
l=0 r=2
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
96
Quick Sort – Ví Dụ
 Phân hoạch đoạn l = 4, r = 7:
x = a[5] = 6
l=4 r=7
17
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
97
 Phân hoạch đoạn l = 6, r = 7:
x = a[6] = 6
l=6 r=7
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
98
Quick Sort
void QuickSort(int a[], int left, int right)
{ int i, j, x;
x = a[(left+right)/2];
i = left; j = right;
while(i < j)
{
while(a[i] < x) i++;
while(a[j] > x) j--;
if(i <= j)
{ 
Doicho(a[i],a[j]);
i++ ; j--;
}
}
if(left<j)
QuickSort(a, left, j);
if(i<right)
QuickSort(a, i, right);
}
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
99
Quick Sort – Ví Dụ
2 8 1 6 4 1512
1 2 3 4 5 6 70
left right
STOP 
Not less than X
i j
STOP 
Not greater than X
Phân hoạch dãy
5
X
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
100
Quick Sort – Ví Dụ
2 8 5 1 6 12 154
2 3 4 5 6 7 81
left right
5X
STOP 
Khơng nhỏ hơn X
i j
STOP 
Khơng lớn hơn X
Phân hoạch dãy
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
101
Quick Sort – Ví Dụ
2 1 5 8 6 12 154
2 3 4 5 6 7 81
left right
ij
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
102
6X
Quick Sort – Ví Dụ
2 4 5 8 6 12 151
2 3 4 5 6 7 81
left right
i j
STOP 
Khơng nhỏ hơn X
STOP 
Khơng lớn hơn X
Sắp xếp đoạn 3
Phân hoạch dãy
18
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
103
Quick Sort – Ví Dụ
2 4 5 6 8 12 151
2 3 4 5 6 7 81
left right
ij
Sắp xếp đoạn 3
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
104
Độ Phức Tạp Của Quick Sort
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
105
Sorting Algorithms 
 Demo
 Animation of sorting algorithms
 
 
demo.html
 
 
(heap sort)
 
(quick sort)
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
106
Sorting Algorithms Comparison
Method
Average 
Time
Best Time Worst Time
Auxiliary 
Space
Sort In 
Place
Stability
Simple Sort 
(Selection, 
Insertion, 
Bubble, )
O(n2)
O(n2) /
O(n) /
O(n)
O(n2) O(1) Yes Yes
Quick Sort O(nlogn) O(nlogn) O(n2)
(logn)
(stack size)
Yes No
Heap Sort O(nlogn) O(nlogn) O(nlogn) O(1) Yes No
Merge Sort O(nlogn) O(nlogn) O(nlogn) O(n) No Yes
Radix Sort O((n+r)k) O((n+r)k) O((n+r)k) O(rk) No Yes
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
107
Bài Tập
 Nhập một dãy số nguyên n phần tử.
 Sắp xếp lại dãy sao cho: 
 số nguyên dương đầu ở đầu dãy và 
theo thứ tự giảm.
 số nguyên âm tăng ở cuối dãy và theo 
thứ tự tăng.
 số 0 ở giữa.
 Lưu ý: Khơng dùng đổi chỗ trực tiếp.