Giáo án và PPT Khoa học máy tính 11 cánh diều Bài 8: Lập trình một số thuật toán sắp xếp

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 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.

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: 

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

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

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

Sản phẩm dự kiến:

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

Sản phẩm dự kiến:

- Ý 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)

Nêu kết luận về thuật toán sắp xếp chèn tuyến tính (Insertion Sort) ?

Sản phẩm dự kiến:

Ý 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 thực hiện nhiệm vụ 1,2,3 ta có kết luận sau ?

Sản phẩm dự kiến:

- 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. Ý tưởng sau đây minh họa thuật toán nào?

- 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ự.

A. Thuật toán sắp xếp nổi bọt.                     B. Thuật toán tìm kiếm nhị phân.

C. Thuật toán sắp xếp chèn tuyến tính.          D. Thuật toán tìm kiếm tuần tự.

Câu 2. Một cặp hai phần tử (a_i, a_j) gọi là nghịch thế nếu

A. i < j mà a_i > a_j.                                                            B. i > j mà a_i < a_j.

C. i > j mà a_i > a_j.                                         D. i < j mà a_i < a_j.

Câu 3. Ướ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 là 

A. O(n).                B. O(n²).               C. O(log₂n).          D. O(n!).

Câu 4. Thuật toán sắp xếp nổi bọt có bao nhiêu vòng lặp lồng nhau?

A. 2.                     B. 3.                     C. 4.                     D. 5.

Câu 5. Số lượng nghịch thế tối đa của một dãy A gồm n số nguyên phân biệt là

A. n – 1.                B. n.                     C. .                      D. .

Đá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 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.