SKKN Phân tích, vận dụng các thuật toán sắp xếp để giải quyết một số bài toán viết bằng ngôn ngữ lập trình C++

án có độ phức tạp O(nlogn) và O(n) vẫn ổn định khi dữ liệu vào 
lớn. 
Trường hợp 3: Với 5 bộ test mà các phần tử dương, số lượng phần tử 
50000<=N<=100000. 
Đối với trường hợp này tôi chỉ test những giải thuật Sort thuộc top nhanh của 2 
trường hợp trên. 
Độ phức 
tạp 
50000 60000 80000 90000 100000 
Quick O(nlogn) 0.184 0.221 0.295 0.324 0.365 
Couting O(n) 0.190 0.21 0.287 0.322 0.356 
Heap O(nlogn) 0.204 0.259 0.332 0.383 0.451 
Merge O(n) 0.315 0.35 0.422 0.459 0.509 
Phân tích kết quả: Ở trường hợp này, thuật toán Counting Sort vẫn đang 
chứng minh là thuật toán ổn nhất. Tiếp theo đó là Quick Sort, Heap Sort, Merge 
Sort. 
2.3.3.2. Những yếu tố cần quan tâm khi sử dụng thuật toán 
Từ những phân tích trên ta nhận thấy, cùng một mục đích sắp xếp như 
nhau nhưng có nhiều phương pháp giải quyết khác nhau. Nếu chỉ dựa vào thời 
gian tính toán của thuật toán đo được trong một ví dụ cụ thể mà đánh giá giải 
 24
thuật này tốt hơn giải thuật kia về mọi mặt là chưa đủ. Việc lựa chọn một thuật 
toán sắp xếp phù hợp với từng yêu cầu, từng điều kiện cụ thể là kỹ năng của 
người lập trình. 
Vì vậy đối với người lập trình không cần phải học hết tất cả các thuật toán 
Sort, chỉ cần nắm vững tư tưởng của nó, học thuộc vài thuật toán thông dụng 
như Bubble Sort, Intertion Sort, Selection Sort. Sau đó khi học nâng cao hơn, 
với những bài toán với dữ liệu vào lớn thì người lập trình có thể học Quick Sort, 
Merge Sort, Heap Sort. 
Sau đây là một số yếu tố cần quan tâm. 
2.3.3.2.1. Độ phức tạp 
 Đây là yếu tố chính khi đánh giá thuật toán sort. Độ phức tạp của thuật 
toán có thể hiểu là tổng khối lượng công việc mà thuật toán sẽ xử lý. 
 Độ phức tạp của thuật toán chủ yếu được đánh giá bởi 3 thành phần là độ 
lớn dữ liệu (n), số phép so sánh và số phép gán. 
 Một thuật toán có độ phức tạp trung bình là O(n2) thì được đánh giá là 
chưa tốt, thời gian chạy rất lâu. Tuy nhiên những thuật toán này thì đa số lại dễ 
cài đặt và rất thông dụng như: Bubble Sort, Intertion Sort, Selection Sort. 
 Ví dụ những bài toán đơn giản như sắp xếp danh sách 1000 phần tử, sử 
dụng 1 trong những thuật toán trên là quá đủ rồi. Vừa đơn giản vừa dễ cài đặt. 
Người lập trình không cần phải sử dụng các thuật toán trong top chạy nhanh vì 
hầu hết chúng rất phức tạp, cài đặt dễ sai. 
 Thuật toán tốt và chạy nhanh hiện nay thường có độ phức tạp O(nlogn) 
hoặc O(n). 
2.3.3.2.2. Tài nguyên sử dụng 
 Một số thuật toán cần sử dụng các biến tạm để hỗ trợ, cần sử dụng thêm 
RAM, phần cứng khác... chúng đều được xem là tài nguyên sử dụng. 
 Các thuật toán thường có nguyên tắc đánh đổi: Nếu tài nguyên sử dụng 
nhiều thì thuật toán chạy nhanh và ngược lại. 
 Các thuật toán thông dụng như Bubble Sort, Intertion Sort, Selection 
Sort... thường sử dụng tài nguyên cực nhỏ (1,2 hoặc 3 biến tạm). 
2.3.3.2.3. Tính tổng quát 
 Một số thuật toán chỉ chạy được trên số nguyên, mặc dù vẫn thuộc top 
chạy nhanh nhưng không có tính tổng quát. Trong những giải thuật tôi trình bày 
ở trên thì có thuật toán Counting Sort. Rõ ràng thuật toán này chạy nhanh 
thường ở top đầu nhưng chỉ với phần tử dương và không quá lớn. 
 25
2.3.4. Một số bài toán áp dụng 
2.3.4.1. Nguồn  
 Vaxia đã viết được một số lớn trên một cuộn giấy dài và muốn khoe với 
anh trai Petia về thành quả vừa đạt được. Tuy nhiên, khi Vaxia vừa ra khỏi 
phòng để gọi anh trai thì cô em Kachia chạy vào phòng xé rách cuộn giấy thành 
một số mảnh. Kết quả là trên mỗi mảnh có một hoặc vài kí số theo thứ tự đã 
viết. 
 Bây giờ Vaxia không thể nhớ chính xác mình đã viết số gì. Vaxia chỉ nhớ 
rằng đó là một số rất lớn. 
 Để làm hài lòng cậu em trai, Petia quyết định truy tìm số nào là lớn nhất 
mà Vaxia đã có thể viết lên cuộn giấy trước khi bị xé. Bạn hãy giúp Petia làm 
việc này. 
Dữ liệu: Vào từ file văn bản NUMCON.INP: ghi một hoặc nhiều dòng. Mỗi 
dòng ghi một dãy kí tự số. Số dòng không vượt quá 100. Mỗi dòng ghi từ 1 đến 
100 kí tự số. Đảm bảo rằng có ít nhất một dòng mà kí tự số đầu tiên khác 0. 
Kết quả: Ghi ra file NUMCON.OUT - số lớn nhất có thể viết trên cuộn giấy 
trước khi bị xé rách. 
Ví dụ: 
NUMCON.INP NUMCON.OUT 
2 
20 
004 
66 
66220004 
3 3 
Ý tưởng: Bài toán này cần sắp xếp theo tiêu chí sau: Nếu xâu a[i] đứng trước 
xâu a[j] thì a[i]+a[j]>a[j]. 
Bài toán này dữ liệu vào tương đối nhỏ, nên người lập trình chỉ cần sử 
dụng những giải thuật Sort đơn giản, dễ cài đặt như Bubble Sort, Selection Sort, 
Insert Sort, Shell Sort. Trong chương trình tham khảo, tôi sử dụng thuật toán 
quen thuộc Bubble Sort. 
Chú ý phép cộng này chính là phép ghép hai xâu. Kết quả bài toán là ghi 
lần lượt các xâu theo thứ tự đã sắp xếp. 
Cài đặt chương trình: 
#include 
 26
#include 
#include 
#include 
using namespace std; 
string a[10001]; 
int n; 
string x,y,tg; 
int main() 
{ 
 clock_t begin=clock(); 
 ifstream fi("NUMCON.inp"); 
 ofstream fo("NUMCON.out"); 
 int i=0; 
 while (!fi.eof()) 
 { 
 i++; 
 fi>>a[i]; 
 } 
 n=i;int j; 
 for (int i=0;i<=n-1;i++) 
 for (int j=i+1;j<=n;j++) 
 if (a[i]+a[j]<a[j]+a[i]) 
 { 
 tg=a[j]; 
 a[j]=a[i]; 
 a[i]=tg; 
 } 
 //in ket qua 
 for (int i=0;i<=n-1;i++) 
 fo<<a[i]; 
 fo<<"\n"; 
 27
 clock_t end=clock(); 
 fo<<"time run:"<<(float) (end-begin)/CLOCKS_PER_SEC<<" s"; 
 fi.close();fo.close(); 
 return 0; 
} 
2.3.4.2. QUÀ TẶNG 
 Nhân ngày sinh nhật, hai anh em sinh đôi Tèo và Tý nhận được N món 
quà, N là số chẵn. Mỗi người gán cho mỗi món quà một giá trị ưa thích- là một 
số nguyên dương nhỏ hơn hoặc bằng 100. Giá trị này thể hiện mức độ hạnh phúc 
họ có được nếu có được món quà đó. Sau đó, 2 anh em quyết định chia quà, hai 
người có số lượng quà bằng nhau và bằng N/2. 
Yêu cầu: Hãy xác định cách chia quà sao cho tổng mức độ hạnh phúc của hai 
anh em là lớn nhất. 
Dữ liệu: Vào từ file văn bản GIFT.INP trong đó: 
 + Dòng đầu tiên là số nguyên dương N <500000 
 + N dòng tiếp theo, mỗi dòng ghi 2 số nguyên dương a và b tương ứng là 
giá trị ưa thích của Tèo và Tý với từng món quà. 
Kết quả: Ghi ra file GIFT.OUT duy nhất là số có tổng mức độ hạnh phúc lớn 
nhất. 
Ví dụ: 
GIFT.INP GIFT.OUT 
4 
1 2 
2 3 
3 5 
2 1 
11 
Ý tưởng: 
 + Đọc 2 mảng tương ứng là a[i] và b[i] 
 + Tạo mảng C[i]=a[i]-b[i] 
 + Sắp xếp lại a[i] và b[i] theo chiều tăng dần của c[i] 
Bài toán này dữ liệu vào tương đối lớn, nên để đảm bảo thời gian thực 
hiện, người lập trình nên sử dụng những thuật toán tốt hơn như Quick Sort, 
Counting Sort, Heap Sort, Merge Sort. Trong chương trình tham khảo, tôi sử 
 28
dụng thuật toán Quick Sort. 
 + Kết quả là tổng N/2 số đầu của b[i] và tổng N/2 số cuối của a[i]. Lấy 
như vậy mới được tổng mức độ hạnh phúc lớn nhất. 
Cài đặt chương trình: 
#include 
#include 
#include 
using namespace std; 
long a[50001],b[50001],c[50001]; 
long n,i; 
int s; 
void swap(long &a,long &b) 
{ 
 int tg=a; 
 a=b; 
 b=tg; 
} 
void QuickSort(long left, long right) 
{ 
 long i=left; long j=right; 
 long pivot=a[(left+right)/2]; 
 while (i<=j) 
 { 
 while (a[i]<pivot) 
 i++; 
 while (a[j]>pivot) 
 j--; 
 if (i<=j) 
 { 
 swap(a[i],a[j]); 
 swap(b[i],b[j]); 
 29
 swap(c[i],c[j]); 
 i++; 
 j--; 
 } 
 } 
 if (left<j) 
 QuickSort(left,j); 
 if (i<right) 
 QuickSort(i,right); 
} 
int main() 
{ 
 clock_t begin=clock(); 
 ifstream fi("GIFT.inp"); 
 ofstream fo("GIFT.out"); 
 fi>>n; 
 for (long i=0;i<=n-1;i++) 
 { 
 fi>>a[i]>>b[i]; 
 c[i]=a[i]-b[i]; 
 } 
 QuickSort(0,n-1); 
 s=0; 
 for (long i=0;i<=n/2;i++) 
 s+=b[i]; 
 for (long i=n/2;i<=n-1;i++) 
 s+=a[i]; 
 fo<<s; 
 fo<<"\n"; 
 clock_t end=clock(); 
 fo<<"time run:"<<(float) (end-begin)/CLOCKS_PER_SEC<<" s"; 
 30
 fi.close();fo.close(); 
 return 0; 
} 
2.3.4.3. Nguồn:  
 Cho một dãy N viên gạch lần lượt có độ cách nhiệt là các số a1, a2,...,an. 
Nếu xếp lần lượt các viên gạch theo trình tự đó thì độ cách nhiệt cả khối là a1 + 
a2 +...+ an + max(0,a2-a1) + max(0,a3-a2) + ...+max(0,an-an-1). Nhiệm vụ của bạn 
là tìm cách sắp xếp sao cho độ cách nhiệt của cả khối là lớn nhất có thể. 
Dữ liệu: Vào từ file văn bản INSUL.INP trong đó: 
 + Dòng đầu tiên là số nguyên dương N <500000 
 + N dòng tiếp theo, mỗi dòng ghi một số ai (1<=i<=N và 1<=ai<=10000). 
Kết quả: Ghi ra file INSUL.OUT - một dòng kết quả cần tìm. 
Ví dụ: 
INSUL.INP INSUL.OUT 
4 
5 
4 
1 
7 
24 
Ý tưởng: 
 + sắp xếp mảng A theo thứ tự tăng dần. 
Bài toán này dữ liệu vào tương đối lớn, nên để đảm bảo thời gian thực 
hiện, người lập trình nên sử dụng những thuật toán tốt hơn như Quick Sort, 
Counting Sort, Heap Sort, Merge Sort. Trong điều kiện dữ liệu vào của bài toán 
này, có phần tử dương và không quá 10000 nên phù hợp để lựa chọn thuật toán 
Counting Sort. 
 + Kết quả là cách sắp xếp theo thứ tự như sau: viên gạch thứ n, viên gạch 
thứ 1, viên gạch thứ n-1, viên gạch thứ 2.... 
Cài đặt chương trình: 
#include 
#include 
#include 
 31
using namespace std; 
long a[100001]; 
long n,res; 
void swap(long &a,long &b) 
{ 
 int tg=a; 
 a=b; 
 b=tg; 
} 
void counting_sort(long a[],long n) 
{ 
 long output[n]; 
 long max=a[0]; 
 long min=a[0]; 
 for (long i=1;i<n;i++) 
 { 
 if (a[i]>max) 
 max=a[i]; 
 else if(a[i]<min) 
 min=a[i]; 
 } 
 long k=max-min+1; 
 long dem[k]; 
 fill_n(dem,k,0); 
 for (long i=0;i<n;i++) 
 dem[a[i]-min]++; 
 for (long i=1;i<k;i++) 
 dem[i]+=dem[i-1]; 
 for (long i=0;i<n;i++) 
 { 
 output[dem[a[i]-min]-1]=a[i]; 
 32
 dem[a[i]-min]--; 
 } 
 for (long i=0;i<n;i++) 
 a[i]=output[i]; 
} 
int main() 
{ 
 res=0; 
 clock_t begin=clock(); 
 ifstream fi("INSUL.inp"); 
 ofstream fo("INSUL.out"); 
 fi>>n; 
 for (long i=0;i<=n-1;i++) 
 { 
 fi>>a[i]; 
 res+=a[i]; 
 } 
 counting_sort(a,n); 
 //in ket qua 
 for (long i=0;i<=n/2-1;i++) 
 res=res+a[n-i-1]-a[i]; 
 fo<<res; 
 fo<<"\n"; 
 clock_t end=clock(); 
 fo<<"time run:"<<(float) (end-begin)/CLOCKS_PER_SEC<<" s"; 
 fi.close();fo.close(); 
 return 0; 
} 
2.3.4.4. Đề thi HSG Tỉnh Nghệ An năm 2016-2017 
 Cho dãy số gồm n số nguyên a1, a2, , an và 2 số nguyên không âm L, R (L ≤ R). 
Yêu cầu: Đếm số cặp (i, j) thỏa mãn điều kiện: i ≤ j và L ≤ |ai++aj| ≤ R . 
 33
Dữ liệu vào: Từ file văn bản SEQ.INP gồm: 
 - Dòng đầu tiên chứa 3 số nguyên n, L, R (n ≤ 105 ; 0 ≤ L ≤ R ≤ 109) 
 - Dòng thứ hai chứa n số nguyên dương a1, a2,, an (ai ≤ 10
9) 
Kết quả: Ghi ra file văn bản SEQ.OUT gồm một số nguyên duy nhất là số lượng 
cặp (i, j) đếm được. 
 Ví dụ: 
SEQ.INP SEQ.OUT 
3 0 1 
1 -1 2 
4 
Hạn chế: - Có 50% số test ứng với 0 < n ≤ 103 
 - Có 50% số test ứng với 103 < n ≤ 105 
Ý tưởng: 
Bài toán này dữ liệu vào tương đối lớn, nên để đảm bảo thời gian thực 
hiện, người lập trình nên sử dụng những thuật toán tốt hơn như Quick Sort, 
Counting Sort, Heap Sort, Merge Sort. Trong chương trình tham khảo, tôi sử 
dụng thuật toán Quick Sort. 
Cài đặt chương trình: 
#include 
#include 
#include 
using namespace std; 
int a[100001]; 
int n,l,r; 
int d,c,res; 
void swap(int &a,int &b) 
{ 
 int tg=a; 
 a=b; 
 b=tg; 
} 
void QuickSort(int left, int right) 
{ 
 34
 int i=left; int j=right; 
 int pivot=a[(left+right)/2]; 
 while (i<=j) 
 { 
 while (a[i]<pivot) 
 i++; 
 while (a[j]>pivot) 
 j--; 
 if (i<=j) 
 { 
 swap(a[i],a[j]); 
 i++; 
 j--; 
 } 
 } 
 if (left<j) 
 QuickSort(left,j); 
 if (i<right) 
 QuickSort(i,right); 
} 
int main() 
{ 
 clock_t begin=clock(); 
 ifstream fi("SEQ.INP"); 
 ofstream fo("SEQ.out"); 
 fi>>n>>l>>r; 
 for (int i=0;i<=n-1;i++) 
 { 
 fi>>a[i]; 
 a[i]+=a[i-1]; 
 } 
 35
 QuickSort(0,n); 
 for (int i=0;i<=n-1;i++) 
 { 
 d=max(d,i+1); 
 c=max(d,c); 
 while ((d<n)&&(a[d]-a[i]<l)) 
 d++; 
 while ((c<n)&&(a[c+1]-a[i]<=r)) 
 c++; 
 if (d<=c) 
 res+=c-d+1; 
 } 
 fo<<res; 
 fo<<"\n"; 
 clock_t end=clock(); 
 fo<<"time run:"<<(float) (end-begin)/CLOCKS_PER_SEC<<" s"; 
 fi.close();fo.close(); 
 return 0; 
} 
2.4. Hiệu quả của sáng kiến kinh nghiệm 
Với cách làm như vậy đã rèn luyện kỹ năng lập trình cho các học sinh tham 
gia học đội tuyển, các em cũng có thói quen tối ưu hóa thuật toán và cài đặt 
chương trình phù hợp, để ý đến về thời gian chạy chương trình hơn (không chỉ 
quan tâm đến đáp số như trước đây). 
Qua các lần thi khảo sát chất lượng học sinh giỏi năm học 2019 - 2020 chất 
lượng học sinh dần dần tiến bộ (nhận thấy thông qua điểm lần sau thường cao 
hơn lần trước, mặc dù mức độ đề khó tăng dần). Và tôi nhận thấy khi gặp những 
bài toán có giải thuật sắp xếp, học sinh đã biết cách lựa chọn giải thuật phù hợp 
với dữ liệu vào của bài toán. 
Những năm trước khi bồi dưỡng HSG, tôi thường chỉ giới thiệu cho học 
sinh giải thuật Bubble Sort nên khi gặp những bài toán có sử dụng giải thuật sắp 
xếp thì học sinh không lấy được điểm tối đa. Vì vậy những năm trước đó kết quả 
cao nhất của học sinh là khuyến khích. 
 36
Năm 2019-2020 tôi tiếp tục được bồi dưỡng chính đội tuyển học sinh giỏi, 
sau khi giới thiệu và phân tích các giải thuật sắp xếp, tôi cho học sinh làm lại 
một số bài trong đề các năm thì kết quả rất khả quan. 
Kết quả HSG Tỉnh năm học 2019-2020 đạt giải 3 với số điểm 15. 
Như vậy rõ ràng việc giúp học sinh lựa chọn và cài đặt thuật toán tối ưu, 
hiệu quả đem lại là rất rõ rệt, tránh được việc học sinh mất điểm vì những lí do 
đáng tiếc trong kì thi học sinh giỏi THPT môn Tin học. 
 37
3. KẾT LUẬN VÀ KIẾN NGHỊ 
3.1. Kết luận 
Giải thuật sắp xếp có rất nhiều, nhưng trong đề tài này tôi chỉ giới thiệu một 
số thuật toán phù hợp với đối tượng là học sinh trong đội tuyển thi HSG Tỉnh 
môn Tin học và học sinh các lớp chuyên tin THPT. 
Bài tập vận dụng các thuật toán sắp xếp rất nhiều và đa dạng, nhưng trong 
sáng kiến kinh nghiệm trên tôi đã giới thiệu một số giải thuật sắp xếp, phân tích 
đánh giá từng nhóm giải thuật để học sinh có thể vận dụng một cách tối ưu nhất. 
Để chứng minh cho sự tối ưu của nhóm giải thuật đó tôi đưa ra nhiều bộ test với 
nhiều trường hợp khác nhau để học sinh có thể nắm được sự tối ưu của từng 
nhóm giải thuật. Từ đó học sinh sẽ hiểu sâu sắc hơn và giải quyết tốt hơn một số 
bài toán có vận dụng giải thuật sắp xếp, áp dụng làm các bài tập khác nhạy bén 
hơn nhằm nâng cao chất lượng học sinh giỏi và mang lại kết quả cao hơn trong 
các kì thi học sinh giỏi Tin. 
Ngoài ra, tôi cài đặt chương trình trên NNLT C++ để học sinh tiếp cận với 
ngôn ngữ mới. 
Đề tài này đã được áp dụng giảng dạy cho đội tuyển học sinh giỏi năm học 
2019-2020 của trường tôi. Đồng thời tôi đã trao đổi, chia sẽ với một số giáo viên 
cốt cán chuyên bồi dưỡng HSG của một số trường THPT của tỉnh Nghệ An và 
đạt được kết quả tốt. Tôi nhận thấy học sinh hứng thú, tích cực hơn trong việc 
học lập trình và kết quả rất khả quan trong các kỳ thi HSG môn tin học. Bên 
cạnh đó, việc tôi giới thiệu NNLT mới giúp học sinh đam mê, tìm tòi và tự học 
thêm NNLT mới phục vụ cho việc học trong tương lai. 
Do thời gian có hạn và kinh nghiệm chưa nhiều nên đề tài không tránh khỏi 
những thiếu sót, kính mong sự đóng góp ý kiến của các đồng nghiệp để đề tài 
được hoàn thiện hơn. 
3.2. Kiến nghị 
Đối với tổ chuyên môn, cần phân dạng bài tập cho học sinh khi giảng dạy. 
Ra nhiều dạng đề đúng với cấu trúc đề do Sở giáo dục Nghệ An quy định để đưa 
vào ngân hàng đề làm phong phú nguồn tài liệu bồi dưỡng học sinh giỏi của nhà 
trường. 
 Mong Ban giám hiệu nhà trường luôn duy trì việc tổ chức các kì thi khảo 
sát chất lượng học sinh giỏi môn Tin trong trường và liên trường để học sinh có 
cơ hội thử sức với các kì thi. 
Trên đây chỉ là những kiến nghị mang tính chủ quan của tôi, nhưng cũng rất 
mong được các cấp có thẩm quyền xem xét và sự góp ý của các đồng nghiệp. 
Nghệ An, ngày 20 tháng 3 năm 2021 
 38
TÀI LIỆU THAM KHẢO 
[1] Ngôn ngữ lập trình C++, Đặng Trung Kiên, giáo viên THPT Chuyên Lê 
Hồng Phong 
[2] Bài giảng chuyên đề, Lê Minh Hoàng 
[3] Tài liệu chuyên tin quyển 1, Hồ Sĩ Đàm (chủ biên), Đỗ Đức Đông, Lê Minh 
Hoàng, Nguyễn Thanh Hùng, NXB Giáo Dục Việt Nam 
[4] Trang web: https://vn.spoj.com/ 
[5] Trang web: https://codelearn.io/ 
 39
MỤC LỤC 
1. MỞ ĐẦU ........................................................................................................ 2 
1.1. Lý do chọn đề tài ..................................................................................... 2 
1.2. Mục đích nghiên cứu ............................................................................... 2 
1.3. Đối tượng nghiên cứu .............................................................................. 3 
1.4. Phương pháp nghiên cứu.......................................................................... 3 
2. NỘI DUNG NGHIÊN CỨU .......................................................................... 4 
2.1. Cơ sở lý luận ............................................................................................ 4 
2.2. Thực trạng ............................................................................................... 4 
2.2.1 Thực trạng trước khi nghiên cứu ........................................................ 4 
2.3. Các biện pháp sử dụng để giải quyết vấn đề ............................................. 4 
2.3.1. Giới thiệu về bài toán sắp xếp ........................................................... 4 
2.3.1.1. Khái niệm ................................................................................... 4 
2.3.1.2. Mục đích của sắp xếp.................................................................. 5 
2.3.2. Một thuật toán sắp xếp cơ bản ........................................................... 5 
2.3.1.1. Sắp xếp nổi bọt (Bubble Sort) ..................................................... 5 
2.3.1.2. Sắp xếp chọn (Selection Sort) ..................................................... 6 
2.3.1.3. Sắp xếp chèn (Insert Sort) ........................................................... 8 
2.3.1.4. Thuật toán Shell Sort ................................................................ 10 
2.3.1.5. Sắp xếp kiểu phân đoạn (QuickSort) ......................................... 12 
2.3.1.6. Sắp xếp bằng phép đếm phân phối (Counting Sort) .................. 15 
2.3.1.7. Sắp xếp kiểu vun đống (Heap sort) ........................................... 16 
2.3.1.8. Sắp xếp trộn (Merge Sort) ......................................................... 19 
2.3.3. Đánh giá thuật toán và những yếu tố cần quan tâm khi sử dụng thuật 
toán ........................................................................................................... 22 
2.3.3.1. Đánh giá thuật toán ................................................................... 22 
2.3.3.2. Những yếu tố cần quan tâm ...................................................... 23 
2.3.4. Một số bài toán áp dụng .................................................................. 25 
2.3.4.1. Nguồn  25 
2.3.4.2. QUÀ TẶNG ............................................................................. 27 
2.3.4.3. Nguồn:  ........................... 30 
2.3.4.4. Đề thi HSG Tỉnh Nghệ An năm 2016-2017 .............................. 32 
2.4. Hiệu quả của sáng kiến kinh nghiệm ...................................................... 35 
3. KẾT LUẬN VÀ KIẾN NGHỊ ..................................................................... 37 
3.1. Kết luận ................................................................................................. 37 
3.2. Kiến nghị ............................................................................................... 37 
TÀI LIỆU THAM KHẢO ............................................................................... 38