Bài 8. Lập trình một số thuật toán sắp xếp trang 122, 123, 124 SGK Tin học 11 Khoa học máy tính Cánh diều

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.

Phương pháp giải:

Dựa vào kiến thức đã học.

Lời giải chi tiết:

Một trong số các lựa chọn sắp xếp:

Sắp xếp nổi bọt:

=> Ưu điểm:

• Là thuật toán cơ bản, dễ hiểu, phù hợp cho người bắt đầu học về sắp xếp

• Đoạn code ngắn gọn, dễ nhớ.

HĐ

Dựa trên minh họa diễn biến từng bước của thuật toán sắp xếp nổi bọt được trình bày như ở Hình 1, em hãy nêu tóm tắt ý tưởng của thuật toán này.

Phương pháp giải:

Dựa vào kiến thức đã học.

Lời giải chi tiết:

Xét một mảng gồm 5 số nguyên: a1, a2, …, a5.

Với cách sắp xếp không giảm từ trái qua phải, mục đích của chúng ta là đưa dần các số lớn nhất về cuối dãy (ngoài cùng bên phải).

Bắt đầu từ vị trí số 1, xét lần lượt từng cặp 2 phần tử, nếu phần tử bên phải nhỏ hơn phần tử bên trái, ta sẽ thực hiện đổi chỗ 2 phần tử này, nếu không, xét tiếp cặp tiếp theo. Với cách làm như vậy, phần tử nhỏ hơn sẽ “nổi” lên, còn phần tử lớn hơn sẽ “chìm” dần và về bên phải.

Khi kết thúc vòng thứ nhất, ta sẽ đưa được phần tử lớn nhất về cuối dãy. Sang vòng thứ hai, ta tiếp tục bắt đầu ở vị trí đầu tiên như vậy và đưa được phần tử lớn thứ hai về vị trí thứ hai ở cuối dãy ...

NV1

Em hãy thực hiện các công việc sau:

a) Tính số lần lặp của vòng lặp bên trong của thuật toán sắp xếp chèn tuyến tính.

b) Tính số lần lặp của vòng lặp ngoài của thuật toán sắp xếp chèn tuyến tính.

c) Ước lượng độ phức tạp thời gian của thuật toán sắp xếp chèn tuyến tính.

Phương pháp giải:

Dựa vào kiến thức đã học và kỹ năng lập trình.

Lời giải chi tiết:

a) Tính số lần lặp của vòng lặp bên trong của thuật toán sắp xếp chèn tuyến tính, sử dụng vòng lặp:

for i in range (1, n):

val ai

k i – 1

b) Tính số lần lặp của vòng lặp ngoài của thuật toán sắp xếp chèn tuyến tính, sử dụng các câu lệnh:

while k >= 0 and ak > val:

ak+1 ak

k k-1

ak+1 val

c) Ước lượng độ phức tạp thời gian của thuật toán sắp xếp chèn tuyến tính:

Vòng lặp for bên ngoài kiểm soát việc thực hiện đúng n-1 bước.

Vòng lặp while lồng bên trong thực hiện đồng thời cùng lúc hai việc a) và b) theo cách dịch chuyển dần từng bước sang trái, từ vị trí i tới vị trí k+1.

NV2

Viết chương trình Python thực hiện thuật toán sắp xếp nổi bọt.

Phương pháp giải:

 Dựa vào kiến thức đã học và kỹ năng lập trình.

Lời giải chi tiết:

Chương trình:

NV3

Em hãy viết chương trình Python thực hiện thuật toán sắp xếp chèn tuyến tính dựa trên mã giả đã cho trong bài học.

Phương pháp giải:

Dựa vào kiến thức đã học và kỹ năng lập trình.

Lời giải chi tiết:

Tham khảo code C:

Vận dụng

Cho danh sách Bảng điểm là 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... Hãy viết chương trình sắp xếp Bảng điểm theo điểm môn Tin học giảm dần.

Gợi ý: Mỗi phân tử của Bảng điểm là một danh sách con, ứng với một học sinh. So sánh theo thành phần điểm Tin học của danh sách con để sắp xếp.

Phương pháp giải:

Dựa vào kiến thức đã học và kỹ năng lập trình.

Lời giải chi tiết:

Tham khảo code C:

Luyện tập

Trong hai thuật toán sắp xếp nổi bọt và thuật toán sắp xếp chèn, thuật toán nào đơn giản và để cài đặt hơn?

Phương pháp giải:

Dựa vào kiến thức đã học và kỹ năng lập trình.

Lời giải chi tiết:

Cả hai thuật toán sắp xếp nổi bọt và sắp xếp chèn đều đơn giản và dễ cài đặt. Tuy nhiên, thuật toán sắp xếp chèn có thể được coi là đơn giản hơn vì nó sử dụng ít phép so sánh hơn so với thuật toán sắp xếp nổi bọt.

Thuật toán sắp xếp chèn thực hiện việc chèn một phần tử vào một mảng đã được sắp xếp trước đó. Với mỗi phần tử trong mảng, nó sẽ so sánh nó với các phần tử đã được sắp xếp trước đó, và chèn phần tử đó vào vị trí thích hợp trong mảng. Điều này đòi hỏi ít phép so sánh hơn so với thuật toán sắp xếp nổi bọt, do đó thuật toán sắp xếp chèn có hiệu suất tốt hơn khi sắp xếp một mảng lớn.