TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO
THỰC TẬP CƠ SỞ
ĐỀ TÀI:
TÌM HIỂU VỀ NGÔN NGỮ LẬP TRÌNH C VÀ ỨNG DỤNG
NGÔN NGỮ LẬP TRÌNH C CÀI ĐẶT THUẬT TOÁN
SẮP XẾP CHỌN VÀ SẮP XẾP CHÈN
Giáo viên hướng dẫn:
Sinh viên thực hiện:
Lớp:
Thái Nguyên, tháng 5 năm 2010
MỤC LỤC
2
LỜI NÓI ĐẦU
Hiện nay trong hầu hết các hệ lưu trữ, quản lý dữ liệu, thao tác tìm kiếm thường
được thực hiện nhiều nhất để khai thác thông tin một cách nhanh chóng và muốn việc
tìm kiếm một cách nhanh chóng thì dữ liệu cần phải được sắp xếp sẵn, ngăn nắp theo
một trật tự, hệ thống nhất định sẽ cho phép chúng ta tìm kiếm nhanh, việc sắp xếp có ý
nghĩa rất lớn trong quản lí và lưu trữ .
Do đó khi xây dựng một hệ quản lý thông tin trên máy tính, bên cạnh các thuật
toán tìm kiếm, các thuật toán sắp xếp dữ liệu cũng là một trong những chủ đề được
quan tâm hàng đầu.
Hiện nay có rất nhiều thuật toán sắp xếp đã được xây dựng và mỗi thuật toán lại
có mức độ hiệu quả khác nhau, trong đó có những thuật toán cơ bản như: sắp xếp nổi
bọt, sắp xếp chèn, sắp xếp chọn, sắp xếp trộn, sắp xếp vun đống, sắp xếp nhanh
Trong bài báo cáo thực tập cơ sở này em sẽ tìm hiểu chi tiết về hai thuật toán là:
thuật toán sắp xếp chèn, sắp xếp chọn và ứng dụng ngôn ngữ lập trình C để cài đặt hai
thuật toán trên.
Em xin được gửi lời cảm ơn trân thành đến cô Th.s Đoàn Thị Bích Ngọc đã
giúp đỡ em trong quá trình thực hiện đề tài này.

tạm thời lúc này chính là giá trị lớn nhất trong dãy số.
4
1.1.2 Biểu diễn thuật toán
Ðể trình bày một thuật toán hay biểu diễn một thuật toán, ta có thể sử dụng các
phương pháp biểu diễn thuật toán sau đây:
Dùng ngôn ngữ tự nhiên.
Dùng lưu đồ hay sơ đồ khối.
Dùng mã giả.
Lưu đồ:
Ngôn ngữ lưu đồ hay sơ đồ khối là một công cụ rất trực quan để diễn đạt các
thuật toán. Biểu diễn bằng lưu đồ sẽ giúp ta có được một cái nhìn tổng quan về toàn
cảnh của quá trình xử lý theo thuật toán.
Lưu đồ là một hệ thống các nút có hình dạng khác nhau, thể hiện các chức năng
khác nhau và được nối với nhau bởi các cung. Lưu đồ được tạo thành bởi 4 thành phần
chủ yếu sau đây:
• Nút giới hạn: được biểu diễn bởi hình ôvan có ghi chữ bên trong như :
Các nút trên còn được gọi là nút đầu và nút cuối của lưu đồ.
• Nút thao tác: là một hình chữ nhật có ghi các lệnh cần thực hiện
• Nút điều kiện: thường là một hình thoi có ghi điều kiện cần kiểm tra. Trong các
cung nối với nút này có 2 cung ra chỉ hướng đi theo 2 trường hợp: điều kiện
đúng và điều kiện sai.
• Cung: là các đường nối từ nút này đến nút khác của lưu đồ.
Hoạt động của thuật toán theo lưu đồ được bắt đầu từ nút đầu tiên. Sau khi thực
hiện các thao tác hoặc kiểm tra điều kiện ở mỗi nút thì bộ xử lý sẽ theo một cung để
đến nút khác. Quá trình thực hiện thuật toán dừng khi gặp nút kết thúc hay nút cuối.
Trong bài này chúng ta chủ yếu là sử dụng ngôn ngữ tự nhiên và mã giả để trình
bày thuật toán. Trong cách sử dụng ngôn ngữ tự nhiên ta sẽ liệt kê các bước thực hiện
5
các thao tác hay công việc nào đó của thuật toán bằng ngôn ngữ mà con người sử dụng
một cách phổ thông hàng ngày. Các thuật toán được trình bày trong hai ví dụ trên

khiển của ngôn ngữ lập trình PASCAL). Trước khi viết các bước thực hiện thuật toán
ta thường ghi rõ những gì được cho trước (phần nhập) và kết quả cần đạt được
(phần xuất).
Thuật toán tìm phần tử lớn nhất trong một dãy hữu hạn các số nguyên:
Nhập: dãy số a
1
, a
2
, . . ., a
n
Xuất: max là giá trị lớn nhất trong dãy số đã cho trong input.
Thuật toán:
1. max := a
1
2. for i := 2 to n do
if max < a
1
then max := a
1
3. max là giá trị lớn nhất trong dãy số.
Thuật toán giải phương trình bậc hai ax
2
+ bx + c = 0 (a ≠ 0):
7
Nhập : 3 hệ số a, b, c
Ðiều kiện : a ≠ 0
Xuất : nghiệm của phương trình
Thuật toán:
1. delta := b
2

giải cho bài toán.
Tính xác định (definiteness): Các bước trong thuật toán phải chính xác rõ ràng.
Tính hữu hạn (finiteness): Thuật toán phải cho ra lời giải (hay kết quả) sau một số
hữu hạn bước.
Tính hiệu quả (về thời gian): Thuật toán cần phải được thực hiện một cách chính
xác và trong một khoảng thời gian cho phép.
Tính tổng quát. Thuật toán phải áp dụng được cho tất cả các bài toán có dạng như
mong muốn, chứ không phải chỉ áp dụng được cho một số trường hợp đặc biệt nào đó.
Tính đúng: Thuật toán phải cho kết quả như mong muốn.
Trong các tính chất trên, 3 tính chất cơ bản của thuật toán đòi hỏi phải được thỏa mãn
là tính xác định, tính hữu hạn và tính đúng.
Các thuật toán trong hai ví dụ 1 và 2 được trình bày ở trên đều thỏa mãn các tính chất
nêu trên.
Dưới đây chúng ta xét thêm một số ví dụ về các thuật toán.
Ví dụ : Thuật toán tìm kiếm tuyến tính (Linear Search)
9
Bài toán được đặt ra là xác định xem một phần tử x có trong một dãy a
1
, a
2
, . . .,
a
n
hay không? Lời giải của bài toán này là giá trị chỉ vị trí (hay chỉ số) của một phần tử
trong dãy bằng phần tử x, hoặc là 0 nếu x không có trong dãy.
Một thuật toán đơn giản để giải bài toán này là thuật toán tìm kiếm tuyến tính
(hay còn gọi là tìm kiếm tuần tự). Thuật toán bắt đầu bằng việc so sánh x với a
1
, và
nếu x = a

Thuật toán:
1. i := 1
2. while ( i ≤ n and x ≠ a
i
) do
i := i + 1;
3. if i ≤ n then location := i
else location := 0
4. location là một lời giải (ví trí cần tìm).
Trong thuật toán nầy từ "location" là một biến nguyên.
10
Ghi chú : Trong trường hợp dãy a
1
, a
2
, . . ., a
n
có thứ tự thì ta có thể tìm kiếm theo
thuật toán tìm kiếm nhị phân (binary search). Ta có thể tham khảo thuật toán này trong
các sách về "cấu trúc dữ liệu và thuật toán".
1.1.4 Độ phức tạp của thuật toán
Mỗi thuật toán chỉ giải một lớp bài toán nào đó, nhưng có thể có nhiều thuật
toán khác nhau giải cùng một bài toán. Một vấn đề đặt ra là ta cần chọn một thuật toán
tốt để giải bài toán đã cho.
Nhưng thế nào là thuật toán tốt? Thước đo hiệu quả là thời gian máy tính sử
dụng để giải bài toán theo thuật toán đang xét khi các giá trị đầu vào có kích thước xác
định, và dung lượng bộ nhớ đòi hỏi để thực hiện thuật toán đó. Như vậy khi xem xét
đến độ phức tạp tính toán của thuật toán ta phải xem xét đến độ phức tạp thời gian và
độ phức tạp không gian.
Độ phức tạp không gian gắn liền với cấu trúc dữ liệu cụ thể được dùng để thực

có tên là BCPL do Martin Richards nghiên cứu ảnh hưởng của BCPL lên C gián tiếp
qua ngôn ngữ B, do Ken Thompson viết năm 1970 cho hệ UNIX chạy trên họ máy
tính PDP-7.
Ngoài việc C được dùng để viết hệ điều hành UNIX (hiện nay trên 90% chương
trình nguồn của các hệ điều hành UNIX được viết bằng C, chưa đầy 10% bằng hợp
ngữ), người ta nhanh chóng nhận ra sức mạnh của C trong việc xử lí các vấn đề hiện
đại của tin học: xử lí số, văn bản, cơ sở dữ liệu, lập trình hướnh đối tượng. Thực tế C
đã tổ hợp được các thành tựu tiên tiến của tin học và đã trở thành một chuẩn mực mặc
nhiên.
Liên quan đến sự hình thành và phát triển của ngôn ngữ, có một số sự kiện đánh
quan tâm sau:
- Năm 1978 cuốn giáo trình dạy lập trình bằng ngôn ngữ C với tên “The C
programming language” do chính hai tác giả của ngôn ngữ Brain W.Kemighan và
Dennism M.Ritchie biên soạn đã được xuất bản và được phổ biến rộng rãi.
- Năm 1983, một tiểu ban của viện tiêu chuẩn quốc gia Mỹ (ANSI được thành
lập nhằm đề xuất ra một chuẩn cho ngôn ngữ.
12
- Năm 1988, chuẩn ANSI C chính thức được ban hành. Chuẩn này bao gồm các
mô tả về ngôn ngữ theo K&R và quy định các thư viện chuẩn của ngôn ngữ C, nhờ đó
tăng tính khả chuyển của ngôn ngữ viết bằng C.
Trong thế giới PC, có các hệ chương trình dịch C nổi tiếng như là: Turbo C,
Borland C của Borland Inc.MSC, VC của Microsoft Corp.Lattice C của Lattice.
Sự phát triển của ngôn ngữ lập trình trong những năm 80 đã đưa đến phong
cách lập trình hướng đối tượng mà một trong những ngôn ngữ rất được ưa dùng là C+
+, bổ sung mới các yếu tố hướng đối tượng vào ngôn ngữ C.
1.2.2 Đặc điểm của ngôn ngữ lập trình C
Ngôn ngữ C có những đặc điểm cơ bản sau:
- Tính cô đọng (compact): C chỉ có 32 từ khóa chuẩn và 40 toán tử chuẩn,
nhưng hầu hết đều được biểu diễn bằng những chuỗi ký tự ngắn gọn.
- Tính cấu trúc (structured): C có một tập hợp những chỉ thị của lập trình như

thực dụng.
• Dùng ngôn ngữ tiền xử lý, tức là các câu lệnh tiền xử lý, cho các nhiệm vụ như
là định nghĩa các macro và hàm chứa nhiều tập tin mã nguồn (bằng cách dùng
câu lệnh tiền xử lý dạng #include chẳng hạn).
• Mức thấp của ngôn ngữ cho phép dùng tới bộ nhớ máy tính qua việc sử dụng
kiểu dữ liệu pointer.
• Số lượng từ khóa rất nhỏ gọn.
• Các tham số được đưa vào các hàm bằng giá trị, không bằng địa chỉ.
• Hàm các con trỏ cho phép hình thành một nền tảng ban đầu cho tính đóng và
tính đa hình.
• Hỗ trợ các bản ghi hay các kiểu dữ liệu kết hợp do người dùng từ khóa định
nghĩa struct cho phép các dữ liệu liên hệ nhau có thể được tập hợp lại và được
điều chỉnh như là toàn bộ.
14
• Là ngôn ngữ có cấu trúc modul, đó chính là việc sử dụng các chương trình con
loại hàm (function). Các hàm này có thể sử dụng được nhiều lần trong chương
trình hay chương trình khác
1.2.3.2Nhược điểm:
- Một số chức năng khác mà C không có (hay còn thiếu) nhưng có thể tìm thấy ở
các ngôn ngữ khác bao gồm:
• An toàn kiểu.
• Tự động Thu dọn rác.
• Các lớp hay các đối tượng cùng với các ứng xử của chúng
• Các hàm lồng nhau.
- Cú pháp của C thuộc loại là và khó học.
- Một số kí hiệu của C có nhiều nghĩa khác nhau, ví dụ kí hiệu
* là toán tử nhân, là toán tử không định hướng, là toán tử thay thế. Việc sử dụng
các kí hiệu này phụ thuộc vào ngữ cảnh sử dụng.
1.2.4 Các cặp lệnh sử lí
• Cấu trúc điều kiện if … else

break;
}
case constant_2:
{
Statements;
break;
}
16
case constant_n:
{
Statements;
break;
}
default:
{
Statements;
}
}
Cách hoạt động:
Biểu thức nguyên trong switch được tính toán và kiểm tra lần lượt với giá trị
của từng case label. Đầu tiên, nó sẽ được so sánh với giá trị của case label đầu tiên.
Nếu bằng nhau thì sẽ thực hiện các statement trong case label này cho đến khi nó gặp
được từ khoá break. Khi đó, cấu trúc switch…case kết thúc. Chương trình sẽ thực hiện
tiếp những dòng code sau cấu trúc switch…case. Ngược lại, nếu như giá trị biểu thức
nguyên không bằng giá trị case label đầu tiên thì nó sẽ tiếp tục so sánh đến giá trị của
case label thứ hai và tiếp tục thực hiện như những bước trên. Giả sử, đến cuối cùng
vẫn không tìm được giá trị bằng nó thì các khối codes trong default label sẽ được thực
hiện nếu như có tồn tại default label.
• Cấu trúc vòng lặp for:
Cú pháp:

ương tr ình thoát ra khỏi vòng lặp. Nếu giá trị của biểu thức 1 đúng thì quay lại bước
1.
18
19
CHƯƠNG 2: TÌM HIỂU THUẬT TOÁN SẮP XẾP CHÈN VÀ SẮP XẾP CHỌN
2.1 Giới thiệu thuật toán sắp xếp
2.1.1 Định nghĩa thuật toán sắp xếp
Thuật toán là một tập hợp hữu hạn của các chỉ thị hay phương cách được định
nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước; khi
các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán.
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 đó dựa trên nội dung thông tin lưu
giữ tại mỗi phần tử.
2.1.2 Phân loại thuật toán sắp xếp
• Sắp xếp ổn định :
Một thuật toán sắp xếp được gọi là sắp xếp ổn định nếu sau khi tiến hành sắp
xếp vị trí tương đối giữa các phần tử bằng nhau không bị thay đổi.
• Sắp xếp so sánh:
Một thuật toán sắp xếp được gọi là sắp xếp so sánh nếu trong quá trình thực
hiện thuật toán ta tiến hành so sánh các khoá và đổi chỗ các phần tử cho nhau. Đa
số các thuật toán sắp xếp dưới đây là sắp xếp so sánh, riêng sắp xếp đếm phân phối
không phải là sắp xếp so sánh.
2.1.3 Một số thuật toán sắp xếp cơ bản
• Sắp xếp nổi bọt:
Sắp xếp nổi bọt (bubble sort) là phương pháp sắp xếp đơn giản, dễ hiểu thường
được dạy trong khoa học máy tính. Giải thuật bắt đầu từ đầu của tập dữ liệu. Nó so
sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ
chúng cho nhau. Tiếp tục làm như vậy với cặp phần tử tiếp theo cho đến cuối tập hợp
dữ liệu. Sau đó nó quay lại với hai phần tử đầu cho đến khi không còn cần phải đổi
chỗ nữa.

thủ tục phân chia như sau: để chia một dãy ta chọn một phần tử được gọi là "chốt"
21
(pivot), chuyển tất cả các phần tử nhỏ hơn chốt về trước chốt, chuyển tất cả các phần
tử lớn hơn chốt về sau nó. Thủ tục này có thể thực hiện trong thời gian tuyến tính. Tiếp
tục phân chia các dãy con đó như trên cho đến khi các dãy con chỉ còn một phần tử.
Điểm khác biệt giữa sắp xếp nhanh và sắp xếp trộn là trong sắp xếp trộn việc xác định
thứ tự được xác định khi "trộn", tức là trong khâu tổng hợp lời giải sau khi các bài toán
con đã được giải, còn sắp xếp nhanh đã quan tâm đến thứ tự các phần tử khi phân chia
một danh sách thành hai danh sách con.
• Sắp xếp theo cơ số:
Sắp xếp theo cơ số (radix sort) dựa trên tính chất "số" của các khóa. Trong giải
thuật sắp xếp theo cơ số, ta không chỉ so sánh giá trị của các khóa, mà so sánh các
thành phần của khóa. Giả sử các khóa là các số biểu diễn theo hệ ghi số cơ số M. Khi
đó sắp xếp theo cơ số sẽ so sánh từng ký số của nó.
Chúng ta mô tả cách sắp này khi cơ số M=10. Giả sử phải sắp các hồ sơ đánh số bởi 3
chữ số thập phân. Đầu tiên ta chia các hồ sơ vào các đống có cùng chữ số hàng trăm
(đồng thới xếp các đống theo thứ tự của chữ số hàng trăm), trong mỗi đống con lại
phân chia theo chữ số hàng chục, cuối cùng trong mỗi đống có cùng chữ số hàng trăm
và hàng chục, sắp xếp theo thứ tự của chữ số hàng đơn vị.
Trong máy tính, đương nhiên việc sắp xếp theo cơ số nhị phân (cơ số 2) hoặc cơ số là
lũy thừa của 2 là thuận lợi nhất. Trong trường hợp cơ số 2, việc phân hoạch tương tự
như phân hoạch trong Quick Sort, chỉ khác ở chỗ cách chọn phần tử chốtmn
• Sắp xếp đếm phân phối:
Sắp xếp đếm phân phối là phương pháp sắp xếp có độ phức tạp tuyến tính trong
trường hợp các khóa nhận hữu hạn giá trị trong khoảng cho trước. Để đơn giản ta giả
sử các phần tử của danh sách a[1 n] nhận các giá trị tự nhiên trong khoảng [1 M].
Sắp xếp đếm phân phối đầu tiên đếm các phần tử thuộc danh sách nhận giá trị k với
. Các giá trị đếm được đươc ghi vào mảng Counter[1 M]. Sau đó khi
duyệt theo k từ 1 đến M, ta lần lượt xếp Counter[k] phần tử của vào danh sách a[1 n].
22

sắp xếp trực tiếp trên dãy số ban đầu – gọi là các thuật toán sắp xếp tại chỗ – lại được
đầu tư phát triển. Một trong số những giải thuật sắp xếp thường được sử dụng đó là
thuật toán sắp xếp chèn
2.2.2 Ý tưởng
Cho một tập hợp gồm n phần tử được lưu trữ trong một mảng A
Xem danh sách đầu tiên đã có thứ tự chỉ có một phần thử A[1]
Lần chèn 1: chèn A[2] vào danh sách tại vị trí sao cho danh sách có thứ
tự có hai phần tử là A[1] và A[2].
23
Lần chèn 2: chèn A[3] vào danh sách tại vị trí sao cho danhsách có thứ
tự gồm ba phần tử là A[1], A[2] và A[3]
Lần chèn thứ n-1: chèn A[n] vào danh sách sao cho danh sách có thứ tự có n
phần tử A[1], A[2], A[3], , A[n].
2.2.3 Các bước thực hiện:
- Bước 1: i = 2 (xem A[1] là dãy số có thứ tự vì nó chỉ có 1 phần tử)
- Bước 2: temp = A[i] (phải lưu A[i] ra biến tạm vì trong lúc hoán đổi vị trí sẽ
làm mất giá trị của A[i])
- Bước 3: j = i – 1
- Bước 4: Xét từ j về 1, tìm vị trí thích hợp để chèn temp vào mãng A
+ Nếu A[j]> temp thì A[j+i] = A[j]
- Nếu j > 1 thì j = j – 1; Lặp lại bước 4
- Ngược lại, A[j] = temp;
+ Ngược lại: A[j+1] = temp;
- Bước 5: Nếu i < n thì i = i + 1; Quay lại bước 2;
Ngược lại thì ta đã có mãng A[1 n] theo thứ tự tăng dần.
24
2.2.4 Lưu đồ thuật toán
25
Đúng
Đúng