Bài giảng Cấu trúc dữ liệu - Chương 3: Các thuật toán sắp xếp - Thiều Quang Trung

CHƯƠNG 3 
CÁC THUẬT TOÁN SẮP XẾP 
GV Th.S. Thiều Quang Trung 
Bộ môn Khoa học cơ bản 
Trường Cao đẳng Kinh tế Đối ngoại 
2 
• Chọn trực tiếp - Selection Sort 1 
• Chèn trực tiếp - Insertion Sort 2 
• Đổi chỗ trực tiếp - Interchange Sort 3 
• Nổi bọt - Bubble Sort 4 
• Sắp xếp dựa trên phân hoạch - Quick Sort 5 
• Trộn trực tiếp - Merge Sort 6 
Nội dung 
GV. Thiều Quang Trung 
3 
Các khái niệm 
• Sắp xếp là gì ? 
– Sắp xếp là quá trình xử lý một danh sách các phần 
tử (hoặc các mẫu tin) để đặt chúng theo một thứ 
tự thỏa mãn một tiêu chuẩn nào đó. 
• Khái niệm nghịch thế: 
– Xét một mảng các số a0, a1,  ,aN 
– Giả sử xét mảng có thứ tự tăng dần, nếu có i < j và 
ai > aj, thì ta gọi đó là nghịch thế. 
GV. Thiều Quang Trung 
4 
Các khái niệm 
• Để sắp xếp một mảng => tìm cách giảm số các 
nghịch thế trong mảng này bằng cách hoán vị 
các cặp phần tử. 
• Cho trước một dãy số a1, a2,  aN được lưu trữ 
trong cấu trúc dữ liệu mảng. 
 Ví dụ: int a[N]; 
 => Chọn lựa một số phương pháp để sắp xếp. 
GV. Thiều Quang Trung 
5 
• Ý tưởng: thực hiện N-1 lần việc đưa phần tử nhỏ 
nhất trong dãy hiện hành về vị trí đứng ở đầu dãy 
• Nhận xét: nếu mảng có thứ tự thì phần tử ai luôn 
là min (ai,ai+1,..,an-1) => Ý tưởng của thuật toán 
chọn trực tiếp: 
– Chọn phần tử nhỏ nhất trong N phần tử ban đầu, đưa 
phần tử này về vị trí đứng đầu dãy hiện hành; 
– Sau đó không quan tâm phần tử này nữa, xem dãy hiện 
hành chỉ còn N-1 phần tử của dãy 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  cho đến khi 
dãy hiện hành chỉ còn một phần tử. 
Chọn trực tiếp - Selection Sort 
GV. Thiều Quang Trung 
6 
• Giải thuật : 
B1: i = 0; 
B2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành 
từ a[i] đến a[n] 
B3: if (min ≠ i) : hoán vị a[min] và a[i] 
B4: if (i≤ (n-1): 
 B4.1: i++ 
 B4.2: Lặp lại B2 
Ngược lại : dừng // vì n-1 phần tử đã nằm đúng vị trí 
Chọn trực tiếp (tt) 
GV. Thiều Quang Trung 
7 
1. Chọn trực tiếp (tt) 
 GV. Thiều Quang Trung 
8 
1. Chọn trực tiếp (tt) 
 GV. Thiều Quang Trung 
9 
void SelectionSort(int a[],int n ) 
{ 
 int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hành 
 for (int i=0; i<n-1 ; i++) 
 { 
 min = i; 
 for(int j = i+1; j < n ; j++) 
 if (a[j] < a[min]) 
 min = j; // ghi nhận vị trí phần tử nhỏ nhất 
 if (min != i) 
 Swap(a[min], a[i]); 
 } 
} 
Cài đặt giải thuật Chọn trực tiếp 
GV. Thiều Quang Trung 
10 
• Ở lượt thứ I, cần (n-i) lần so sánh để tìm phần tử nhỏ nhất 
hiện hành. Số lượng phép so sánh không phụ thuộc vào tình 
trạng của dãy ban đầu. 
• Trong mọi trường hợp số lần so sánh là 
• Số lần hoán vị (một hoán vị bằng 3 phép gán) phụ thuộc vào 
tình trạng ban đầu của dãy số. 
Đánh giá giải thuật Chọn trực tiếp 
Xấu nhất 
0 Tốt nhất 
Số phép gán Số lần so sánh Trường hợp 
2
)1( nn
2
)1( nn
2
)1(3 nn
2
1)n(n
i)(n
1n
1i
 
GV. Thiều Quang Trung 
11 
Ý tưởng: 
• Giả sử dãy {a0,a1,an-1} có k phần tử đầu tiên 
{a0,a1,ak-1} đã có thứ tự. 
• Chèn phần tử ak vào k phần tử đầu tiên đã có 
thứ tự bằng cách tìm vị trí đúng của phần tử k 
theo giải thuật tìm tuần tự (Sequential Search) 
 có dãy mới {a0,a1,,ak-1,ak} có thứ tự. 
• Vị trí cần chèn ak chính là giữa 2 phần tử ai-1 và ai 
sao cho ai-1 ≤ ak+1 ≤ ai 
Chèn trực tiếp - Insertion Sort 
GV. Thiều Quang Trung 
12 
Thuật toán: 
B1: k = 1 //Giả sử đoạn a[0] đã sắp xếp 
B2: x = ak Tìm vị trí pos thích hợp trong đoạn a0 đến ak-1 để 
chèn ak vào 
B3: Dời chỗ các phần tử từ apos đến ak-1 sang phải 1 vị trí để 
dành chỗ cho ak 
 B4: apos = x; // đoạn a0  ak đã được sắp 
 B5: k = k+1 
 Nếu i<= n: lặp lại B2 
 Ngược lại : dừng 
Chèn trực tiếp - Insertion Sort (tt) 
GV. Thiều Quang Trung 
13 
Ví dụ mô phỏng chèn trực tiếp 
• Cho dãy số a : N = 8 ; 
 12 2 8 5 1 6 4 15 
 GV. Thiều Quang Trung 
14 
Ví dụ mô phỏng chèn trực tiếp (tt) 
 GV. Thiều Quang Trung 
15 
void InsertionSort (int a [ ], int n) 
 { int k=0, i; 
 while (a[k]≤a[k+1] && k<n) k++; 
 while (k<n) 
 { int x=a[k+1]; i=k; 
 while (x0) 
 { a[i+1] = a[i]; 
 i--; 
 } 
 a[i+1]=x; 
 k++; 
 } return; 
 } 
Cài đặt giải thuật Chèn trực tiếp 
GV. Thiều Quang Trung 
16 
• Trường hợp tốt nhất: khi mảng a ban đầu đã 
có thứ tự tăng 
– Số phép gán: Gmin = 2*(n-1) 
– Số phép so sánh: Smin = 1+2++ (n-1) = n*(n-1)/2 
• Trường hợp xấu nhất: khi mảng a ban đầu 
luôn có phần tử nhỏ nhất trong n-k phần tử 
còn lại 
– Số phép gán: Gmax = 2*(n-1) + n*(n-1)/2 
– Số phép so sánh: Smax = n-1 
• Độ phức tạp của thuật toán: O(n2) 
Đánh giá giải thuật Chèn trực tiếp 
GV. Thiều Quang Trung 
17 
Ý tưởng: 
• Phương pháp chèn nhị phân tương tự 
phương pháp chèn trực tiếp. 
• Tuy nhiên, khi thực hiện tìm kiếm vị trí i cho 
phần tử ai để chèn vào đoạn {a0,a1,,ai-1} có 
thể dùng phương pháp tìm kiếm nhị phân 
(Binary Search) thay cho tìm kiếm tuần tự 
(Sequential Search) 
Chèn nhị phân – Binary Insertion Sort 
GV. Thiều Quang Trung 
18 
void BinaryInsertionSort(int a[], int n ) 
{ int l,r,m,i; 
 int x;//lưu trữ giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử. 
 for(int i=0 ; i<n ; i++) 
 { x = a[i]; l = 0; r = i-1; 
 while(l<=r) // tìm vị trí chèn x 
 { m = (l+r)/2; // tìm vị trí thích hợp m 
 if(x < a[m]) r = m-1; 
 else l = m+1; 
 } 
 for(int j = i ; j >l ; j--) 
 a[j] = a[j-1]; // dời chỗ các phần tử sẽ đứng sau x 
 a[l] = x; // chèn x vào dãy 
 } 
} 
Cài đặt Binary Insertion Sort 
GV. Thiều Quang Trung 
19 
• Phương pháp chèn nhị phân chỉ cải tiến cách 
tìm kiếm vị trí thích hợp của phần tử a[i], 
làm giảm số lần so sánh nhưng lại không làm 
thay đổi số lần di chuyển. 
• Vì vậy việc cải tiến này không đáng kể lắm 
Độ phức tạp của thuật toán vẫn là O(n2) 
Đánh giá Binary Insertion Sort 
GV. Thiều Quang Trung 
20 
Đổi chỗ trực tiếp - Interchange Sort 
• Ý tưởng : 
 Ý tưởng chính của giải thuật là xuất phát đầu dãy, tìm 
tất cả nghịch thế chứa phần tử này, triệt tiêu chúng 
bằng cách đổi chỗ phần tử này với phần tử tương 
ứng trong cặp nghịch thế. Lặp lại xử lý trên với các 
phần tử tiếp theo trong dãy. 
 GV. Thiều Quang Trung 
21 
3. Đổi chỗ trực tiếp (tt) 
• Giải thuật : 
 B1 : i = 1 ; // Bắt đầu từ đầu dãy. 
 B2 : j = i + 1 ; // Tìm các phần tử a[j] i 
 B3 : Trong khi j n thực hiện 
 Nếu a[j] < a[i] : Hoán vị a[i] và a[j] ; 
 j = j +1; 
 B4 : i = i+1; 
 Nếu i < n : lặp lại Bước 2. 
 Ngược lại : Dừng. 
 GV. Thiều Quang Trung 
22 
Ví dụ mô phỏng Đổi chỗ trực tiếp 
• Cho dãy số a : N = 8 ; 
12 2 8 5 1 6 4 15 
 GV. Thiều Quang Trung 
23 
Ví dụ mô phỏng Đổi chỗ trực tiếp (tt) 
GV. Thiều Quang Trung 
24 
Ví dụ mô phỏng Đổi chỗ trực tiếp (tt) 
GV. Thiều Quang Trung 
25 
Ví dụ mô phỏng Đổi chỗ trực tiếp (tt) 
GV. Thiều Quang Trung 
26 
Ví dụ mô phỏng Đổi chỗ trực tiếp (tt) 
GV. Thiều Quang Trung 
27 
Ví dụ mô phỏng Đổi chỗ trực tiếp (tt) 
GV. Thiều Quang Trung 
28 
Cài đặt thuật toán Đổi chỗ trực tiếp 
void InterchangeSort ( int a[] , int N ) 
 for (int i = 0 ; i < N - 1 ; i ++ ) 
 for (int j = i +1 ; j < N ; j ++) 
 if (a[j] < a[i]) // Nếu có sự sai vị trí thì đổi chỗ 
 swap (a[i],a[j]); 
  
 GV. Thiều Quang Trung 
29 
Đánh giá giải thuật Đổi chỗ trực tiếp 
Số lượng các phép so sánh không phụ thuộc vào tình trạng 
của dãy số ban đầu, nhưng số lượng các phép hoán vị phụ 
thuộc vào kết quả so sánh 
2
)1( nn
2
)1( nn
2
)1( nn
Xấu nhất 
0 Tốt nhất 
Số lần hoán vị Số lần so sánh Trường hợp 
 GV. Thiều Quang Trung 
30 
Giải thuật Nổi bọt (Bubble Sort) 
Ý tưởng : 
• Xuất phát từ cuối (đầu) dãy, đổi chỗ các cặp phần tử 
kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần 
tử đó về vị trí đứng đầu (cuối) dãy hiện hành, sau đó 
sẽ không xét đến nó ở bước tiếp theo, 
• Ở 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. 
 GV. Thiều Quang Trung 
31 
Giải thuật : 
 B1: i = 0 ; // Lần xử lý đầu tiên 
 B2: j = N-1 ; // Duyệt từ cuối dãy ngược về vị trí i 
 Trong khi (j > i) thực hiện 
 if a[j] < a[j-1] : swap (a[j], a[j-1]); 
 j = j - 1; 
 B3: i = i + 1; // Lần xử lý kế tiếp 
 Nếu i = n: Hết dãy. Dừng 
 Ngược lại : Lặp lại Bước 2. 
Giải thuật Nổi bọt (Bubble Sort) 
GV. Thiều Quang Trung 
32 
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]) 
 Swap(a[j], a[j-1]); 
} 
Cài đặt giải thuật Nổi bọt 
GV. Thiều Quang Trung 
33 
Ví dụ mô phỏng giải thuật Nổi bọt 
• Cho dãy số a : N = 8 ; 
12 2 8 5 1 6 4 15 
 GV. Thiều Quang Trung 
34 
4. Nổi bọt (tt) 
 GV. Thiều Quang Trung 
35 
4. Nổi bọt (tt) 
 GV. Thiều Quang Trung 
36 
4. Nổi bọt (tt) 
 GV. Thiều Quang Trung 
37 
4. Nổi bọt (tt) 
 GV. Thiều Quang Trung 
38 
4. Nổi bọt (tt) 
 GV. Thiều Quang Trung 
39 
Đánh giá thuật toán Nổi bọt 
• Số lượng các phép so sánh xảy ra không phụ thuộc 
vào tình trạng của dãy số ban đầu, 
• Số lượng phép hoán vị thực hiện tùy thuộc vào kết 
quả so sánh 
Xấu nhất 
0 Tốt nhất 
Số lần hoán vị Số lần so sánh Trường hợp 
2
)1( nn
2
)1( nn
2
)1( nn
 GV. Thiều Quang Trung 
40 
Sắp xếp dựa trên phân hoạch - Quick Sort 
• Ý tưởng : 
 Để sắp xếp dãy a1, a2,  , an giải thuật QuickSort dựa trên 
việc phân hoạch dãy ban đầu thành hai phần : 
 Dãy con 1 : gồm các phần tử a1 .. ai có giá trị nhỏ hơn x. 
 Dãy con 2 : gồm các phần tử ai .. an 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. 
 x x x 
GV. Thiều Quang Trung 
41 
Sắp xếp dựa trên phân hoạch (tt) 
Giải thuật sắp xếp : Cho dãy aL, aL + 1, , aR : 
B1 : 
 Phân hoạch dãy aL  aR thành các dãy con : 
– Dãy con 1 : aL ... aj x 
– Dãy con 2 : aj + 1 ... ai -1 = x 
– Dãy con 3 : ai ... aR x 
B2 : 
 Nếu (L < j) Phân hoạch dãy aL ... aj 
 Nếu (i < R) Phân hoạch dãy ai .. aR 
 GV. Thiều Quang Trung 
42 
Sắp xếp dựa trên phân hoạch (tt) 
Giải thuật phân hoạch: 
(Phân hoạch dãy aL, aL + 1, , aR thành 2 dãy con) 
B1 : 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 ; 
B2 : Phát hiện và hiệu chỉnh cặp phần tử a[i], a[j] nằm sai chỗ 
 B2.1 : Trong khi (a[i] < x) i++; 
 B2.2: Trong khi (a[j] > x) j--; 
 B2.3 : Nếu (i < j) Hoán vị a[i] và a[j]; 
B3 : 
 Nếu i < j : lặp lại bước 2. 
 Ngược lại : Dừng phân hoạch. 
 GV. Thiều Quang Trung 
43 
void QuickSort(int a[], int l, int r) 
{ int i, j, x; 
 x = a[(l+r)/2]; // chọn phần tử giữa làm giá trị mốc 
 i = l; j = r; 
 while(i < j) 
 { while(a[i] < x) i++; 
 while(a[j] > x) j--; 
 if(i <= j) 
 { Swap(a[i], a[j]); 
 i++ ; j--; 
 } 
 } 
 if (l<j) QuickSort(a, l, j); 
 if (i<r) QuickSort(a, i, r); 
} 
Cài đặt giải thuật sắp Quicksort 
GV. Thiều Quang Trung 
44 
• Hiệu quả phụ thuộc vào việc chọn giá trị mốc: 
• Trường hợp tốt nhất: mỗi lần phân hoạch đều chọn phần tử 
median làm mốc dãy được chia thành 2 phần bằng nhau 
log2(n) lần phân hoạch thì sắp xếp xong. 
• Nếu mỗi lần phân hoạch chọn phần tử có giá trị cực đại (hay 
cực tiểu) là mốc dãy sẽ bị phân chia thành 2 phần không 
đều: một phần chỉ có 1 phần tử, phần còn lại gồm (n-1) phần tử 
 n lần phân hoạch mới sắp xếp xong. 
 Trường hợp Độ phức tạp 
Tốt nhất n*log(n) 
Trung bình n*log(n) 
Xấu nhất n2 
Đánh giá giải thuật Quicksort 
GV. Thiều Quang Trung 
45 
5. Sắp xếp dựa trên phân hoạch (tt) 
• Ví dụ : Cho dãy số a : N = 8 ; 
 12 2 8 5 1 6 4 15 
 GV. Thiều Quang Trung 
46 
5. Sắp xếp dựa trên phân hoạch (tt) 
12 2 8 5 1 6 4 15
Phaân hoaïch ñoaïn l = 1, r = 8 : x = a[4] = 5
l = 1 r = 8
4 2 1 5 8 6 12 15
4 2 1 5 8 6 12 15
Phaân hoaïch ñoaïn l = 1, r = 3 : x = a[2] = 2
l = 1 r = 3
1 2 4 5 8 6 12 15
 GV. Thiều Quang Trung 
47 
5. Sắp xếp dựa trên phân hoạch (tt) 
1 2 4 5 8 6 12 15
Phaân hoaïch ñoaïn l = 5, r = 8 : x = a[6] = 6
l = 5 r = 8
1 2 4 5 6 8 12 15
Phaân hoaïch ñoaïn l = 7, r = 8 : x = a[7] = 12
1 2 4 5 6 8 12 15
l = 7 r = 8
1 2 4 5 6 8 12 15
Döøng
 GV. Thiều Quang Trung 
48 
Giải thuật Trộn trực tiếp - Merge Sort 
• Ý tưởng : 
 Để sắp xếp dãy a1, a2, ... , an, giải thuật trộn trực tiếp 
dựa trên nhận xét sau : 
– Mỗi dãy a1, a2, ... , an bất kỳ đều có thể coi như là 
một tập hợp các dãy con liên tiếp mà mỗi dãy con 
đều đã có thứ tự. Ví dụ dãy 12, 2, 8, 5, 1, 6, 4, 15 
có thể coi như gồm 5 dãy con không giảm (12); (2, 
8); (5); (1, 6); (4, 15). 
– Dãy đã có thứ tự coi như có 1 dãy con. 
 GV. Thiều Quang Trung 
49 
 Cách tiếp cận để sắp xếp dãy là tìm cách làm giảm số dãy 
con không giảm của nó => Phân hoạch dãy ban đầu thành 
các dãy con. 
 Sau khi phân hoạch xong, dãy ban đầu sẽ được tách ra 
thành 2 dãy phụ theo nguyên tắc phân phối đều luân 
phiên. 
 Trộn từng cặp dãy con của 2 dãy phụ thành một dãy con 
của dãy ban đầu, ta sẽ nhận lại dãy ban đầu nhưng với số 
lượng dãy con ít nhất giảm đi một nửa. 
 Lặp lại quá trình trên sau một số bước, ta sẽ nhận được 
một dãy gồm 1 dãy con không giảm. Nghĩa là dãy ban đầu 
đã được sắp xếp. 
Giải thuật Trộn trực tiếp - Merge Sort (tt) 
GV. Thiều Quang Trung 
50 
 Giải thuật trộn là phương pháp đơn giản nhất. 
Việc phân hoạch thành các dãy con đơn giản là 
tách dãy gồm n phần tử thành n dãy con. Cứ 
mỗi lần tách rồi trộn, chiều dài của các dãy con 
sẽ được nhân đôi. 
Giải thuật Trộn trực tiếp - Merge Sort (tt) 
GV. Thiều Quang Trung 
51 
Giải thuật : 
B1 : 
 k = 1; // k là chiều dài của dãy con trong bước hiện hành 
B2 : 
 Tách dãy a1, a2,  , an thành 2 dãy b, c theo nguyên tắc luân 
phiên từng nhóm k phần tử : 
 b = a1,  , ak, a2k +1,  a3k,  
 c = ak + 1,  , a2k, a3k +1,  a4k,  
B3 : 
 Trộn từng cặp dãy con gồm k phần tử của 2 dãy b, c vào a. 
B4 : 
 k = k * 2; 
 Nếu k < n thì trở lại bước 2. 
 Ngược lại : Dừng. 
Giải thuật Trộn trực tiếp - Merge Sort (tt) 
GV. Thiều Quang Trung 
52 
• Cho dãy số a : N = 8 ; 
 12 2 8 5 1 6 4 15 
Ví dụ mô phỏng giải thuật Merge Sort 
GV. Thiều Quang Trung 
53 
Ví dụ mô phỏng giải thuật Merge Sort (tt) 
GV. Thiều Quang Trung 
54 
void MergeSort (int a[], int N) 
 int pa, pb, pc; // các chỉ số trên các mảng a,b,c 
 int i, k = 1; // độ dài của dãy con khi phân hoạch 
 int b [N], c[N]; // hai mảng phụ 
 do // tách a thành b và c 
 pa = pb = pc = 0; 
 while (pa < N) 
 for (i = 0 ; (pa < N) && (i < k) ; i++) b [pb++] = a [pa++]; 
 for (i = 0 ; (pa < N) && (i < k) ; i ++) c [pc++] = a [pa++] 
  
 Merge (a, b, c, pb, pc, k); // trộn b, c lại thành a 
 k * = 2; 
  while (k < N); 
 
Cài đặt giải thuật Merge Sort 
GV. Thiều Quang Trung 
55 
void Merge ( int a [], int b [], int c [], int nb, int nc, int k) 
 int pa, pb, pc, ib, ic, kb, kc; 
 pa = pb = pc = 0 ; ib = ic = 0 ; 
 while ((nb > 0) && (nc > 0)) 
 kb = min (k, nb) ; kc = min (k, nc) ; 
 if (b [pb + ib] <= c [pc + ic]) 
 a [pa++] = b [pb + ib]; ib ++; 
 if (ib = = kb) 
 for (; ic < kc ; ic ++ ) 
 a [pa ++] = c [pc + ic] ; 
 pb += kb ; pc += kc ; ib = ic = 0 ; 
 nb = kb ; nc = kc; 
  
Cài đặt giải thuật Merge Sort (tt) 
GV. Thiều Quang Trung 
56 
  else 
 a [pa ++] = c [pc + ic] ; ic ++; 
 if (ic = = kc) 
 for (; ib < kb ; ib ++) 
 a [pa ++] = b [pb + ib] ; 
 pb += kb ; pc += kc ; ib = ic = 0; 
 nb = kb ; nc = kc ; 
  
  
  
 
Cài đặt giải thuật Merge Sort (tt) 
GV. Thiều Quang Trung 
57 
• Số lần lặp của bước 2 và bước 3 là log2n do sau mỗi 
lần lặp giá trị của k tăng lên gấp đôi. 
• Chi phí thực hiện của giải thuật trộn là nlog2n. 
• Do không sử dụng thông tin nào về đặc tính của dãy 
cần sắp xếp, nên trong mọi trường hợp của thuật 
toán chi phí là không đổi. Đây chính là một trong 
những nhược điểm lớn của thuật toán. 
Đánh giá giải thuật Merge Sort 
GV. Thiều Quang Trung 
58 
So sánh các phương pháp sắp xếp 
STT Phương pháp Độ phức tạp 
1 Chèn trực tiếp – InsertionSort O(n2) 
2 Chèn nhị phân – Binary InsertionSort O(n2) 
3 Chọn trực tiếp - SelectionSort O(n2) 
4 Nổi bọt – BubbleSort O(n2) 
5 QuickSort O(nlogn) 
6 MergeSort O(nlogn) 
GV. Thiều Quang Trung 
59 
Bài tập thực hành 
• Bài 1: Cho dãy số dùng mảng lưu trữ. Viết chương trình 
sắp xếp bằng phương pháp chọn trực tiếp (Selection 
Sort). In ra dãy số trước khi sắp và sau khi sắp. 
• Bài 2: Cho dãy số dùng mảng lưu trữ. Viết chương trình 
sắp xếp bằng phương pháp chèn trực tiếp (Insertion 
Sort). In ra dãy số trước khi sắp và sau khi sắp. 
• Bài 3: Cho dãy số dùng mảng lưu trữ. Viết chương trình 
sắp xếp bằng phương pháp đổi chổ trực tiếp 
(Interchange Sort). In ra dãy số trước khi sắp và sau khi 
sắp. 
 GV. Thiều Quang Trung 
60 
Bài tập thực hành (tt) 
• Bài 4: Cho dãy số dùng mảng lưu trữ. Viết chương 
trình sắp xếp bằng phương pháp nổi bọt (Bubble 
Sort). In ra dãy số trước khi sắp và sau khi sắp. 
• Bài 5: Cho dãy số dùng mảng lưu trữ. Viết chương 
trình sắp xếp bằng phương pháp theo nguyên tắc trộn 
(Merge Sort). In ra dãy số trước khi sắp và sau khi sắp. 
• Bài 6: Cho dãy số dùng mảng lưu trữ. Viết chương 
trình sắp xếp bằng phương pháp hiệu quả cao (Quick 
Sort). In ra dãy số trước khi sắp và sau khi sắp. 
 GV. Thiều Quang Trung 
GV. Thiều Quang Trung