Giáo án điện tử Khoa học máy tính 11 cánh diều Chủ đề F(CS) Bài 8: Lập trình một số thuật toán sắp xếp

CHÀO MỪNG CẢ LỚP ĐẾN VỚI BÀI HỌC MỚI!

KHỞI ĐỘNG

Trình quản lí tệp của hệ điều hành cho phép lựa chọn hiển thị nội dung của thư mục được sắp xếp thứ tự theo vài cách khác nhau. Em hãy cho biết một trong số các lựa chọn này và giải thích rõ thêm tiêu chí (yêu cầu) sắp xếp tương ứng.

Một số lựa chọn để sắp xếp

Ví dụ: Sắp xếp tên tệp theo thứ tự tăng dần.

Đầu vào:

Các tệp nằm trong thư mục.

Đầu ra:

Dãy các tệp được sắp xếp theo thứ tự bảng chữ cái tăng dần.

BÀI 8: LẬP TRÌNH MỘT SỐ THUẬT TOÁN SẮP XẾP

NỘI DUNG BÀI HỌC

Bài toán sắp xếp

Thuật toán sắp xếp nổi bọt (Bubble Sort)

Thuật toán sắp xếp chèn tuyến tính (Insertion Sort)

Thực hành

01

BÀI TOÁN SẮP XẾP

Một số bài toán sắp xếp với tiêu chí sắp xếp cụ thể:

Cho các dãy số, yêu cầu sắp xếp “theo thứ tự tăng dần (giảm dần)”.

Cho dãy các xâu kí tự, yêu cầu sắp xếp “theo thứ tự bảng chữ cái”, “theo độ dài tăng dần”,...

Sắp xếp các hàng trong một bảng gồm nhiều cột (hay bản ghi trong bảng CSDL) theo một cột nào đó. Ví dụ, có bảng kết quả học tập gồm các cột Họ và tên, Điểm Toán, Điểm Ngữ Văn, Điểm Tin học,... yêu cầu sắp xếp theo điểm môn Tin học giảm dần. Các hàng có trong bảng có dạng như sau:

Dựa vào các ví dụ vừa nêu, đọc hiểu mục 1 SGK và thực hiện yêu cầu:

Sắp xếp có nghĩa là gì?

Phân biệt sắp xếp tại chỗ và không tại chỗ.

Nghịch thế là gì? Nghịch thế có vai trò gì trong thuật toán sắp xếp.

Trong tin học, sắp xếp là tổ chức lại một tập hợp dữ liệu theo một tiêu chí sắp xếp, tức là đáp ứng một yêu cầu cụ thể về trình tự.

Phân biệt sắp xếp tại chỗ và sắp xếp không tại chỗ

Một thuật toán không dùng thêm một dãy khác ở bên ngoài dãy ban đầu để thực hiện sắp xếp được gọi là sắp xếp tại chỗ.

Nếu thuật toán sử dụng một dãy khác ở bên ngoài dãy ban đầu để chứa kết quả thì gọi là sắp xếp không tại chỗ.