Slide bài giảng 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

Tóm lược nội dung

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

HOẠT ĐỘNG KHỞI ĐỘNG

GV yêu cầu HS trả lời câu hỏi Khởi động tr.122 SGK:

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

NỘI DUNG BÀI HỌC GỒM

• 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
• Luyện tập
• Vận dụng

HOẠT ĐỘNG HÌNH THÀNH KIẾN THỨC

Hoạt động 1: Bài toán sắp xếp

GV yêu cầu học sinh trao đổi: 

Sắp xếp được hiểu là gì?

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

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

Nội dung gợi ý:

- Trong tin học, thuật ngữ sắp xếp đề cấp đến việc 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ự.

- Yêu cầu sắp xếp cần chỉ rõ cách so sánh hai mục dữ liệu để quyết định thứ tự.

Ví dụ: Bài toán sắp xếp đơn giản và minh họa bằng sắp xếp dãy số.

- Đầu vào: Dãy n số a₀, a₁ ,..., a_{n – 1}.

- Đầu ra: Dãy được sắp xếp theo thứ tự tăng dần (không giảm).

Sắp xếp tại chỗ và 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ỗ.

Nghịch thế 

- Nếu i < j mà a_i > a_j thì cặp hai phần tử (a_i, a_j) gọi là một nghịch thế.

- Một thuật toán sắp xếp dựa trên ý tưởng giảm dần và tiến đến triệt tiêu các nghịch thế trong dãy.

Hoạt động 2: Thuật toán sắp xếp nổi bọt (Bubble Sort)

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ư trong Hình 1, em hãy tóm tắt ý tưởng chính của thuật toán này.

Nội dung gợi ý:

- Ý tưởng sắp xếp nổi bọt (Bubble Sort):

+ Xét lần lượt các cặp phần tử liên tiếp: nếu a_i > a_i+1 thì đổi chỗ [a_i, a_i+1]. 

+ Lặp lại cho đến khi triệt tiêu hết các cặp nghịch thế. 

+ Có thể chứng minh sau vòng lặp 1 thì số lớn nhất trong dãy sẽ được chuyển đến vị trí cuối dãy, tức là phần tử a[n – 1] đã ở đúng vị trí. Như vậy vòng lặp 2 chỉ cần rà soát nghịch thế và đổi chỗ đến vị trí n – 2.

- Sau vòng lặp i thì phần tử a[n – i – 1] đã ở đúng vị trí.

- Mã giả của thuật toán sắp xếp nổi bọt:

Hoạt động 3: Thuật toán sắp xếp chèn tuyến tính (Insertion Sort)

Hãy nêu kết luận về thuật toán sắp xếp chèn (Insertion Sort) ?

Nội dung gợi ý:

Ý tưởng sắp xếp chèn tuyến tính:

- Vì dãy con a₀ chỉ có một phần tử, nên dãy con này có thứ tự.

- Lặp lại việc chèn a_i  với 1 ≤ i < n như sau:

Xét dãy con a₀,..., a_{i – 1} đã có thứ tự, ta chèn a_i vào dãy con này sao cho dãy con sau khi chèn sẽ có thứ tự.

Mô tả thuật toán chèn tuyến tính: 

Mô tả các bước của thuật toán như sau:

Bước 0. i ← 1;

Bước 1. 

      if i ≥ n: kết thúc;

     else: val ← a_i; k ← i – 1;

Bước 2. 

     if k ≥ 0:

           if a_k > val: a_{k + 1} ← a_k; k ← k – 1; đến Bước 2;

Bước 3. a_{k + 1} ← val; i ← i + 1; đến Bước 1;

Để “chèn a_i vào đúng chỗ của nó” trong dãy a₀, a₁ ,..., a_{i – 1} cần:

a) Tìm được chỗ đúng thứ tự của a_i : Cho k đi từ i – 1 qua trái cho đến khi a_k ≤ a_i hoặc k = – 1.

b) Lấy a_i  ra khỏi dãy; dịch chuyển dãy a_{k + 1} ,..., a_{i – 1} sang phải một vị trí để có chỗ trống tại a_{k + 1}; đưa a_i vào chỗ trống đó.

Mã giả thuật toán sắp xếp chèn tuyến tính

Thuật toán sắp xếp chèn tuyến tính kết hợp làm đồng thời 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.

- 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) trong mỗi bước.

Hoạt động 4: Thực hành 

Sau khi hoàn thành nhiệm vụ 1, 2, 3, chúng ta có thể rút ra kết luận nào?

Nội dung gợi ý:

- Thuật toán sắp xếp nổi bọt có hai vòng lặp lồng nhau; vòng lặp trong thực hiện đổi chỗ một lượt các cặp phần tử là nghịch thế, vòng lặp ngoài kiểm tra điều kiện “không xảy ra đổi chỗ”.

- Việc tìm vị trí chèn đúng chỗ trong thuật toán sắp xếp chèn có thể thực hiện bằng cách dịch dần từng bước.

HOẠT ĐỘNG LUYỆN TẬP

Câu 1: Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách nào?

A. Thay thế.

B. Thay đổi.

C. Hoán đổi.

D. Cả A, B và C.

Câu 2: Thuật toán sắp xếp nổi bọt sắp xếp danh sách bằng cách hoán đổi các phần tử liền kề bao nhiêu lần?

A. Một lần.

B. Hai lần.

C. Mười lần.

D. Nhiều lần.

Câu 3: Trong thuật toán sắp xếp nổi bọt, ta thực hiện hoán đổi giá trị các phần tử liền kề khi nào?

A. Giá trị của chúng tăng.

B. Giá trị của chúng giảm.

C. Giá trị của chúng không đúng thứ tự.

D. Giá trị của chúng không bằng nhau.

Câu 4: Trong thuật toán sắp xếp nổi bọt thì dấu hiệu để biết dãy chưa sắp xếp xong là gì?

A. Vẫn còn cặp phần tử liền kế không đúng thứ tự mong muốn. 

B. Dãy chưa được sắp xếp tăng dần.

C. Dãy chưa được sắp xếp giảm dần.

D. Cả A, B và C.

Câu 5: Cho dãy số: 15, 1, 31, 9, 78, 42. Nếu sử dụng thuật toán sắp xếp nổi bọt để sắp xếp dãy trên tăng dần thì sau bao nhiêu lượt đổi chỗ thì thuật toán kết thúc?

A. 2 

B. 3

C. 4

D. 5

Đáp án gợi ý:

HOẠT ĐỘNG VẬN DỤNG

GV yêu cầu HS hoạt động nhóm đôi hoàn thành Vận dụng SGK trang 126: 

Cho danh sách Bảng điểm là kết quả học tập bao 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 theo thứ tự giảm dần.