Nội dung bài viết

    Xem thêm

    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 lớp 11 Bài 8: Lập trình một số thuật toán sắp xếp hay, chi tiết sách Cánh diều sẽ giúp học sinh nắm vững kiến thức trọng tâm, ôn luyện để học tốt Tin học 11.

    1 1,470 23/09/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Lý thuyết Tin học 11 Bài 8: Lập trình một số thuật toán sắp xếp

    A. Lý thuyết Lập trình một số thuật toán sắp xếp

    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:

    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 (ảnh 1)

    - 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à ai > aj thì (ai, aj) 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 đỏ).

    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 (ảnh 1)

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

    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 (ảnh 1)

    - 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

    * Xét dãy con a0,…, ai đã 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.

    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 (ảnh 1)

    - 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←ai; k←i-1;

    + Bước 2.

    if k≥0: 

    if ak >val: ak+1 ← ak; k ←k — 1; đến Bước 2

    + Bước 3. ak + 1← val; i ← i + 1; đến Bước 1

    - Để "chèn ai vào đúng chỗ của nó” trong dãy a0, a1 ..., ai-1 cần:

    + Tìm được chỗ đúng thứ tự của ai cho k đi từ i – 1 qua trái cho đến khi ak ≤ ai hoặc k=−1.

    + Lấy ai ra khỏi dãy; dịch chuyển dãy ak+1,…, ai-1 sang phải một vị trí để có chỗ trống tại ak+1; đưa ai vào ak+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.

    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 (ảnh 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).

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

    Đang cập nhật…

    Xem thêm các bài lý thuyết Tin học 11 sách Cánh diều hay, chi tiết tại:

    Lý thuyết Bài 6: Kiểm thử và sửa lỗi chương trình

    Lý thuyết Bài 7: Lập trình giải bài toán tìm kiếm

    Lý thuyết Bài 9: Lập trình thuật toán sắp xếp nhanh

    Lý thuyết Bài 10: Thiết kế và chương trình từ trên xuống và phương pháp Mô đun hóa

    Lý thuyết Bài 15: Cấu trúc dữ liệu danh sách liên kết và ứng dụng

    Tham khảo các loạt bài Tin học 11 khác:

    Bài viết cùng lớp mới nhất

    Xem thêm
    1 1,470 23/09/2023
    Trang trước
    Chia sẻ
    Trang sau  

    Xem thêm các chương trình khác: