ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN
SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 1
LỜI NÓI ĐẦU
Trong những năm qua, vấn đề công nghệ thông tin đang được quan tâm rất nhiều,
song song đó là sự phát triển của máy vi tính với nhiều ứng dụng rộng rãi trong mọi
lĩnh vực của cuộc sống .Nó hỗ trợ cho nhân viên làm việc ở văn phòng cho đến những
nhà khoa học làm việc trong các phòng thí nghiệm.
Cấu trúc dữ liệu và giải thuật là môn học nền tảng của ngành CNTT. Các cấu trúc
dữ liệu luôn gắn liền với các ứng dụng trong thực tế. Vì vậy khi được giao làm đề tài “
Tìm hiểu về thuật toán RadixSort ” dưới sự hướng dẫn của thầy giáo Lưu Văn
Hiền.Việc làm đồ án giúp cho em hiểu biết thêm về các giải thuật tác động lên dữ liệu
cũng như cách tổ chức , sắp xếp dữ liệu để giải quyết các bài toán sao cho dễ nhất, tối
ưu nhất.
Em xin chân thành cảm ơn sự giúp đỡ và hướng dẫn của thầy để em hoàn thành đồ
án này. Tuy nhiên, trong khi thực hiện sẽ không tránh khỏi được sai sót, mong các thầy
cô góp ý cho em sửa chữa để có thể thực hiện tốt hơn với các đồ án sau.
Em xin chân thành cám ơn!
Đà Nẵng, ngày 01 tháng 10 năm 2008
SVTH
Củng Công Minh
ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN
SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 2
MỤC LỤC
LỜI NÓI ĐẦU
Phần 1: Tổng quan về thuật toán
RadixSort……………4
1. Giới thiệu thuật toán : ………………………………………………..4
2. Ý tưởng thuật toán :…………………………………………………..4
3. Ví dụ minh họa về thuật toán : …………………………………….…5
4. Giải thích: ……………………………………………….………11
Phần 2: Trình bày về cấu trúc dữ liệu Queue …………...11
1. Định nghĩa: …………………………………………………………11
2. Ví dụ : ................................................................................................11
3. Một số ứng dụng của cấu trúc hàng đợi : …………………………...13
4. Một số thao tác phép toán trên hàng đợi: …………………...............13
5.Cài đặt hàng: …………………………………………………………13
5.1 Cài đặt hàng bằng mảng : ……………………………………….15
5.1.1 Phương pháp di chuyển tịnh tiến khi hàng bị tràn : ………..15
Tạo hàng rỗng CREATE_QUEUE(Q)
Kiểm tra hàng rỗng EMPTY_QUEUE
Kiểm tra hàng đầy FULL_QUEUE(Q)
Xóa 1 phần tử của hàng REMOVE(Q)
Thêm 1 phần tử vào hàng ADD(x,Q)
Xác định giá trị của phần tử đầu tiên của hàng FRONT(Q)
ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN
SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 3
5.1.2 Phương pháp mảng xoay vòng : ……………………………....15
Xóa 1 phần tử của hàng REMOVE(Q)
Kiểm tra hàng đầy FULL_QUEUE(Q)
Thêm 1 phần tử vào hàng ADD(x,Q)
5.2 Cài đặt hàng bằng danh sách liên kết(dùng con trỏ) ………………....16
Khởi tạo hàng rỗng CREATE_QUEUE(Q)
Kiểm tra hàng rỗng EMPTY_QUEUE
Thêm 1 phần tử vào hàng ADD(x,Q)
Xóa 1 phần tử của hàng REMOVE(Q)
Xác định giá trị của phần tử đầu tiên của hàng FRONT(Q)
Phần 3: Tìm hiểu những thành phần liên quan của ngôn
ngữ VB để cài đặt thuật toán.
Một số đối tượng trong ngôn ngữ Visual Basic .
Công cụ lưới VSFlex Grid 6.0 và cách thức làm việc với lưới này.
Phần 4: Lưu đồ thuật toán
Phần 5: Cài đặt …………………………………………..18
Màn hình mô phỏng từng bước chạy của thuật toán RadixSort
TÀI LIỆU THAM KHẢO ……………………………………………..19
NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN …………...…………20
NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN ………………………...21
ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN
SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 4
Phần 1: Tổng quan về thuật toán RadixSort
1. Giới thiệu thuật toán :
Khác với các thuật toán trước, Radix sort là một thuật toán tiếp cận theo một hướng
hoàn toàn khác. Nếu như trong các thuật toán khác, cơ sở để sắp xếp luôn là việc so
sánh giá trị của 2 phần tử thì Radix sort lại dựa trên nguyên tắc phân loại thư của bưu
điện. Vì lý do đó nó còn có tên là Postman?s sort. Nó không hề quan tâm đến việc so
sánh giá trị của phần tử và bản thân việc phân loại và trình tự phân loại sẽ tạo ra thứ tự
cho các phần tử.
Ta biết rằng, để chuyển một khối lượng thư lớn đến tay người nhận ở nhiều địa
phương khác nhau, bưư điện thường tổ chức một hệ thống phân loại thư phân cấp.
Trước tiên, các thư đến cùng một tỉnh, thành phố sẽ được sắp chung vào một lô để gửi
đến tỉnh thành tương ứng. Bưu điện các tỉnh thành này lại thực hiện công việc tương
tự. Các thư đến cùng một quận, huyện sẽ được xếp vào chung một lô và gửi đến quận,
huyện tương ứng. Cứ như vậy, các bức thư sẽ được trao đến tay người nhận một cách
có hệ thông mà công việc sằp xếp thư không quá nặng nhọc.
2. Ý tưởng thuật toán :
Coi các phần tử trong mảng sắp xếp được cấu thành từng các lớp có độ ưu tiên khác
nhau. Ví dụ, các số tự nhiên chia thành các lớp như: hàng đơn vị, hàng chục, hàng
trăm, hàng nghìn,..
Bước đầu tiên ta sắp xếp dãy các phần tử bằng cách so sánh các phần tử ở lớp có độ ưu
tiên thấp nhất (ví dụ các chữ số hàng đơn vị). Số nào có hàng đơn vị thấp hơn thì ta
đưa lên trên. Như vậy các số có hàng đơn vị là 0 ở trên cùng, sau đó đến các số có
hàng đơn vị là 1,…
Sau bước 1, ta thu được 1 thứ tự sắp xếp mới. Ta lại làm tương tự với các lớp kế
tiếp(chữ số thuộc hàng chục, hàng trăm,…) cuối cùng ta sẽ có dãy đã sắp xếp.
ĐỒ ÁN CƠ SỞ GVHD: LƯU VĂN HIỀN
SVTH : CỦNG CÔNG MINH ĐỀ TÀI: RADIXSORT 5
3. Ví dụ minh họa về thuật toán :
Cho dãy như sau:
{701, 1725, 999, 9170, 3252, 4518, 7009, 1424, 428, 1239, 8425, 7013}
Ta viết theo dạng cột để quan sát:
Dãy ban đầu
Sắp xếp theo
hàng đơn vị
Sắp xếp theo
hàng chục
Sắp xếp theo
hàng trăm
Sắp xếp theo hàng
nghìn
0 7 0 1 9 1 7
0
0 7
0
1 7
0 9
0
4 2 8
1 7 2 5 0 7 0
1
7 0
0
9 7
1 3
0
7 0 1
0 9 9 9 3 2 5
2
7 0
1
3 9
7 0
0
9 9 9
9 1 7 0 7 0 1
3
4 5
1
8 1
3 9
1
2 3 9
3 2 5 2 1 4 2
4
1 4
2
4 3
5 2
1
4 2 4
4 5 1 8 1 7 2
5
1 7
2
5 1
4
2 4
1
7 2 5
7 0 0 9 8 4 2
5
8 4
2
5 8
2 5
3
2 5 2
1 4 2 4 4 5 1
8
0 4
2
8 0
2 8
4
5 1 8
0 4 2 8 0 4 2
8
1 2
3
9 4
1 8
7
0 0 9
1 2 3 9 0 9 9
9
3 2
5
2 0
0 1
7
0 1 3
8 4 2 5 7 0 0
9
9 1
7
0 1
2 5
8
4 2 5
7 0 1 3 1 2 3
9
0 9
9
9 0
9 9
9
1 7 0