MỤC LỤC 1

LỜI MỞ ĐẦU 2

A.VẤN ĐỀ, MỤC ĐÍCH VÀ PHẠM VI NGHIÊN CỨU CỦA ĐỀ TÀI 4

B. TÌM HIỂU VỀ BÀI TOÁN SẮP XẾP 5

C. NỘI DUNG CỦA CÁC PHƯƠNG PHÁP SẮP XẾP 7

I. Phương pháp chọn trực tiếp (Selection sort): 7

1. Giải thuật: 7

2. Đánh giá giải thuật: 9

3. Lưu đồ thuật toán : 9

II. Phương pháp chèn trực tiếp (Insert sort): 10

1. Giải thuật: 10

2. Đánh giá giải thuật : 11

3. Lưu đồ thuật toán: 12

Xem như dãy số cần sắp xếp đã được nhập vào sẵn: 12

III. Phương pháp sắp xếp nổi bọt (Bubble sort): 13

1. Giải thuật . 15

2. Đánh giá giải thuật : 15

3. Lưu đồ thuật toán: 16

IV. Phương pháp sắp xếp vun đống (Heap sort): 17

1. Định nghĩa heap : 17

2. Giải thuật Heapsort: 17

3. Đánh giá giải thuật : 20

V. Phương pháp sắp xếp nhanh (Quick sort): 22

1. Giải thuật : 22

2. Đánh giá giải thuật : 24

3. Lưu đồ thuật toán : 25

Xem như dãy số cần sắp xếp đã được nhập vào sẵn 25

VI. Phương pháp sắp xếp trộn (MergerSort): 26

2. Đánh giá giải thuật: 28

3. Lưu đồ thuật toán: 28

D. KẾT LUẬN. 34

HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH DEMO 31

TÀI LIỆU THAM KHẢO 35

PHIẾU NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN VÀ GIÁO VIÊN CHẤM 35

PHIẾU CHẤM ĐIỂM BÀI TẬP CHỦ ĐỀ LỚN 1 36

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í dụ như : tra cứu từ điển, tìm sách trong thư viện .) và muốn việc tìm kiếm 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 tìm kiếm, sắp xếp có ý nghĩa rất lớn trong việc 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ó nhiều giải thuật tìm kiếm và sắp xếp được xây dựng, mức độ hiệu quả của từng giải thuật còn phụ thuộc vào tính chất của cấu trúc dữ liệu cụ thể mà nó tác động đến mà ta lựa chọn phương pháp sắp xếp sao cho phù hợp. Trong khoa học máy tính và trong toán học, một thuật toán sắp xếp là một thuật toán sắp xếp các phần tử của một danh sách (hoặc một mảng theo thứ tự tăng dần hoặc giảm dần). Người ta thường xét trường hợp các phần tử cần sắp xếp là các số. Hầu hết các bài toán đều có nhiều thuật toán khác nhau để giải quyết chúng.

Nội dung giới thiệu trình bày dưới đây là những thuật toán sắp xếp thông dụng nhất và đó cũng là nội dung mà nhóm chúng em nghiên cứu trong bài tập chủ đề lớn 1 này là:

1. Phương pháp chọn trực tiếp (Selection sort);

2. Phương pháp chèn trực tiếp( Insertion sort);

3. Phương pháp sắp xếp nổi bọt( Bubble sort);

4.Phương pháp sắp xếp trộn ( Merge sort);

5.Phương pháp sắp xếp nhanh ( Quick sort);

6 Phương pháp sắp xếp kiểu vun đống ( Heap sort);

Ngoài ra còn có nhiều thuật toán sắp xếp khác nữa như: Phương pháp sắp xếp cải tiến ( Shellsort) Trong bài tập chủ đề lớn 1 này chúng ta sẽ được lần lượt tìm hiểu khảo sát từng thuật toán trên. Các thuật toán như Selection sort, Insertion sort, Bubble sort là những thuật toán đơn giản dễ cài đặt nhưng chi phí cao. Các thuật toán Merge sort, Quick sort, Heap sort, phức tạp hơn nhưng hiệu suất cao hơn nhóm thuật toán đầu. Các nhóm thuật toán trên đều có một điểm chung là đều được xây dựng dựa trên cơ sở so sánh giá trị của các phần tử trong mảng (hay so sánh các khóa tìm kiếm). Khi xây dựng một thuật toán sắp xếp cần chú ý tìm cách giảm thiểu những phép so sánh và đổi chổ không cần thiết để tăng hiệu quả của thuật toán.

Mặt dù nhóm chúng em đã rất cố gắng và nổ lực để làm bài tập chủ đề lớn này do kinh nghiệm còn hạn chế và kiến thức chúng em nắm chưa sâu nên chúng em biết sẽ không tránh khỏi những thiếu sót. Nhóm chúng em rất mong nhận được sự thông cảm và đóng góp của các Thầy, Cô để lần sau làm bài tập chủ đề được tốt hơn.

Hoàn thành bài tập chủ đề lớn 1 này là niềm vui của cả nhóm, nhóm chúng em rất là biết ơn Thầy Huỳnh Dương Trung Trực đã hướng dẫn chúng em tận tình trong suốt thời gian chúng em làm bài tập chủ đề. Một lần nữa nhóm chúng em xin gửi lời cám ơn chân thành nhất đến Thầy