SKKN Một số phương pháp sắp xếp trong chương trình tin hoc phổ thông

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ 
TRƯỜNG THPT HOẰNG HÓA 2
SÁNG KIẾN KINH NGHIỆM
TÊN ĐỀ TÀI
MỘT SỐ PHƯƠNG PHÁP SẮP XẾP TRONG CHƯƠNG TRÌNH TIN HOC PHỔ THÔNG
Người thực hiện: TRƯƠNG THỊ QUÝ
Chức vụ: Giáo viên
Đơn vị công tác: Trường THPT HOẰNG HÓA2
SKKN thuộc môn: Tin học
THANH HOÁ NĂM 2016
MỤC LỤC
A. PHẦN MỞ ĐẦU .2
I. LÝ DO CHỌN ĐỀ TÀI.......................................................................................2
II. MỤC ĐÍCH NGHIÊN CỨU..............................................................................2
III. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU	2 1.Đối tượng	2
	2. Phạm vi	3
IV. NHIỆM VỤ VÀ PHƯƠNG PHÁP NGHIÊN CỨU:	3
B. PHẦN NỘI DUNG	4
I. CƠ SỞ LÝ LUẬN	4
	1. Đánh giá thực trạng	4
II. TỔNG QUAN	4
II.1.THỜI GIAN THỰC HIỆN CHƯƠNG TRÌNH	4
	 II.1.1 Ðơn vị đo thời gian thực hiện...4
II.1.2 Thời gian thực hiện trong trường hợp xấu nhất5
III. CÁC PHƯƠNG PHÁP SẮP XẾP ĐƠN GIẢN...6
III.1	Sắp xếp chọn (SelectionSort).6
III.2 Sắp xếp chèn (InsertionSort)...7
	III.3 Sắp xếp nổi bọt (Bubble Sort).8
III.4 Sắp xếp nhanh (QUICKSORT)9
	III.5 Sắp xếp bằng đếm phân phối (Distribution Counting)..13
IV. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN SẮP SẾP14
V. HIỆU QUẢ CỦA ĐỀ TÀI:..18
PHẦN C: KẾT LUẬN 19
I. KẾT LUẬN ...19
II. NHỮNG KIẾN NGHỊ LÀM TĂNG TÍNH KHẢ THI CỦA ĐỀ TÀI.19
III. Tài liệu tham khảo: .20
A. PHẦN MỞ ĐẦU
I. LÝ DO CHỌN ĐỀ TÀI:
Năm học 2015 -2016 là năm tôi được tổ chuyên môn phân công dạy Tin học 11 và đứng ôn đội tuyển học sinh giỏi môn Tin học. Đứng trước nhiệm vụ của năm học này, tôi đã lên kế hoạch và mục tiêu dạy học cho mình nhằm đạt hiệu quả dạy học được tôt nhất cũng như sẽ đạt được chỉ tiêu đăng kí. Và khi ôn thi học sinh giỏi thì tôi và học sinh thấy có rất nhiều thuật toán sắp sếp vậy thì nên sử dụng thuật toán nào đây và thuật toán nào là tối ưu và phù hợp nhất với bài toán của mình.
Trong quá trình giảng dạy, tôi nhận thấy việc lựa chọn các thuật toán về sắp xếp ở học sinh còn lúng túng chưa để ý đến thời gian và bộ nhớ khi thực hiện chương trình. Mặt khác việc giới thiệu các thuật toán sắp xếp trong sách giáo khoa Tin học 11 còn hạn chế về việc thể hiện và nhấn mạnh các thuật toán về sắp xếp.
Từ thực tế đó tôi mạnh dạn chon đề tài “ Một số phương pháp sắp xếp trong chương trình Tin học phổ thông”
II. MỤC ĐÍCH NGHIÊN CỨU:
Đề tài xây dựng các phương pháp sắp xếp thành một hệ thống để cho học sinh biết cách nhận biết và lựa chọn phương pháp một cách tổng quát thông qua các tiêu chí cơ bản. Từ đó áp dụng giải nhanh các bài tập ôn tập và vận dụng để giải các bài toán trong kiểm tra đánh giá, ôn thi học sinh giỏi.
Nhằm nâng cao nghiệp vụ công tác của bản thân và nâng cao chất lượng của học sinh, giúp học sinh có hứng thú hơn trong quá trình học tập và ôn thi học sinh giỏi. 
III. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU: 
1. Đối tượng
Đối tượng nghiên cứu là học sinh lớp 11 và các học sinh trong đội tuyển học sinh giỏi.
2. Phạm vi
Phạm vi nghiên cứu nội dung bài 4 – Bài toán và thuật toán, một số bài toán sắp xếp, thuật toán sắp xếp trong chương trình Tin học 10 để nắm vững hơn kiến thức cho các em học sinh lớp 11 trong kiểm tra đánh giá và ôn thi học sinh giỏi.
IV. NHIỆM VỤ VÀ PHƯƠNG PHÁP NGHIÊN CỨU:
Để tìm hiểu cách dạy học đạt kết quả cao trong việc giới thiệu một số phương pháp sắp xếp, bản thân tôi vận dụng sáng tạo cơ sở lí luận với thực tiễn dạy học. Các kiến thức và kinh nghiệm dạy học được tôi trực tiếp tiến hành giảng dạy trên lớp, ôn luyện thi học sinh giỏi từ năm 2009 tới nay.
 Sáng kiến kinh nghiệm đang trình bày của tôi dựa theo các luận cứ khoa học hướng đối tượng, cụ thể: thuyết trình, quan sát, điều tra cơ bản, phân tích kết quả thực nghiệm sư phạm,v.v phù hợp với bài học và môn học thuộc lĩnh vực cấu trúc dữ liệu.
B. PHẦN NỘI DUNG
I. CƠ SỞ LÝ LUẬN
1. Đánh giá thực trạng :
- Phần lớn học sinh đã nhận thấy vai trò của các thuật toán sắp xếp. Nhưng các thuật toán mà các em biết chỉ hạn hẹp trong chương trình sách giáo khoa Tin học 11. Do đó để giải quyết hầu hết các bài toán đơn giản liên quan đến thuật toán sắp xếp là rất khó khăn.
- Mặt khác nếu các em học sinh có linh hoạt sử dụng các phương pháp sắp xếp trong chương trình phổ thông được thì chỉ đảm bảo được về mặt kết quả, còn về đảm bảo thời gian chạy chương trình sao cho cứ mỗi test là 1 giây thì đa số học sinh chưa giải quyết được.
- Do vậy nên đề tài đưa ra các thuật toán sắp xếp để học sinh nắm được và sử dụng linh hoạt đồng thời cho học sinh thấy được thời gian chạy của từng chương trình mà áp dụng với các bài toán có số liệu lớn, nhỏ khác nhau.
II. TỔNG QUAN
II.1.THỜI GIAN THỰC HIỆN CHƯƠNG TRÌNH
 Thời gian thực hiện một chương trình là một hàm của kích thước dữ liệu vào, ký hiệu T(n) trong đó n là kích thước (độ lớn) của dữ liệu vào.
Ví dụ 1-1: Chương trình tính tổng của n số có thời gian thực hiện là T(n) = cn trong đó c là một hằng số.
Thời gian thực hiện chương trình là một hàm không âm, tức là 
T(n) ≥ 0, n ≥ 0.
II.1.1 Ðơn vị đo thời gian thực hiện.
Ðơn vị của T(n) không phải là đơn vị đo thời gian bình thường như giờ, phút giây... mà thường được xác định bởi số các lệnh được thực hiện trong một máy tính lý tưởng.
Ví dụ 1-2: Khi ta nói thời gian thực hiện của một chương trình là T(n) = Cn thì có nghĩa là chương trình ấy cần Cn chỉ thị thực thi.
II.1.2 Thời gian thực hiện trong trường hợp xấu nhất.
Nói chung thì thời gian thực hiện chương trình không chỉ phụ thuộc vào kích thước mà còn phụ thuộc vào tính chất của dữ liệu vào. Nghĩa là dữ liệu vào có cùng kích thước nhưng thời gian thực hiện chương trình có thể khác nhau. Chẳng hạn chương trình sắp xếp dãy số nguyên tăng dần, khi ta cho vào dãy có thứ tự thì thời gian thực hiện khác với khi ta cho vào dãy chưa có thứ tự, hoặc khi ta cho vào một dãy đã có thứ tự tăng thì thời gian thực hiện cũng khác so với khi ta cho vào một dãy đã có thứ tự giảm.
Vì vậy thường ta coi T(n) là thời gian thực hiện chương trình trong trường hợp xấu nhất trên dữ liệu vào có kích thước n, tức là: T(n) là thời gian lớn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n.
II.2. CÁCH SẮP XẾP DỮ LIỆU VÀ NGÔN NGỮ SỬ DỤNG
Danh sách các đối tượng cần được sắp xếp là một mảng lưu trữ các kiểu dữ liệu có quan hệ thứ tự (như kiểu số nguyên, số thực, )
Mục đích của việc sắp xếp là tổ chức lại các phần tử trong mảng sao cho chúng được sắp thứ tự tương ứng với quy luật sắp xếp.
Ðể trình bày các ví dụ minh họa chúng ta sẽ dùng PASCAL làm ngôn ngữ thể hiện và sử dụng khai báo sau:
CONST N = 10;
Var a: array[1..N]of integer;
Procedure hd(var x,y:integer);
Var	tg:integer;
Begin
	tg:=x;
x:=y;
y:=tg;
	 End;
Cần thấy rằng thủ tục hd lấy O(1) thời gian vì chỉ thực hiện 3 lệnh gán nối tiếp nhau.
III. CÁC PHƯƠNG PHÁP SẮP XẾP ĐƠN GIẢN.
III.1	Sắp xếp chọn (SelectionSort)
a) Phương pháp:
Ðây là phương pháp sắp xếp đơn giản nhất được tiến hành như sau:
· Ðầu tiên chọn phần tử có giá trị nhỏ nhất trong n phần tử từ a[1] đến a[n] và hoán vị nó với phần tử a[1].
· Chọn phần tử có giá trị nhỏ nhất trong n-1phần tử từ a[2] đến a[n] và hoán vị nó với a[2].
· Tổng quát ở bước thứ i, chọn phần tử có giá trị nhỏ nhất trong n-i+1 phần
tử từ a[i] đến a[n] và hoán vị nó với a[i].
· Sau n-1 bước này thì mảng đã được sắp xếp.
Phương pháp này được gọi là phương pháp chọn bởi vì nó lặp lại quá trình chọn phần tử nhỏ nhất trong số các phần tử chưa được sắp.
b) Chương trình:
PROCEDURE SelectionSort;
VAR
T,i,j,y: integer;
BEGIN
{1} FOR i := 1 TO n-1 DO BEGIN
{2} T := a[i];
{3} FOR j := i+1 TO n DO
{4} IF a[j] < T THEN
BEGIN
{5} T := a[j];
{6} y := j;
END;
{7} hd(a[i],a[y]);
END;
END;
c) Đánh giá:
Trước hết ta có thủ tục hd một hằng thời gian như đã nói ở mục trên.
Các lệnh {2} lấy O(1) thời gian. Vòng lặp for {3} – {6} thực hiện n-i lần, vì j chạy từ i+1 đến n, mỗi lần lấy O(1), nên lấy O(n-i) thời gian. Do đó thời gian tổng cộng là: 
T(n) = 	tức là O(n2).
III.2 Sắp xếp chèn (InsertionSort)
a) Phương pháp:
Trước hết ta xem phần tử a[1] là một dãy đã có thứ tự.
Bước 1, xen phần tử a[2] vào danh sách đã có thứ tự a[1] sao cho a[1], a[2] là một danh sách có thứ tự.
· Bước 2, xen phần tử a[3] vào danh sách đã có thứ tự a[1], a[2] sao cho
a[1], a[2], a[3] là một danh sách có thứ tự.
·Tổng quát, bước i, xen phần tử a[i+1] vào danh sách đã có thứ tự a[1],a[2],..a[i] sao cho a[1], a[2],.. a[i+1] là một danh sách có thứ tự.
· Phần tử đang xét a[j] sẽ được xen vào vị trí thích hợp trong danh sách các phần tử đã được sắp trước đó a[1],a[2],..a[j-1] bằng cách so sánh giá trị của a[j] với giá trị của a[j-1] đứng ngay trước nó. Nếu giá trị của a[j] nhỏ hơn giá trị của a[j-1] thì hoán đổi a[j-1] và a[j] cho nhau và tiếp tục so sánh giá trị của a[j-1] (lúc này a[j-1] chứa nội dung của a[j]) với giá trị của a[j-2] đứng ngay trước nó...
b) Chương trình:
PROCEDURE InsertionSort;
VAR
i,j: integer;
BEGIN
{1} FOR i := 2 TO n DO BEGIN
{2} J := i;
{3} WHILE (j>1) AND (a[j] < a[j-1])
 DO BEGIN
{4} hd(a[j], a[j-1]);
{5} j := j-1;
END;
END;
END;
c) Đánh giá:
Ta thấy các lệnh {4} và {5} đều lấy O(1). Vòng lặp {3} chạy nhiều nhất i-1 lần, mỗi lần tốn O(1) nên {3} lấy i-1 thời gian. Lệnh {2} và {3} là hai lệnh nối tiếp nhau, lệnh {2} lấy O(1) nên cả hai lệnh này lấy i-1. Vòng lặp {1} có i chạy từ 2 đến n nên nếu gọi T(n) là thời gian để sắp n phần tử thì ta có:
T(n) = 	tức là O(n2).
III.3 Sắp xếp nổi bọt (Bubble Sort)
a) Phương pháp:
Chúng ta tưởng tượng rằng các phần tử được lưu trong một mảng dọc, qua quá trình sắp, phần tử nào có giá trị “nhẹ” sẽ được nổi lên trên. Chúng ta duyệt toàn mảng, từ dưới lên trên. Nếu hai phần tử ở cạnh nhau mà không đúng thứ tự tức là nếu phần tử “nhẹ hơn” lại nằm dưới thì phải cho nó “nổi lên” bằng cách đổi chỗ hai phần tử này cho nhau. Cụ thể là:
· Bước 1: Xét các phần tử từ a[n] đến a[2], với mỗi phần tử a[j], so sánh giá trị của nó với giá trị của phần tử a[j-1] đứng ngay trước nó. Nếu giá trị của a[j] nhỏ hơn giá trị của a[j-1] thì hoán đổi a[j] và a[j-1] cho nhau.
· Bước 2: Xét các phần tử từ a[n] đến a[3], và làm tương tự như trên.
· Sau n-1 bước thì kết thúc.
b) Chương trình:
PROCEDURE BubbleSort;
VAR
i,j: integer;
BEGIN
{1} FOR i := 1 to n-1 DO
{2} FOR j := n DOWNTO i+1 DO
{3} IF a[j] < a[j-1] THEN
{4} hd(a[j],a[j-1]);
END;
c) Đánh giá:
Dòng lệnh {3} lấy một hằng thời gian. Vòng lặp {2} thực hiện (n-i) bước, mỗi bước lấy O(1) nên lấy O(n-i) thời gian. Như vậy đối với toàn bộ chương trình ta có:
T(n) = 	tức là O(n2).
Một thuật toán nữa cũng có thời gian thực hiện O(n2) là:
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>a[j] then hd(a[i],a[j])
end;
III.4 Sắp xếp nhanh (QUICKSORT).
a. Phương pháp:
Chúng ta vẫn xét mảng a các phần tử a[1]..a[n]. Giả sử v là 1 giá trị mà ta gọi là chốt (pivot). Ta phân hoạch dãy a[1]..a[n] thành hai mảng con "bên trái" và "bên phải". Mảng con "bên trái" bao gồm các phần tử có giá trị nhỏ hơn chốt, mảng con "bên phải" bao gồm các phần tử có giá trị lớn hơn hoặc bằng chốt.
Sắp xếp mảng con “bên trái” và mảng con “bên phải” thì mảng đã cho sẽ được sắp bởi vì tất cả các giá trị trong mảng con “bên trái“ đều nhỏ hơn các giá trị trong mảngcon “bên phải”.
Việc sắp xếp các mảng con “bên trái” và “bên phải” cũng được tiến hành bằng phương pháp nói trên.
Một mảng chỉ gồm một phần tử hoặc gồm nhiều phần tử có giá trị bằng nhau thì đã có thứ tự.
Chọn giá trị lớn nhất trong hai phần tử có giá trị khác nhau đầu tiên kể từ trái qua.
Nếu mảng chỉ gồm một phần tử hay gồm nhiều phần tử có giá trị bằng nhau thì không có chốt.
Ðể phân hoạch mảng ta dùng 2 "con nháy" L và R trong đó L từ bên trái và R từ bên phải, ta cho L chạy sang phải cho tới khi gặp phần tử có giá trị ≥ chốt và cho R chạy sang trái cho tới khi gặp phần tử có giá trị R. Khi đó L sẽ là điểm phân hoạch, cụ thể là a[L] là phần tử đầu tiên của mảng con “bên phải”.
b) Chương trình:
FUNCTION Findch(i,j:integer): integer;
VAR c,k : integer;
BEGIN
{1} k := i+1;
{2} c := a[i];
{3} WHILE (k <= j) AND (a[k]= c) DO k:= k+1;
{4} IF k > j THEN Fidch := 0
ELSE
 {5}IF a[k] > c THEN Findch := k
 ELSE Findch := i;
END;
Trong hàm Findch các lệnh {1}, {2}, {3} và {4} nối tiếp nhau, trong đó chỉ có lệnh WHILE là tốn nhiều thời gian nhất do đó thời gian thực hiện của hàm Findch phụ thuộc vào thời gian thực hiện của lệnh này. Trong trường hợp xấu nhất (không tìm thấy chốt) thì k chạy từ i+1 đến j, tức là vòng lặp thực hiện j-i lần, mỗi lần O(1) do đó tốn j-i thời gian. Đặc biệt khi i=1 và j=n, thì thời gian thực hiện là n-1 hay T(n) = O(n).
Hàm Phanhoach nhận vào ba tham số i, j và chốt để thực hiện việc phân hoạch mảng a[i]..a[j] theo chốt và trả về giá trị L là chỉ số đầu tiên của mảng “bên phải”. Hai con nháy L, R sẽ được sử dụng để thực hiện việc phân hoạch như đã trình bày.
FUNCTION Phanhoach(i,j,c:integer):integer ;
VAR L,R : integer;
BEGIN
{1} L := i; {Ðặt con nháy L ở cực trái}
{2} R := j; {Ðặt con nháy R ở cực phải}
{3} WHILE L <= r DO BEGIN
{L tiến sang phải}
{4} WHILE a[L] < c DO L := L+1;
{R tiến sang trái}
{5} WHILE a[R] >= c DO R := R-1;
{6} IF L < R THEN hd(a[L],a[R]);
END;
{7} Phanhoach := L; {Trả về điểm phân hoạch}
END;
Trong hàm Phanhoach các lệnh {1}, {2}, {3} và {7} nối tiếp nhau, trong đó thời gianthực hiện của lệnh {3} là lớn nhất, do đó thời gian thực hiện của lệnh {3} sẽ là thời gian thực hiện của hàm Phanhoach. Các lệnh {4}, {5} và {6} là thân của lệnh {3}, trong đó lệnh {6} lấy O(1) thời gian. Lệnh {4} và lệnh {5} thực hiện việc di chuyển L sang phải và R sang trái, thực chất là duyệt các phần tử mảng, mỗi phần tử một lần, mỗi lần tốn O(1) thời gian. Tổng cộng việc duyệt này tốn j-i thời gian. Vòng lặp {3} thực chất là để xét xem khi nào thì duyệt xong, do đó thời gian thực hiện của lệnh {3} chính là thời gian thực hiện của hai lệnh {4} và {5} và do đó là j-i. Đặc biệt khi i=1 và j=n ta có T(n) = O(n).
Bây giờ chúng ta trình bày thủ tục cuối cùng có tên là QuickSort và chú ý rằng để sắp xếp mảng A gồm n phần tử ta chỉ cần gọi QuickSort(1,n).
PROCEDURE Quicksort(i,j:integer);
VAR
u,v, k : integer;
BEGIN
v := Findch(i,j);
IF v 0 THEN 
BEGIN
u := a[v];
k := Phanhoach(i,j,u);
QuickSort(i,k-1);
QuickSort(k,j);
END;
END;
Giả sử các giá trị của mảng khác nhau nên hàm Findch luôn tìm được chốt và đệ quy chỉ dừng khi kích thước bài toán bằng 1.
Gọi T(n) là thời gian thức hiện việc QuickSort mảng có n phần tử.
Thời gian để tìm chốt và phân hoạch mảng như đã phân tích đều là O(n) = n.
Khi n = 1, thủ tục QuickSort chỉ làm một nhiệm vụ duy nhất là gọi hàm Findch với kích thước bằng 1, hàm này tốn thời gian O(1) =1.
Trong trường hợp xấu nhất là ta luôn chọn phải phần tử có giá trị lớn nhất làm chốt, lúc bấy giờ việc phân hoạch bị lệch tức là mảng bên phải chỉ gồm một phần tử chốt, còn mảng bên trái gồm n-1 phần tử còn lại. Khi đó ta có thể thành lập phương trình đệ quy như sau:
T(n)=
	1 nêu n = 1
T(n - 1) + T(1) + n nêu n > 1
Giải phương trình này bằng phương pháp truy hồi T(n) =O(n2)
Có trường hợp thực thi cỡ O(nlogn) trong ttrường hợp trung bình
c) Kết luận:	
Nếu chương trình ít gọi tới thủ tục sắp xếp và chỉ trên tập dữ liệu nhỏ, thì việc sủ dụng một thuật toán phức tạp (tuy có hiệu quả) là không cần thiết, khi đó có thể sử dụng thuật toán đơn giản có độ phức tạp O(N2), dễ cài đặt. Tuy nhiên vì độ phức tạp là O(N2) nên thời gian thực hiện tăng lên 4 lần khi số lượng phần tử tăng lên gấp đôi. Do đó, trong trường hợp sắp xếp với dữ liệu lớn thì nên sử dụng thuật toán sắp xếp nhanh.
III.5 Sắp xếp bằng đếm phân phối (Distribution Counting)
a) Phương pháp:
Trong trường hợp khoá các phần tử a[1],a[2],  ,a[n] là các số nguyên trong nằm trong khoảng từ 0 tới k ta có thuật toán đơn giản và hiệu quả như sau:
Xây dựng dãy C[0], C[1], C[2],,C[k] trong đó C[v] là số lần xuất hiện của khoá V trong dãy .
for V := 0 to K do c[V] := 0;{Khởi tạo dãy c}
for i := 1 to n do c[a[i].key] := c[a[i].key] + 1;
Như vậy sau khi sắp sếp 
Các phần tử có khoá bằng 0 đứng trong đoạn từ vị trí 1 đến vị trí C[0] 
Các phần tử có khoá bằng 1 đứng trong đoạn từ vị trí C[0]+1 đến vị trí C[0] +C[1] 
Các phần tử có khoá bằng 2 đứng trong đoạn từ vị trí C[0] +C[1] +1 đến vị trí C[0]+ C[1] +C[2].
.
Các phần tử có khoá bằng V đứng trong đoạn từ vị trí C[0] + C[1]++C[V-1] + 1 đến vị trí C[0]+ C[1] +C[2] +.+ C[V-1] +C[V]
..
Các phần tử có khoá bằng K đứng trong đoạn từ vị trí C[0]+C[1]++C[K-1]+1 đến vị trí C[0]+ C[1] +C[2] +.+ C[K1] +C[K]
b. Đánh giá:
Độ phức tạp của thuật toán là: T(n)= O(Max(N,K))
Với thuật toán này rất phù hợp với những dạng bài tập liên quan tới tìm tần suất số lần xuất hiện của các phần tử trong mảng hoặc trong xâu
IV. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN SẮP SẾP
VD1: Cho dãy a1, a2, a3, ...,an, cá c đôi một khác nhau và số nguyên dương k(1<=k<=n). Hãy đưa ra giá trị nhỏ thứ k trong dãy
Giải:
- Nếu n<= 5000 ta có thể sử dụng thuật toán sắp xếp nổi bọt có độ phức tạp O(n2).
- nếu n >=5000 ta nên sử dụng thuật toán QUICKSORT
Ta có thể tìm được giá trị nhỏ thứ k hiệu quả hơn cụ thể như sau:
Sử dụng thuật toán nổi bọt và chỉ sắp xếp đến phần tử thứ k
For i:=1 to k do 
For j:=n downto i+1 do 
If a[j-1] >a[j] then 
 Begin
	Tg:=a[j];
A[j]:=a[j-1];
A[j-1]:=tg;
 End;
Sử dụng thuật toán sắp xếp nhanh:
Procedure quicksort(l,h:longint);
Var I,j:longint; x,tg:longint;
Begin
If (l=k) then
 	Begin
 	i:=l;
j:=h;
x:=a[(h+l) div 2];
repeat
while a[i]<x do i:=i+1;
while a[j]>x do j:=j-1;
if i<=j then
begin
tg:=a[i];
a[i]:=a[j];
a[j]:=tg;
i:= i+1;
j:=j- 1;
end;
 until i>j;
 if l<j then Quicksort(L,j);
 if i<h then Quicksort(i,h);
 end;
end;
Bài 2: Xét tập F(n) tất cả các số hửu tỷ thuộc trong đoạn [0, 1] với mẫu số không vượt qua N (1 ≤ N ≤ 100)
Yêu cầu : Sắp xếp các phân số trong tập F(N) theo thứ tụe tăng dần, đưa ra phân số thứ K.
Dữ liệu vào: Vào từ file PHANSO.INP chứa duy nhất số N.
Dữ liệu ra: Ghi ra file PHANSO.OUT chứa một dòng là dãy phân số đã được sắp xếp tăng dần.
Ví dụ : 
PHANSO.INP
PHANSO.OUT
7
0/1; 1/7; 1/6; 1/5; 1/4; 2/7; 1/3; 2/5; 3/7; 1/2; 4/7; 3/5; 2/3; 5/7; 3/4; 4/5; 5/6; 6/7; 1/1
Giải : 
- Khi nhìn vào bài toán ta thấy rằng đây ta có thể sử dụng thuật toán sắp xếp tương tự thật toán sắp xếp nổi bọt và cùng có độ phức tạp la O(n2). Vì do N nhỏ nên chúng ta không nhất thiết phải sử dụng QUICKSORT.
- Xét các phần tử của dãy ta thấy phần tử của dãy gồm phức hợp của 3 giá trị : Tử số, mẫu số và thương nên ta sử dụng mảng một chiều kiểu bản ghi để lưu các giá trị đó và sắp sếp chúng tăng dần.
- Các tử số của phần tử i sẽ nhận giá trị từ 0 đến N. Các mẫu số sẽ nhận giá trị từ i+1 đến N.
- Dùng hàm UCLN để rút gọn phân số.
Code : 
const fi='bai1.inp';
 fo='bai2.out';
type phanso = record
 x,y: longint;
 end;
var n: longint;
 i,j: longint;
 a: array[1..100,1..100] of boolean;
 b: array[1..5000] of phanso;
procedure nhapdl;
begin
 assign(input, fi); reset(input);
 assign(output, fo); rewrite(output);
 readln(n);
end;
procedure dongdl;
begin
 close(input); close(output);
end;
function ucln(a,b: longint): longint;
begin
 while (a0) and(b0) do
 if a>b then a:= a mod b
 else b:= b mod a;
 exit(a+b);
end;
procedure xuli;
var i,ii,j: longint;tg: phanso;
begin
 fillchar(a, sizeof(a), false);
 for i:= 1 to n-1 do
 for j:= i+1 to n do a[i div ucln(i,j), j div ucln(i,j)]:= true;
 ii:=0;
 for i:= 1 to n-1 do
 for j:= i+1 to n do
 if a[i,j] then
 begin
 inc(ii);
 b[ii].x:=i;
 b[ii].y:=j;
 end;
 n:=ii;
 for i:= 1 to n-1 do
 for j:= i+1 to n do
 if b[i].x/b[i].y >b[j].x/b[j].y then
 begin
 tg:= b[i];
 b[i]:= b[j];
 b[j]:= tg;
 end;
end;
procedure inkq;
begin
 write('0/1');
 for i:= 1 to n do write(b[i].x,'/',b[i].y);
 write('1/1');
end;
BEGIN
 nhapdl;
 xuli;
 inkq;
 dongdl;
END.
Bài 3: Cho dãy gồm N (N ≤ 30000) số tự nhiên không vượt quá 109, tìm số tự nhuên nhỏ nhất không xuất hiện trong dãy.
Dữ liệu vào file SN.INP có dạng
Dòng đầu là số nguyên N
Dòng thứ hai gồm N số
Kết quả ra