Sắp xếp trong

-

1

-

- 2 -

LỜI CẢM ƠN

Bốn năm học tại trường Đại Học Sư Phạm, các thầy cô đã trang bị cho em

kiến thức lẫn kỹ năng sống. Vì vậy em muốn gởi lời cảm ơn đến Ban Giám Hiệu

nhà trường, các thầy cô đã giúp em có một hành trang kiến thức khá vững vàng

cho tương lại.

Trải qua 4 tháng thực hiện, vận dụng những gì đã học được và cũng học

được thêm nhiều điều, giờ thì luận văn tốt nghiệp cũng đã hoàn thành. Để có

được kết quả này, đó không phải là công sức của một mình em làm ra, mà còn

có sự hỗ trợ hết mình từ gia đình, thầy cô và bạn bè.

Đầu tiên em xin gởi đến PGS.TSKH.Trần Quốc Chiến lời cảm ơn chân

thành nhất, thầy là giảng viên trực tiếp hướng dẫn em trong suốt quá trình

nghiên cứu và thực hiện đề tài này. Thầy đã tận tình hướng dẫn, cung cấp tài liệu

cần thiết để em và các bạn trong nhóm luận văn do thầy hướng dẫn có thể hoàn

thành luận văn một cách tốt nhất.

Kế đến em xin gởi đến những người thân yêu trong gia đình mình, những

người luôn ủng hộ em không chỉ trong thời gian qua mà còn cả những ngày

tháng sau này.

Và lời cảm ơn cuối cùng dành cho những người bạn đáng quý đã cùng em

vượt qua những khó khăn, luôn chia sẽ những kiến thức trong học tập, những

vui buồn trong cuộc sống. Cảm ơn các bạn!

Với lượng thời gian có hạn và điều kiện của một sinh viên, luận văn

không tránh khỏi những hạn chế và sai sót. Em kính mong nhận được lời góp ý

chân thành của quý thầy cô và bạn bè gần xa.

SVTH: LÊ PHƯỚC HUYỀN

- 3 -

MỤC LỤC

LỜI CẢM ƠN.........................................................................................................2

MỤC LỤC...............................................................................................................3

MỞ ĐẦU .................................................................................................................5

1. Lý do chọn đề tài ..............................................................................................5

2. Mục đích nghiên cứu ........................................................................................5

3. Nhiệm vụ nghiên cứu.......................................................................................6

4. Đối tượng và phạm vi nghiên cứu ....................................................................6

5. Phương pháp nghiên cứu ..................................................................................6

CHƯƠNG I THUẬT TOÁN VÀ ĐỘ PHỨC TẠP...........................................6

1.1 Khái niệm giải thuật........................................................................................7

1.2 Các đặc trưng của giải thuật ...........................................................................7

1.3 Ngôn ngữ giải thuật ........................................................................................7

1.4 Độ phức tạp tính toán của giải thuật...............................................................8

1.5 Biểu diễn thời gian chạy của thuật giải ..........................................................9

1.6 Xác định độ phức tạp tính toán của giải thuật ..............................................10

1.6.1 Qui tắc cộng ..........................................................................................10

1.6.2 Qui tắc nhân ..........................................................................................11

1.6.3 Qui tắc tổng quát để phân tích một chương trình.................................11

1.7 Phân tích các chương trình đệ quy................................................................11

1.7.1 Thành lập phương trình đệ quy.............................................................11

1.7.2 Giải phương trình đệ quy .......................................................................12

CHƯƠNG II PHƯƠNG PHÁP SẮP XẾP TRONG ........................................15

2.1 SELECTION SORT .....................................................................................15

2.2 INSERTION SORT......................................................................................17

2.3 BUBBLE SORT ...........................................................................................19

2.4 INTERCHANGE SORT ( đổi chỗ trực tiếp) ............................................21

2.5 SHELL SORT...............................................................................................23

2.6 QUICKSORT................................................................................................27

2.7 HEAPSORT ..................................................................................................36

- 4 -

2.8 BINSORT .....................................................................................................41

2.9 MERGE SORT .............................................................................................45

2.10 RADIXSORT..............................................................................................50

CHƯƠNG III CHƯƠNG TRÌNH MINH HỌA.............................................54

3.1 Tổng quan về phần mềm: .............................................................................54

3.2 Hướng phát triển của phần mềm: ................................................................56

KẾT LUẬN ...........................................................................................................57

TÀI LIỆU THAM KHẢO ...................................................................................57

- 5 -

MỞ ĐẦU

1. Lý do chọn đề tài

Nếu muốn lập trình được một phần mềm giúp ích cho cuộc sống thì ngoài

nắm vững về ngôn ngữ lập trình chúng ta cần phải nắm vững về thuật toán. Vì

vậy môn học CẤU TRÚC DỮ LIỆU và GIẢI THUẬT được xem là môn học

đóng vai trò nền tảng cơ bản đối với những ai bắt đầu bước vào thế giới lập

trình. Môn học giúp chúng ta hiểu rõ bản chất của các thuật toán biết được độ

phức tạp của của từng phương pháp nhờ đó chúng ta có thể lựa chọn cách lập

trình tốt nhất. Và sắp xếp các số liệu là một yêu cầu không thể thiếu đối với các

phần mềm do đó bất cứ lập trình viên nào cũng phải nắm vững kiến thức về lĩnh

vực này từ đó chọn được phương pháp sắp xếp phù hợp với người sử dụng và số

liệu nhập vào.

Vì vậy em chọn đề tài “ sắp xếp trong ” để đi sâu, nắm vững kiến thức

một cách sâu sắc có hệ thống.

2. Mục đích nghiên cứu

Đồ án này sẽ trình bày một số phương pháp sắp xếp trong. Mục đích là sau

khi nghiên cứu chúng ta sẽ nắm vững các phần sau của mỗi phương pháp:

Đánh giá

Minh họa

Chương

Trình Giải Thuật

Ý tưởng

PP Sắp xếp

- 6 -

3. Nhiệm vụ nghiên cứu

Nghiên cứu về ý tưởng, thuật toán, của từng phương pháp “ sắp xếp trong

”. Sau đó cài đặt chương trình minh hoạ cho đề tài.

Đánh giá về độ phức tạp của từng phương pháp “sắp xếp trong” và rút ra

ưu, khuyết điểm của từng phương pháp sắp xếp.

Qua đó chúng ta rút ra kết luận mỗi phương pháp sắp xếp trong nên dùng

trong từng bài toán nào.

4. Đối tượng và phạm vi nghiên cứu

Có rất nhiều phương pháp sắp xếp trong nhưng đề tài chỉ nghiên cứu các

phương pháp “ sắp xếp trong ” cơ bản sau đây:

1.Selection sort 2.Insertion sort

3.Shell sort 4.Heap sort

5.Interchange sort 6.Bubble sort

7.Quick sort 8.Merge sort

9.Binsort 10.Radixsort

5. Phương pháp nghiên cứu

-Thu thập, phân tích các tài liệu liên quan đến sắp xếp trong

-Phân tích bài toán, xây dựng chương trình đệ quy

-Tổng hợp kết quả.