Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
TRƯỜNG ĐẠI HỌC ĐỒNG THÁP
KHOA CÔNG NGHỆ THÔNG TIN
ĐỒ ÁN CÔNG NGHỆ TIN HỌC
Đề tài : Cài đặt các giải thuật sắp xếp
Sinh viên thực hiện: Huỳnh Thị Minh Hằng
Lớp: CĐTin08A
Giáo viên hướng dẫn: Nguyễn Thị Mỹ Dung
Đồng Tháp, 2009
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 1
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
LỜI CẢM ƠN
Trước hết em xin chân thành cảm ơn các thầy cô giáo khoa Công
Nghệ Thông Tin trường Đại học Đồng Tháp đã trang bị cho em những
kiến thức cơ bản cần thiết trong thời gian qua để em có thể thực hiện tốt
đồ án này.
Em xin chân thành cảm ơn cô Nguyễn Thị Mỹ Dung đã tận tình
giúp đỡ và hướng dẫn em hoàn tất đồ án này. Ngoài ra tôi cũng xin cảm
ơn tất cả bạn bè đã giúp đỡ tôi trong suốt quá trình thực hiện đồ án.
Mặc dù đã rất cố gắng, nhưng trong khoảng thời gian cho phép
cũng như những hạn chế về kiến thức nên cuốn đồ án này của em không
thể tránh khỏi những thiếu sót. Chính vì vậy, em rất mong nhận được sự
góp ý của các thầy cô giáo cũng như bạn bè có quan tâm đến lĩnh vực
được trình bày trong cuốn đồ án này để em tích lũy thêm những kinh
nghiệm cho mình nhằm phát huy những kiến thức được học để ứng dụng
trong công tác sau này
Một lần nữa em xin chân thành cảm ơn !.
Sinh Viên Thực Hiện
Huỳnh Thị Minh Hằng
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 2
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp

Mục lục
TRƯỜNG ĐẠI HỌC ĐỒNG THÁP 1
ĐỒ ÁN CÔNG NGHỆ TIN HỌC 1
Đề tài : Cài đặt các giải thuật sắp xếp 1
Mục lục 3
PHẦN MỞ ĐẦU 4
1. Lý do chọn Đồ Án 4
2. Mục tiêu và nhiệm vụ 5
Đồ án này trong giới hạn kiến thức và thời gian, em chỉ tập trung nghiên
cứu các nội dung cơ bản sau 5
1.1Thuật toán (algorithm) 5
1.1.1.Khái niệm thuật toán 5
1.1.2.Các đặc trưng của thuật toán 5
Khái niệm giải thuật 5
Các đặc trưng của giải thuật 5
Một số giải thuật cơ bản 5
CHƯƠNG 2 : ỨNG DỤNG THUẬT TOÁN SẮP XẾP 5
3.1 CÁC THUẬT TOÁN SẮP XẾP ĐƠN GIẢN 5
3.1.1 Sắp xếp lựa chọn 5
3.1.2 Sắp xếp xen vào 5
3.1.3 Sắp xếp nổi bọt 5
Chương 1. TỔNG QUAN VỀ GIẢI THUẬT 6
1.1Thuật toán 6
1.1.1.Khái niệm thuật toán 6
1.1.2.Các đặc trưng của thuật toán 6
1.2GIẢI THUẬT 7
1.2.1. Khái niệm giải thuật 7
1.2.2. Các đặc trưng của giải thuật 8
1.2.3. Ngôn ngữ biểu diễn giải thuật 8
1.2.3.1. Ngôn ngữ tự nhiên 8

1.2.3.2. Ngôn ngữ sơ đồ (Lưu đồ) 8
1.3. Một số giải thuật cơ bản 11
1.3.1.Các cấu trúc suy luận cơ bản của giải thuật 12
1.3.1.1.Tuần tự (Sequential): 12
1.3.1.2.Cấu trúc lựa chọn (Selection) 12
1.3.1.3.Cấu trúc lặp (Repeating) 13
13
CHƯƠNG 2 : ỨNG DỤNG THUẬT TOÁN SẮP XẾP 13
2.2 CÁC THUẬT TOÁN SẮP XẾP CƠ BẢN 15
2.2.1 Phương pháp chọn trực tiếp 15
2.2.3 Phương pháp Nổi Bọt ( Bubble Sort ) 21
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 3
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
PHỤ LỤC DEMO
KẾT LUẬN
TÀI LIỆU THAM KHẢO
PHẦN MỞ ĐẦU
1. Lý do chọn Đồ Án
Ngày nay, với sự phát triển vượt bậc của khoa học kỹ thuật. Công
nghệ thông tin là một lĩnh vực nhiều ứng dụng thiết thực nhất trong mọi lĩnh
vực của cuộc sống và xã hội chúng ta, đặc biệt nó là công cụ hỗ trợ đắc lực
không thể thiếu trong công tác tổ chức, quản lý. Dễ dàng thấy rằng cơ sở dữ
liệu là một trong ứng dụng quan trọng của công tác tin học hoá với những ứng
dụng hữu ích cho mọi lĩnh vực của cuộc sống. Nhờ vào công tác tin học hoá
mà công tác quản lý, tổ chức sắp xếp dữ liệu tỏ ra có hiệu quả, nhanh chóng,
chính xác, lưu trữ gọn, bảo mật cao và dễ dàng. Chính vì lẽ đó mà cơ sở dữ
liệu như là một giải pháp hữu hiệu nhất cho mọi cơ quan, tổ chức có thể làm
việc 1 cách khoa học và đạt năng suất cao.
Trong 2 thập niên qua, với sự phát triển không ngừng của ngành công
nghệ thông tin, các ứng dụng của công nghệ thông tin ngày càng đi sâu vào

các lĩnh vực của cuộc sống. nó giữ một vai trò cực kỳ quan trọng, góp phần
giúp nhà quản lý thực hiện chức năng quản lý một cách khoa học, chính xác
và hiệu quả. Sự phát triển của các công nghệ phận mềm, trên các lĩnh vực như
đồ họa, ứng dụng văn phòng, tổ chức dữ liệu, thiết kế web .v.v Trong đó cấu
trúc dữ liệu và giải thuật là một bộ môn giúp cho nhà lập trình xây dựng ý
tưởng và thiết kế nên những phần mềm ứng dụng quan trọng, mà các giải
thuật sắp xếp là một trong những ứng dụng quan trọng của bộ môn cấu trúc dữ
liệu và giải thuật, nó giúp cho chúng ta có thể tổ chức sắp xếp dữ liệu theo
nhiều phương án khác nhau, thuận tiện cho việc truy xuất, kiểm tra, đối chiếu
dữ liệu, thế nên việc nghiên cứu các giải thuật sắp xếp để đưa vào ứng dụng
trong cuộc sống là một nhu cầu cấp thiết mà người lập trình phải tìm hiểu và
nghiên cứu. Chính vì thế mà em chọn đề tài “ Cài đặt các giải thuật sắp xếp”
làm đồ án của mình và dùng ngôn ngữ hỗ trợ cài đặt là Visual Basic để thiết
kế bản Demo.
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 4
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
2. Mục tiêu và nhiệm vụ
Đồ án này trong giới hạn kiến thức và thời gian, em chỉ tập trung nghiên cứu
các nội dung cơ bản sau
• Nghiên cứu tổng quan về giải thuật.
• Nghiên cứu các thuật toán sắp xếp
• Thiết kế các giải thuật sắp xếp.
• Hướng đến các kỹ thuật lập trình với mã nguồn mở và ngôn ngữ lập
trình C#
• Áp dụng kết quả nghiên cứu làm một demo cài đặt các giải thật sắp xếp
1. Cấu trúc Đồ Án
Chương 1. TỔNG QUAN VỀ GIẢI THUẬT
1.1 Thuật toán (algorithm)
1.1.1. Khái niệm thuật toán
1.1.2. Các đặc trưng của thuật toán

Khái niệm giải thuật
Các đặc trưng của giải thuật
Một số giải thuật cơ bản
CHƯƠNG 2 : ỨNG DỤNG THUẬT TOÁN SẮP XẾP
3.1 CÁC THUẬT TOÁN SẮP XẾP ĐƠN GIẢN
3.1.1 Sắp xếp lựa chọn
3.1.2 Sắp xếp xen vào
3.1.3 Sắp xếp nổi bọt
CHƯƠNG 3 : PHỤ LỤC BẢN DEMO
KẾT LUẬN
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 5
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
Chương 1. TỔNG QUAN VỀ GIẢI THUẬT
1.1 Thuật toán
1.1.1. Khái niệm thuật toán
Thuật ngữ “algorithm” (thuật toán hoặc còn gọi là giải thuật) được gọi
theo tên nhà toán học Ả rập thế kỷ IX al-Khowarizmi, người đã viết cuốn
sách về các chữ số Hindu – cơ sở của kí hiệu số thập phân hiện đại (xem [4],
trang 118). Xuất xứ ban đầu là từ algorism, được dùng để chỉ các quy tắc thực
hiện các phép tính số học trên các số thập phân. Sau đó, vào thế kỷ XVIII
algorism biến thành algorithm. Với sự quan tâm ngày càng tăng đối với máy
tính, khái niệm thuật toán đã được cho một ý nghĩa chung hơn, bao hàm cả các
thủ tục xác định để giải các bài toán, chứ không phải chỉ là thủ tục để thực
hiện các phép tính số học.
Thuật toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình
tự xác định sao cho sau khi thực hiện dãy các thao tác ấy, từ Input của bài toán
ta nhận được Output cần tìm.
Cũng có thế xem thuật toán như một công cụ để giải quyết một bài toán
cụ thể. Phát biểu bài toán sẽ chỉ định tổng quát mối quan hệ Input/Output cần
thiết. Thuật toán mô tả một thủ tục tính toán cụ thể để đạt được mối quan hệ

1.1.2. Các đặc trưng của thuật toán
Các thuật toán có một số tính chất chung, đó là:
• Đầu vào (Input): Một thuật toán có các giá trị đầu vào từ một tập
xác định.
• Đầu ra (Output): Từ mỗi tập giá trị đầu vào, thuật toán sẽ tạo ra
các giá trị đầu ra. Các giá trị đầu ra chính là nghiệm của bài toán.
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 6
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
• Tính xác định: Các bước của thuật toán phải được xác định một
cách chính xác.
• Tính đúng đắn: Một thuật toán phải cho các giá trị đầu ra đúng
đối với mỗi tập giá trị đầu vào.
• Tính hữu hạn: Một thuật toán phải tạo ra các giá trị đầu ra sau
một số hữu hạn (có thể rất lớn) các bước thực hiện đối với mỗi
tập đầu vào.
• Tính hiệu quả: Mỗi bước của thuật toán phải thực hiện được một
cách chính xác và trong một khoảng thời gian chấp nhận được.
• Tính tổng quát: Thuật toán cần phải áp dụng được cho mọi tập dữ
liệu đầu vào của bài toán, chứ không phải chỉ cho một tập đặc
biệt các giá trị đầu vào.
1.2 GIẢI THUẬT
1.2.1. Khái niệm giải thuật
Giải thuật là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác
định một dãy các thao tác trên những dữ liệu vào sao cho sau một số hữu hạn
bước thực hiện các thao tác đó ta thu được kết quả của bài toán.
Ví dụ 1: Giả sử có hai bình A và B đựng hai loại chất lỏng khác nhau, chẳng
hạn bình A đựng rượu, bình B đựng nước mắm. Giải thuật để hoán đổi (swap)
chất lỏng đựng trong hai bình đó là:
• Yêu cầu phải có thêm một bình thứ ba gọi là bình C.
• Bước 1: Đổ rượu từ bình A sang bình C.

• Bước 2: Đổ nước mắm từ bình B sang bình A.
• Bước 3: Đổ rượu từ bình C sang bình B.
Ví dụ 2: Một trong những giải thuật tìm ước chung lớn nhất của hai số a và b
là:
• Bước 1: Nhập vào hai số a và b.
• Bước 2: So sánh 2 số a,b chọn số nhỏ nhất gán cho UCLN.
• Bước 3: Nếu một trong hai số a hoặc b không chia hết cho UCLN thì
thực hiện bước 4, ngược lại (cả a và b đều chia hết cho UCLN) thì thực
hiện bước 5.
• Bước 4: Giảm UCLN một đơn vị và quay lại bước 3
• Bước 5: In UCLN - Kết thúc.
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 7
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
1.2.2. Các đặc trưng của giải thuật
• Tính kết thúc: Giải thuật phải dừng sau một số hữu hạn bước.
• Tính xác định: Các thao tác máy tính phải thực hiện được và các máy
tính khác nhau thực hiện cùng một bước của cùng một giải thuật phải
cho cùng một kết quả.
• Tính phổ dụng: Giải thuật phải "vét' hết các trường hợp và áp dụng cho
một loạt bài toán cùng loại.
• Tính hiệu quả: Một giải thuật được đánh giá là tốt nếu nó đạt hai tiêu
chuẩn sau:
- Thực hiện nhanh, tốn ít thời gian.
- Tiêu phí ít tài nguyên của máy, chẳng hạn tốn ít bộ nhớ.
Giải thuật tìm UCLN nêu trên đạt tính kết thúc bởi vì qua mỗi lần thực
hiện bước 4 thì UCLN sẽ giảm đi một đơn vị cho nên trong trường hợp xấu
nhất thì UCLN=1, giải thuật phải dừng. Các thao tác trình bày trong các bước,
máy tính đều có thể thực hiện được nên nó có tính xác định. Giải thuật này
cũng đạt tính phổ dụng vì nó được dùng để tìm UCLN cho hai số nguyeên
dương a và b bất kỳ. Tuy nhiên tính hiệu quả của giải thuật có thể chưa cao;

cụ thể là thời gian chạy máy có thể còn tốn nhiều hơn một số giải thuật khác
mà chúng ta sẽ có dịp trở lại trong phần lập trình C.
1.2.3. Ngôn ngữ biểu diễn giải thuật
Để biểu diễn giải thuật, cần phải có một tập hợp các ký hiệu dùng để biểu
diễn, mỗi ký hiệu biểu diễn cho một hành động nào đó. Tập hợp các ký hiệu
đó lại tạo thành ngôn ngữ biểu diễn giải thuật.
1.2.3.1. Ngôn ngữ tự nhiên
Ngôn ngữ tự nhiên là ngôn ngữ của chúng ta đang sử dụng, chúng ta có
thể sử dụng ngôn ngữ tự nhiên để mô tả giải thuật giống như các ví dụ ở trên.
Ví dụ: Ta có giải thuật giải phương trình bậc nhất dạng ax+b=0 như sau:
• Bước 1: Nhận giá trị của các tham số a, b
• Bước 2: Xét giá trị của a xem có bằng 0 hay không? Nếu a=0 thì làm
bước 3, nếu a khác không thì làm bước 4.
• Bước 3: (a bằng 0) Nếu b bằng 0 thì ta kết luận phương trình vô số
nghiệm, nếu b khác 0 thì ta kết luận phương trình vô nghiệm.
• Bước 4: ( a khác 0) Ta kết luận phương trình có nghiệm x=-b/a
1.2.3.2. Ngôn ngữ sơ đồ (Lưu đồ)
Lưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật toán.
Biểu diễn thuật toán bằng lưu đồ sẽ giúp người đọc theo dõi được sự phân cấp
các trường hợp và quá trình xử lý của thuật toán. Phương pháp lưu đồ thường
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 8
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
được dùng trong những thuật toán có tính rắc rối, khó theo dõi được quá trình
xử lý.
Ðể biểu diễn thuật toán theo sơ đồ khối, ta phải phân biệt hai loại thao tác.
Một thao tác là thao tác chọn lựa dựa theo một điều kiện nào đó. Chẳng hạn :
thao tác"nếu a = b thì thực hiện thao tác B2, ngược lại thực hiện B4" là thao
tác chọn lựa. Các thao tác còn lại không thuộc loại chọn lựa được xếp vào
loại hành động. Chẳng hạn, "Chọn một hộp bất kỳ và để lên dĩa cân còn
trống." là một thao tác thuộc loại hành động.

Thao tác chọn lựa (decision)
Thao tác chọn lựa được biểu diễn bằng một hình thoi, bên trong chứa biểu
thức điều kiện.
Thao tác xử lý (process)
Thao tác xử lý được biểu diễn bằng một hình chữ nhật, bên trong chứa nội
dung xử lý.
Ðường đi (route)
Khi dùng ngôn ngữ tự nhiên, ta mặc định hiểu rằng quá trình thực hiện
sẽ lần lượt đi từ bước trước đến bước sau (trừ khi có yêu cầu nhảy sang bước
khác). Trong ngôn ngữ lưu đồ, do thể hiện các bước bằng hình vẽ và có thể
đặt các hình vẽ này ở vị trí bất kỳ nên ta phải có phương pháp để thể hiện trình
tự thực hiện các thao tác.
Hai bước kế tiếp nhau được nối bằng một cung, trên cung có mũi tên để
chỉ hướng thực hiện. Chẳng hạn trong hình dưới, trình tự thực hiện sẽ là B1,
B2, B3.
ừ thao tác chọn lựa có thể có đến hai hướng đi, một hướng ứng với điều
kiện thỏa và một hướng ứng với điều kiện không thỏa. Do vậy, ta dùng hai
cung xuất phát từ các đỉnh hình thoi, trên mỗi cung có ký hiệu Ð/Ðúng/Y/Yes
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 9
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
để chỉ hướng đi ứng với điều kiện thỏa và ký hiệu S/Sai/N/No để chỉ hướng đi
ứng với điều kiện không thỏa.

Ðiểm cuối (terminator)
Ðiểm cuối là điểm khởi đầu và kết thúc của thuật toán, được biểu diễn
bằng hình ovan, bên trong có ghi chữ bắt đầu/start/begin hoặc kết thúc/end.
Ðiểm cuối chỉ có cung đi ra (điểm khởi đầu) hoặc cung đi vào (điểm kết thúc).
Xem lưu đồ thuật toán giải phương trình bậc hai ở trên để thấy cách sử dụng
của điểm cuối.
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 10

Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
(connector)
Ðiểm nối được dùng để nối các phần khác nhau của một lưu đồ lại với
nhau. Bên trong điểm nối, ta đặt một ký hiệu để biết sự liên hệ giữa các điểm
nối.
Ðiểm nối sang trang (off-page connector)
Tương tự như điểm nối, nhưng điểm nối sang trang được dùng khi lưu
đồ quá lớn, phải vẽ trên nhiều trang. Bên trong điểm nối sang trang ta cũng đặt
một ký hiệu để biết được sự liên hệ giữa điểm nối của các trang.
Ở trên chỉ là các ký hiệu cơ bản và thường được dùng nhất. Trong thực
tế, lưu đồ còn có nhiều ký hiệu khác nhưng thường chỉ dùng trong những lưu
đồ lớn và phức tạp
1.3. Một số giải thuật cơ bản
Ví dụ 1 : Viết chương trình cho phép nhập vào 2 giá trị a, b mang ý
nghĩa là các hệ số a, b của phương trình bậc nhất. Dựa vào các giá trị a, b đó
cho biết nghiệm của phương trình bậc nhất ax + b = 0.
Mô tả giải thuật bằng ngôn ngữ tự nhiên:
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 11
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
- Bước 1: Nhập 2 số a và b
- Bước 2: Nếu a = 0 thì thực hiện bước 3, ngược lại thực hiện bước 4
- Bước 3: Nếu b=0 thì thông báo phương trình vô số nghiệm và kết thúc
chương trình, ngược lại thông báo phương trình vô nghiệm và kết thúc chương
trình.
- Bước 4: Thông báo nghiệm của phương trình là –b/a và kết thúc.
BeginEnd
Nhập hai số a,ba=0 Đúng b=0 ĐúngSai SaiNghiệm x=-b/a PT vô nghiệm PT
vô định
Ví dụ 2: Viết chương trình cho phép nhập vào 1 số n, sau đó lần lượt
nhập vào n giá trị a1, a2,…,an. Hãy tìm và in ra giá trị lớn nhất trong n số a1,

a2, …, an.
Để giải quyết bài toán trên, chúng ta áp dụng phương pháp “thử và
sửa”. Ban đầu giả sử a1 là số lớn nhất (được lưu trong giá trị max); sau đó lần
lượt xét các ai còn lại, nếu ai nào lớn hơn giá trị max thi lúc đó max sẽ nhận
giá trị là ai. Sau khi đã xét hết các ai thì max chính là giá trị lớn nhất cần tìm.
Mô tả giải thuật bằng ngôn ngữ tự nhiên:
- Bước 1: Nhập số n
- Bước 2: Nhập số thứ nhất a1
- Bước 3: Gán max=a1
- Bước 4: Gán i=2
- Bước 5: Nếu i<=n thì thực hiện bước 6, ngược lại thực hiện bước 9
- Bước 6: Nhập ai
- Bước 7: Nếu max < ai thì gán max=ai.
- Bước 8: Tăng i lên một đơn vị và quay lại bước 5
- Bước 9: In max - kết thúc
1.3.1.Các cấu trúc suy luận cơ bản của giải thuật
Giải thuật được thiết kế theo ba cấu trúc suy luận cơ bản sau đây:
1.3.1.1.Tuần tự (Sequential):
Các công việc được thực hiện một cách tuần tự, công việc này nối tiếp công
việc kia.
1.3.1.2.Cấu trúc lựa chọn (Selection)
Lựa chọn một công việc để thực hiện căn cứ vào một điều kiện nào đó. Có
một số dạng như sau:
- Cấu trúc 1: Nếu < điều kiện> (đúng) thì thực hiện <công việc>
- Cấu trúc 2: Nếu < điều kiện> (đúng) thì thực hiện <công việc 1>, ngược lại
(điều kiện sai) thì thực hiện <công việc 2>
- Cấu trúc 3: Trường hợp < i> thực hiện <công việc i>
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 12
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
1.3.1.3.Cấu trúc lặp (Repeating)

Thực hiện lặp lại một công việc không hoặc nhiều lần căn cứ vào một điều
kiện nào đó. Có hai dạng như sau:
- Lặp xác định: là loại lặp mà khi viết chương trình, người lập trình đã xác
định được công việc sẽ lặp bao nhiêu lần.
- Lặp không xác định: là loại lặp mà khi viết chương trình người lập trình
chưa xác định được công việc sẽ lặp bao nhiêu lần. Số lần lặp sẽ được xác
định khi chương trình thực thi.
Trong một số trường hợp người ta cũng có thể dùng các cấu trúc này để diễn
tả một giải thuật.
.
.
.
.
.
CHƯƠNG 2 : ỨNG DỤNG THUẬT TOÁN SẮP XẾP
2.1 KHÁI NIỆM GIẢI THẬT SẮP XẾP
Sắp xếp là một quá trình biến đổi một danh sách các đối tượng thành
một danh sách thoả mãn một thứ tự xác định nào đó. Sắp xếp đóng vai trò
quan trọng trong tìm kiếm dữ liệu. Chẳng hạn, nếu danh sách đã được sắp xếp
theo thứ tự tăng dần (hoặc giảm dần), ta có thể sử dụng kỹ thuật tìm kiếm nhị
phân hiệu quả hơn nhiều tìm kiếm tuần tự… Trong thiết kế thuật toán, ta cũng
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 13
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
thường xuyên cần đến sắp xếp, nhiều thuật toán được thiết kế dựa trên ý tưởng
xử lý các đối tượng theo một thứ tự xác định.
Các thuật toán sắp xếp được chia làm 2 loại: sắp xếp trong và sắp xếp
ngoài. Sắp xếp trong được thực hiện khi mà các đối tượng cần sắp xếp được
lưu ở bộ nhớ trong của máy tính dưới dạng mảng. Do đó sắp xếp trong còn
được gọi là sắp xếp mảng. Khi các đối tượng cần sắp xếp quá lớn cần lưu ở bộ
nhớ ngoài dưới dạng file, ta cần sử dụng các phương pháp sắp xếp ngoài, hay

còn gọi là sắp xếp file. Trong chương này, chúng ta trình bày các thuật toán
sắp xếp đơn giản, các thuật toán này dòi hỏi thời gian O(n
2
) để sắp xếp mảng n
đối tượng. Sau đó chúng ta đưa ra các thuật toán phức tạp và tinh vi hơn,
nhưng hiệu quả hơn, chỉ cần thời gian O(nlogn).
Mảng cần được sắp xếp có thể là mảng số nguyên, mảng các số thực,
hoặc mảng các xâu ký tự. Trong trường hợp tổng quát, các đối tượng cần được
sắp xếp chứa một số thành phần dữ liệu, và ta cần sắp xếp mảng các đối tượng
đó theo một thành phần dữ liệu nào đó. Thành phần dữ liệu đó được gọi là
khoá sắp xếp. Chẳng hạn, ta có một mảng các đối tượng sinh viên, mỗi sinh
viên gồm các thành phần dữ liệu: tên, tuổi, chiều cao,…, và ta muốn sắp xếp
các sinh viên theo thứ tự chiều cao tăng, khi đó chiều cao là khoá sắp xếp.
Từ đây về sau, ta giả thiết rằng, mảng cần được sắp xếp là mảng các đối
tượng có kiểu Item, trong đó Item là cấu trúc sau:
struct Item
{
keyType key; // Khoá sắp xếp
// Các trường dữ liệu khác
};
Vấn đề sắp xếp bây giờ được phát biểu chính xác như sau. Cho mảng
A[0 n-1] chứa n Item, chúng ta cần sắp xếp lại các thành phần của mảng A
sao cho:
A[0].key <= A[1].key <= <= A[n-1].key
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 14
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
2.2 CÁC THUẬT TOÁN SẮP XẾP CƠ BẢN
Mục này trình bày các thuật toán sắp xếp đơn giản: sắp xếp lựa chọn
(selection sort), sắp xếp xen vào (insertion sort), và sắp xếp nổi bọt (bubble
sort). Thời gian chạy của các thuật toán này là O(n

2
), trong đó n là cỡ của
mảng.
2.2.1 Phương pháp chọn trực tiếp
• Giải thuật
Ta thấy rằng, nếu mảng có thứ tự, phần tử a
i
luôn là min(a
i
, a
i+1
, ., a
n-1
).
Ý tưởng của thuật toán chọn trực tiếp mô phỏng một trong những cách sắp
xếp tự nhiên nhất trong thực tế: 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 là đầu dãy hiện hành; sau đó không quan
tâm đến nó 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 đến khi dãy hiện
hành chỉ còn 1 phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật
toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị
trí đúng ở đầu dãy. Các bước tiến hành như sau :
• Bước 1 : i = 0 ; // Bắt đầu từ phần tử đầu tiên
• 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 : Hoán vị a[min] và a[i]
• Bước 4 : | Nếu i

< n-1 thì i = i+1 ( tăng i ) rồi lặp lại Bước 2
| Ngược lại: Dãy đã được sắp xếp. // n-1 phần tử đã nằm

đúng vị trí.
• Ví dụ
Cho dãy số a: 12 2 8 5 1 6 4 15
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 15
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp


• Cài đặt : Cài đặt thuật toán sắp xếp chọn trực tiếp thành hàm
SelectionSort
void SelectionSort(int a[],int N )
{
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 16
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
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]) //So sánh 2 phần tử kế cận với nhau
min = j; // ghi nhận vị trí phần tử hiện
nhỏ nhất
Hoanvi(a[min], a[i]);
}
}
• Ðánh giá giải thuật
Ðối với giải thuật chọn trực tiếp, có thể thấy rằng ở lượt thứ i, bao giờ
cũng cần (n-i) lần so sánh để xác định phần tử nhỏ nhất hiện hành. Số lượng
phép so sánh này không phụ thuộc vào tình trạng của dãy số ban đầu, do vậy
trong mọi trường hợp có thể kết luận :

Số lần so sánh =
Số lần hoán vị (một hoán vị bằng 3 phép gán) lại phụ thuộc vào tình trạng ban
đầu của dãy số, ta chỉ có thể ước lược trong từng trường hợp như sau :
Trường
hợp
Số lần so sánh Số phép gán
Tốt nhất n(n-1)/2 0
Xấu nhất n(n-1)/2 3n(n-1)/2
2.2.2 Phương pháp Chèn trực tiếp (Insertion sort )
• Giải thuật
Giả sử có một dãy a
1
, a
2
, ,a
n
trong đó i phần tử đầu tiên a
1
, a
2
, ,a
i-1
đã
có thứ tự. Ý tưởng chính của giải thuật sắp xếp bằng phương pháp chèn trực
tiếp là tìm cách chèn phần tử a
i
vào vị trí thích hợp của đoạn đã được sắp để
có dãy mới a
1
, a

2
, ,a
i
trở nên có thứ tự. Vị trí này chính là vị trí giữa hai
phần tử a
k-1
và a
k
thỏa a
k-1
? a
i
< a
k
(1?k?i).
Cho dãy ban đầu a
1
, a
2
, ,a
n
, ta có thể xem như đã có đoạn gồm một
phần tử a
1
đã được sắp, sau đó thêm a
2
vào đoạn a
1
sẽ có đoạn a
1

a
2
được sắp;
tiếp tục thêm a
3
vào đoạn a
1
a
2
để có đoạn a
1
a
2
a
3
được sắp; tiếp tục cho đến
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 17
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
khi thêm xong a
N
vào đoạn a
1
a
2
a
N-1


sẽ có dãy a
1

a
2
a
N
được sắp. Các bước
tiến hành như sau :
• Bước 1 : i = 2; // 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.
• Ví dụ
Cho dãy số a: 12 2 8 5 1 6 4 15

Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 18
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp

Dừng
• Cài đặt
Cài đặt thuật toán sắp xếp chèn trực tiếp thành hàm InsertionSort

void InsertionSort(int a[], 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(int 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
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 19
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
a[pos+1] = a[pos];
pos ;
}
a[pos+1] = x];// chèn x vào dãy
}
}
Nhận xét
Khi tìm vị trí thích hợp để chèn a[i] vào đoạn a[0] đến a[i-1], do đoạn
đã được sắp, nên có thể sử dụng giải thuật tìm nhị phân để thực hiện việc tìm
vị trí pos, khi đó có giải thuật sắp xếp chèn nhị phân :
void BInsertionSort(int a[], int N )
{ int l,r,m,i;
int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử.
for(int i=1 ; i<N ; i++)
{ x = a[i]; l = 1; r = i-1;
while(i<=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-1 ; j >=l ; j )
a[j+1] = a[j];// dời các phần tử sẽ đứng sau x
a[l] = x; // chèn x vào dãy
}
}
• Đánh giá giải thuật
Ðối với giải thuật chèn trực tiếp, các phép so sánh xảy ra trong mỗi vòng
lặp while tìm vị trí thích hợp pos, và mỗi lần xác định vị trí đang xét không
thích hợp, sẽ dời chỗ phần tử a[pos] tương ứng. Giải thuật thực hiện tất cả N-
1 vòng lặp while , do số lượng phép so sánh và dời chỗ này phụ thuộc vào tình
trạng của dãy số ban đầu, nên chỉ có thể ước lược trong từng trường hợp như
sau :
Trường
hợp
Số phép so sánh Số phép gán
Tốt nhất
Xấu nhất
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 20
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
2.2.3 Phương pháp Nổi Bọt ( Bubble Sort )
• Giải thuật
Ý tưởng chính của giải thuật là 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,
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ác bước tiến hành như sau :
• Bước 1 : i = 0; // lần xử lý
đầu tiên
• Bước 2 : j = N; //Duyệt từ

cuối dãy ngược về vị trí i
Trong khi j vẫn còn nhỏ hơn i ( j < i ) thì thực hiện:
| Nếu a[j]<a[j-1] : hoán vị a[j] với a[j-1] rồi
giảm j : j = j - 1
| Nếu không thì giảm j : 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.
Ví dụ Cho dãy số a: 12 2 8 5 1 6 4 15
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 21
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 22
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
• Cài đặt : Cài đặt thuật toán sắp xếp theo kiểu nổi bọt thành hàm
BubbleSort:
void BubleSort(int a[], int N )
{ int i, j;
for (i = 0 ; i<N-1 ; i++)
for (j =N-1; j >i ; j )
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 23
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
if(a[j]< a[j-1]) // nếu sai vị trí thì đổi chỗ
Hoanvi(a[j],a[j-1]);
}
• Ðánh giá giải thuật
Ðối với giải thuật 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, nhưng số lượng phép hoán vị thực
hiện tùy thuộc vào kết qủa so sánh, có thể ước lược trong từng trường hợp như
sau :
Trường

hợp
Số lần so sánh Số lần hoán vị
Tốt nhất


0
Xấu nhất
Nhận xét
BubbleSort có các khuyết điểm sau: không nhận diện được tình trạng
dãy đã có thứ tự hay có thứ tự từng phần. Các phần tử nhỏ được đưa về vị trí
đúng rất nhanh, trong khi các phần tử lớn lại được đưa về vị trí đúng rất chậm
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 24
Đồ Án CTDL và GT Cài đặt các thuật toán sắp xếp
KẾT LUẬN
Qua đồ án bản thân nhận thấy mỗi kiểu sắp xếp có ưu thế riêng của nó, việc
cài đặt các giải thuật sắp xếp phải mang tính hướng đối tượng. Tùy theo dữ
liệu là lớn, nhỏ, độ phức tạp của dữ liệu thế nào, mà ta dùng các kiểu sắp xếp
(Sort) khác nhau, để đạt hiệu quả mong muốn một cách tối ưu nhất.
Các thuật sắp xếp thông thường như là: Insertion, Selection, Bubble,
thường chỉ sử dụng cho các dữ liệu nhỏ.
QuickSort tương đối nhanh trong một số kiểu dữ liệu, trên thực tế nó
cũng không nhanh hơn nhiều so với các thuật sắp xếp thông thường là mấy.
HeapSort, MergeSort, đó là những giải thuật sắp xếp được đánh giá là
nhanh, nhưng chỉ đúng với các kiểu dữ liệu hợp lý với nó thôi.
Qua nghiên cứu từng thuật toán một ta có thể tạo ra một giải thuật sắp
xếp phù hợp nhất với dữ liệu của mình, làm sao cho dúng với đối tượng cần
sắp xếp.
Việc sử dụng ngôn ngữ lập trình nào để viết và xây dựng bản Demo là
do sự chủ động của người viết chương trình, để mục dích cuối cùng là xây
dựng chương trình sao cho dễ thực hiện, ít lỗi và phổ thông

Trong giới hạn kiến thức của mình, em nhân thấy đồ án của em thực
hiện còn nhiều yếu kém, sai sót, mong dược sự đóng góp chỉ bảo của quí thầy
cô để làm cơ sở giúp em rút kinh nghiệm, học hỏi và ứng dụng sau nay trong
công việc của mình.
Sinh viên thực hiện: Huỳnh Thị Minh Hằng Trang 25