Video giảng 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

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

Thông qua video này, các em sẽ nắm được các kiến thức và kĩ năng như sau:

• Phát biểu được bài toán sắp xếp.
• Viết được chương trình cho một vài thuật toán sắp xếp.

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

Trước khi bước vào bài học ngày hôm nay, các em suy nghĩ và trả lời: 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

Nội dung 1: Bài toán sắp xếp

Các em hãy 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.

Video trình bày nội dung:

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

Nội dung 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. 

Video trình bày nội dung:

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

Nội dung 3: Thuật toán sắp xếp chèn tuyến tính (Insertion Sort)

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

Video trình bày nội dung:

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

Nội dung 4: Thực hành 

Sau khi thực hiện nhiệm vụ 1,2,3 ta có kết luận sau ?

Video trình bày nội dung:

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

………..

Nội dung video Bài 8: Lập trình một số thuật toán sắp xếp còn nhiều phần rất hấp dẫn và thú vị. Hãy cùng đăng kí để tham gia học bài và củng cố kiến thức thông qua hoạt động luyện tập và vận dụng trong video.