Lý thuyết Tin học 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 tắt Lý thuyết Tin học 11 Cánh Diều Bài 8: Lập trình một số thuật toán sắp xếp theo chương trình Sách mới ngắn gọn nhất. Tổng hợp lý thuyết Tin học 11 trọn bộ chi tiết, đầy đủ.

Bài 8: Lập trình một số thuật toán sắp xếp

- Soạn Tin học 11 Cánh Diều Bài 8

1. Bài 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ố 0, 0, 0, Y 

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

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

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

2. Thuật toán sắp xếp nổi bọt (Bubble Sort)

- 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 e thể hiện thao tác đổi chỗ khi có nghịch thế (cặp phần tử màu đỏ).

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

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

3. Thuật toán sắp xếp chèn tuyến tính (Insertion Sort)

- Ý 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 với 1 < i <n như sau:

* Xét dãy con a₀,…, a_i đã có thứ tự,

* Chèn a 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.

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

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

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

>>> Xem toàn bộ: 

- Lý thuyết Tin học 11 Cánh Diều

- Soạn Tin 11 Cánh Diều

- Sơ đồ tư duy Tin học 11 Cánh Diều

- Trắc nghiệm Tin 11 Cánh Diều

-------------------------------------------

Trên đây Toploigiai đã cùng các bạn Tóm tắt Lý thuyết Tin học 11 Cánh Diều Bài 8: Lập trình một số thuật toán sắp xếp theo chương trình Sách mới ngắn gọn nhất. Mời các bạn hãy click ngay vào trang chủ Top lời giải để tham khảo và chuẩn bị bài cho năm học mới Lớp 11 nhé. Chúc các bạn học tốt.