Tìm hiểu về Thuật Toán Sắp Xếp

Nghiên cứu khoa học Mô phỏng thuật toán sắp xếp

NGHIÊN CỨU KHOA HỌC

Đề tài : Tìm hiểu về Thuật Toán Sắp Xếp

Sinh viên thực hiện:Nguyễn Hải Nam 1

Nghiên cứu khoa học Mô phỏng thuật toán sắp xếp

Mục lục

NGHIÊN CỨU KHOA HỌC ............................................................................ 1

Đề tài : Tìm hiểu về Thuật Toán Sắp Xếp ........................................................ 1

Mục lục ............................................................................................................... 2

PHẦN MỞ ĐẦU ................................................................................................ 4

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

2. Mục tiêu và nhiệm vụ ................................................................................ 5

Chương 1. MỘT SỐ KIẾN THỨC CƠ SỞ ..................................................... 6

Thuật toán ....................................................................................................... 6

Khái niệm thuật toán .................................................................................. 6

Các đặc trưng của thuật toán ..................................................................... 7

Chương 2. MÔ PHỎNG THUẬT TOÁN ..................................................... 10

Tổng quan về mô phỏng thuật toán ............................................................. 10

Khái niệm mô phỏng thuật toán .............................................................. 10

Lịch sử mô phỏng thuật toán .................................................................. 11

Tác dụng của mô phỏng thuật toán ......................................................... 14

Kiến trúc của hệ thống mô phỏng thuật toán .......................................... 18

Lựa chọn công cụ mô phỏng thuật toán .................................................. 20

Một số yêu cầu đối với mô phỏng thuật toán ............................................. 21

Mô tả đúng theo thuật toán ...................................................................... 21

Hệ thống mô phỏng phải được thực hiện theo từng bước ..................... 21

Mô phỏng thuật toán phải có tính động .................................................. 21

Phải tạo ra sự phân cấp cho người học ................................................... 22

Cấu trúc của mô phỏng thuật toán .......................................................... 22

Quy trình thiết kế nhiệm vụ mô phỏng thuật toán ...................................... 23

Nghiên cứu và phân tích giải thuật ......................................................... 23

Phân tích giải thuật thành nhiều bước, sau đó lần lượt mô phỏng từng

bước đó .................................................................................................... 26

Phân tích khả năng tổng hợp các bước đã phân tích thành giải thuật ... 27

Phân tích những khó khăn và thuận lợi với những người lần đầu tiên

biết đến giải thuật ..................................................................................... 27

Kết luận ........................................................................................................ 28

CHƯƠNG 3 : CHƯƠNG TRÌNH ỨNG DỤNG THUẬT TOÁN SẮP XẾP

.......................................................................................................................... 29

3.1 CÁC THUẬT TOÁN SẮP XẾP ĐƠN GIẢN ............................... 30

3.1.1 Sắp xếp lựa chọn ...................................................................... 30

3.1.2 Sắp xếp xen vào ......................................................................... 32

3.1.3 Sắp xếp nổi bọt ......................................................................... 33

3.2 SẮP XẾP HOÀ NHẬP .................................................................... 35

Sinh viên thực hiện:Nguyễn Hải Nam 2

Nghiên cứu khoa học Mô phỏng thuật toán sắp xếp

3.3 SẮP XẾP NHANH .......................................................................... 38

3.4 SẮP XẾP SỬ DỤNG CÂY THỨ TỰ BỘ PHẬN ........................ 45

Sinh viên thực hiện:Nguyễn Hải Nam 3

Nghiên cứu khoa học Mô phỏng thuật toán sắp xếp

PHẦN MỞ ĐẦU

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

Trong hai thập kỷ qua, mô phỏng thuật toán đã được các nhà sư phạm

của ngành công nghệ thông tin sử dụng như một công cụ có tính chất giúp

đỡ trong việc dạy các thuật toán đồ thị, các thuật toán sắp xếp, … khác nhau

bằng máy tính. Nguyên nhân của việc mô phỏng thuật toán được sử dụng

như một công cụ trợ giúp cho việc giảng dạy là do nó có thể cung cấp các

mô phỏng động bằng đồ họa của một thuật toán và các thay đổi trong cấu

trúc dữ liệu của nó trong suốt quá trình thực thi.

Như một phần của quá trình học thuật toán, những sinh viên ngành

công nghệ thông tin sẽ học về cấu trúc của một trình biên dịch (compiler)

trong một ngôn ngữ lập trình cho quá trình đó. Điều này sẽ chỉ ra cho chúng

ta từng nhiệm vụ của các giai đoạn khác nhau trong trình biên dịch.

Hiện nay, một số hệ thống mô phỏng thuật toán được phát triển sau

hai thập kỷ. Hầu hết các thuật toán được đề cập đến trong giai đoạn này đều

là các hệ thống phổ biến hơn và tinh vi hơn các hệ thống mà thực tế đang sử

dụng.

Mô phỏng thuật toán ngày càng trở nên hữu ích và trở thành một giáo

cụ trực quan rất quan trọng trong hầu hết các lĩnh vực, nhất là trong

môi trường giáo dục. Với các nhà sư phạm của ngành công nghệ

thông tin thì mô phỏng thuật toán có tác dụng như một tài liệu hướng

dẫn trong việc dạy các thuật toán bằng máy tính. Đặc biệt, nó giúp học

sinh và sinh viên hiểu cấu trúc dữ liệu và thuật toán nhanh hơn. Như

vậy, mô phỏng thuật toán góp phần to lớn vào việc ứng dụng CNTT

trong giảng dạy và góp phần vào sự phát triển nhanh chóng của hệ

thống elearning.

Sinh viên thực hiện:Nguyễn Hải Nam 4