Video giảng Khoa học máy tính 11 cánh diều bài 9 Lập trình thuật toán sắp xếp nhanh

Tóm lược nội dung

BÀI 9. LẬP TRÌNH THUẬT TOÁN SẮP XẾP NHANH

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:

• Hiểu được ý tưởng của thuật toán sắp xếp nhanh.
• Viết được chương trình thực hiện sắp xếp nhanh một dãy số dựa trên các mã lệnh thuật toán phân đoạn cho trước.

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: Nếu cần chọn một trong hai việc sau đây, em sẽ chọn làm việc nào? Vì sao?

1) Từ mô tả thuật toán bằng liệt kê các bước, viết chương trình Python thực hiện thuật toán.

2) Từ chương trình Python thực hiện thuật toán, viết lại ngắn gọn ý tưởng chính của thuật toán.

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

Nội dung 1: Lược đồ phân đoạn trong sắp xếp nhanh

Các em hãy trao đổi:

+ Trình bày về thuật toán sắp xếp nhanh (Quick Sort).

+ Quan sát Hình 1, hãy mô tả lược đồ phân đoạn dãy số.

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

Thuật toán sắp xếp nhanh (Quick Sort)

- Thuật toán theo chiến lược chia để trị, lặp lại nhiều lần việc phân đoạn dãy đầu vào thành hai đoạn con.

Lược đồ phân đoạn dãy số

- Lấy giá trị của một phần từ trong dãy làm pivot (giá trị chốt). Giá trị pivot có thể là bất cứ phần tử nào trong dãy. 

- Kết quả phân đoạn: 

+ Đoạn con ở nửa dãy bên trái chỉ gồm các phần tử nhỏ hơn hay bằng pivot.

+ Đoạn con ở nửa dãy bên phải chỉ gồm các phần tử lớn hơn hay bằng pivot.

+ Phần tử làm pivot được chuyển đến vị trí phân tách hai đoạn.

Hình 1. Kết quả phân đoạn: đoạn trái = {i|lo ≤ i ≤ p – 1}, đoạn phải = {j|p + 1 ≤ i ≤ hi}

- Hàm thực hiện phân đoạn cần trả về vị trí phân tách dãy thành hai đoạn con vì sau đó sẽ sắp xếp chỉ trong nội bộ hai đoạn con.

Nội dung 2: Thuật toán sắp xếp nhanh áp dụng phân đoạn Lomuto

Em hãy nêu kết luận về Thuật toán sắp xếp nhanh áp dụng phân đoạn Lomuto

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

- Mã giả của thuật toán Lomuto phân đoạn dãy số a, trong đó:

lo là chỉ số đầu mút trái

hi là chỉ số đầu mút phải

- Ý tưởng của thuật toán Lomuto: Chọn pivot là giá trị phần tử đứng cuối dãy số. 

+ Duy trì chỉ số i ở vị trí phân tách;

+ Duyệt dãy số bằng một chỉ số j khác và đảo giá trị các phần tử sao cho các phần tử từ vị trí i – 1 về đầu mút trái nhỏ hơn hay bằng pivot; các phần tử từ vị trí i + 1 đến j lớn hơn pivot, riêng phần tử ở vị trí i đúng bằng pivot.

- Mã lệnh Python thực hiện sắp xếp nhanh bằng phân đoạn Lomuto:

Nội dung 3: Thuật toán sắp xếp nhanh áp dụng phân đoạn Hoare

Em hãy trình bày:

+ Ý tưởng chính của thuật toán sắp xếp nhanh áp dụng phân đoạn Hoare là gì?

+ Trình bày mã giả thực hiện phân đoạn Hoare và mã lệnh Python tương ứng 

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

Lược đồ phân đoạn Hoare

- Ý tưởng của thuật toán: 

+ Đổi chỗ nhảy qua điểm phân tách (pivot), rà soát từ hai phía, trái và phải, cùng tiến dần từng bước vào giữa.

+ Tạm dừng khi phát hiện phần tử vi phạm yêu cầu phân đoạn ở mỗi phía và đổi chỗ chúng cho nhau.

+ Rà soát từ hai điểm tạm dừng đi vào giữa cho đến khi gặp nhau thì kết thúc việc phân đoạn.

+ Điểm gặp nhau là vị trí phân tách dãy thành hai đoạn con.

- Mã giả của thuật toán sắp xếp nanh áp dụng phân đoạn Hoare:

- Mã lệnh Python của thuật toán phân đoạn dãy số a, xuất phát với pivot là đầu dãy.

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

Em hãy nêu kết luận sau khi hoàn thành Nhiệm vụ 1,2,3 

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

- Thuật toán sắp xếp nhanh có thể áp dụng một trong hai lược đồ phân đoạn: theo Lomuto hoặc theo Hoare.

- Lược đồ Lomuto thực hiện phân đoạn bằng cách kiểm tra theo một chiều từ trái sang phải đổi chỗ và dịch chuyển dần vị trí phân tách hai dãy con cho đến khi thỏa mãn yêu cầu phân đoạn.

- Lược đồ Hoare thực hiện phân đoạn bằng cách kiểm tra theo hai chiều, từ hai đầu dây số tiến dần vào giữa, đổi chỗ để thoả mãn yêu cầu phân đoạn; kết thúc khi gặp nhau.

………..

Nội dung video Bài 9: Lập trình thuật toán sắp xếp nhanh 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.