Tin học 11 Cánh diều Chủ đề FCS Bài 8: Lập trình một số thuật toán sắp xếp

- Một số bài toán sắp xếp như sau:

 + Cho dãy các số, yêu cầu sắp xếp “theo thứ tự tăng dần (giảm dần)”.

 + Cho dãy các xâu kí tự, yêu cầu sắp xếp “theo thứ tự bảng chữ cái”, “theo độ dài tăng dần”,....

 + Sắp xếp các hàng trong bảng (hay bản ghi trong cơ sở dữ liệu) theo một cột nào đó. Ví dụ sắp xếp bảng kết quả học tập theo điểm môn Tin học giảm dần. Các hàng trong bảng có dạng như sau:

 

 

- Thuật ngữ sắp xếp trong tin học ám chỉ tổ chức tập hợp dữ liệu theo một tiêu chí nhất định để đáp ứng yêu cầu trình tự.

- Kết quả của sắp xếp là danh sách theo trình tự yêu cầu, giúp tìm kiếm nhanh chóng hơn.

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

- Trình bày bài toán sắp xếp đơn giản và minh hoạ bằng sắp xếp dãy số:

+ Đầu vào: Dãy n số \(a_{0}, a_{1},..., a_{n-1}\). 

+ Đầu ra: Dãy được sắ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ỗ

- Thuật toán sắp xếp tại chỗ chỉ đổi chỗ các phần tử trong dãy ban đầu, không dùng thêm dãy khác ở bên ngoài.

- Yêu cầu sắp xếp tại chỗ rất quan trọng khi dãy cần sắp xếp dài.

- Sắp xếp không tại chỗ là khi sử dụng dãy khác để chứa kết quả.

- Các thuật toán được trình bày trong bài học đều sắp xếp tại chỗ và dùng cấu trúc mảng, phải dịch chuyển khi thao tác chèn.

 

Nghịch thế

- Nếu \(i < j\) và \(a_{i} > a_{j}\) thì \((a_{i}, a_{j})\) là nghịch thế.

- Dãy chưa sắp đúng khi còn ít nhất một nghịch thế.

- Một số thuật toán sắp xếp giảm dần và triệt tiêu các nghịch thế trong dãy.

- Dãy sắp xếp khi không còn nghịch thế nào.

 

- Xét cặp phần tử liền kề, nếu nghịch thế thì đổi chỗ để loại bỏ nó.

- Lặp lại việc trên để soát hết dãy từ đầu đến cuối.

- Số lượng nghịch thế giảm sau một vòng lặp.

- Thực hiện nhiều vòng lặp để hết nghịch thế và sắp xếp dãy.

- Hình 1 trình bày diễn biến từng vòng lặp khi thực hiện thuật toán. 

- Kí hiệu thể hiện thao tác đổi chỗ khi có nghịch thế (cặp phần tử màu đỏ).

 

Hình 1. Diễn biến từng vòng lặp của thuật toán

 

- Ở vòng lặp 5, nếu không tìm ra nghịch thế nào thì không đổi chỗ, dãy đã sắp xếp đúng thứ tự.

- Dùng biến logic "có đổi chỗ" để biết khi nào hết nghịch thế và dãy được sắp xếp xong.

- Hình 2 là mã giả của thuật toán sắp xếp nổi bọt phiên bản thô nhất.

 

Hình 2. Mã giả của thuật toán sắp xếp nổi bọt

 

- Nhận xét:

+ Số lớn nhất trong dãy sẽ được chuyển đến vị trí cuối dãy sau vòng lặp 1.

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

 

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

 + Vì dãy con \(a_{0}\) 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_{1}\) với \(1 \le 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: Hình 3 minh hoạ diễn biến từng bước của thuật toán sắp xếp chèn tuyến tính.

 

Hình 3. Minh hoạ thuật toán sắp xếp 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. ak + 1← val; i ← i + 1; đến Bước 1

- Để "chèn \(a_i\) vào đúng chỗ của nó” trong dãy \(a_{0}, a_{1} ,..., a_{i-1}\) cần:

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

 + 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 \(a_{k+1}\)

- 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 trên 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.

 

Hình 4. Mã giả 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 (xem Hình 4). 

- Vòng lặp while lồng bên trong thực hiện đồng thời cùng lúc hai việc trên trong mỗi bước (xem Hình 4).

 

1.4. Thực hành

Nhiệm vụ 1. 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.

Nhiệm vụ 2. Em hãy viết chương trình Python thực hiện thuật toán sắp xếp nổi bọt.

Nhiệm vụ 3. 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.

Theo em, 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?

Hướng dẫn giải:

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

- Trong khi đó, thuật toán sắp xếp nổi bọt cần thực hiện nhiều phép so sánh hơn và có thể không hiệu quả khi sắp xếp mảng lớn. Nó hoạt động bằng cách so sánh các cặp phần tử liên tiếp trong mảng và đổi chỗ chúng nếu chúng không được sắp xếp đúng thứ tự. Vì vậy, trong nhiều trường hợp, thuật toán sắp xếp chèn được ưa chuộng hơn do hiệu quả và tính đơn giản của nó.

Học xong bài này, em sẽ:

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

Như vậy là các em đã xem qua bài giảng Bài 8 Chủ đề FCS SGK Tin học 11 Cánh diều Khoa học máy tính. Để củng cố kiến thức bài học mời các em tham gia bài tập trắc nghiệm Trắc nghiệm Tin học 11 Cánh diều Chủ đề FCS Bài 8.

Câu 4-10: Mời các em đăng nhập xem tiếp nội dung và thi thử Online để củng cố kiến thức về bài học này nhé!

Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 11 Cánh diều Chủ đề FCS Bài 8 để giúp các em nắm vững bài học và các phương pháp giải bài tập.

Khởi động trang 122 SGK Tin học 11 Cánh diều - CD

Nhiệm vụ 1 trang 125 SGK Tin học 11 Cánh diều - CD

Nhiệm vụ 2 trang 126 SGK Tin học 11 Cánh diều - CD

Nhiệm vụ 3 trang 126 SGK Tin học 11 Cánh diều - CD

Vận dụng trang 126 SGK Tin học 11 Cánh diều - CD

Câu hỏi trang 126 SGK Tin học 11 Cánh diều - CD

Trong quá trình học tập nếu có thắc mắc hay cần trợ giúp gì thì các em hãy comment ở mục Hỏi đáp, Cộng đồng Tin học của HOC247 sẽ hỗ trợ cho các em một cách nhanh chóng!

Chúc các em học tập tốt và luôn đạt thành tích cao trong học tập!