Nội dung bài viết

    Xem thêm

    Lý thuyết Tin học 11 (Cánh diều) Bài 9: Lập trình thuật toán sắp xếp nhanh

    Tóm tắt lý thuyết Tin học lớp 11 Bài 9: Lập trình thuật toán sắp xếp nhanh 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,401 23/09/2023
    Trang trước
    Chia sẻ
    Trang sau  

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

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

    1. Lược đồ phân đoạn trong sắp xếp nhanh

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

    - Chiến lược chia để trị phân đoạn dãy đầu vào thành 2 đoạn con

    - Sắp xếp trong nội bộ 2 đoạn con

    - Chia 2 đoạn con thành các đoạn con nhỏ hơn

    - Lặp lại việc phân đoạn cho đến khi chỉ còn không quá 1 phần tử

    - Dãy ban đầu được sắp xếp xong.

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

    - Phân đoạn thành 2 đoạn con: bên trái nhỏ hơn hay bằng pivot, bên phải lớn hơn hay bằng pivot, pivot chuyển đến vị trí phân tách hai đoạn

    - Hàm trả về vị trí phân tách dãy thành hai đoạn con

    - Sắp xếp trong nội bộ hai đoạn con để hoàn thành việc sắp xếp dãy số.

    - Bài toán sắp xếp ban đầu chia thành 2 bài toán con nhỏ hơn.

    Lý thuyết Tin học 11 (Cánh diều) Bài 9: Lập trình thuật toán sắp xếp nhanh (ảnh 1)

    Có những lược đồ phân đoạn khác nhau để đạt mục đích trên.

    2. Thuật toán sắp xếp nhanh áp dụng phân đoạn Lomuto

    - Chọn pivot là phần tử cuối dãy số

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

    - Duyệt dãy số bằng chỉ số j khác và đảo giá trị các phần tử sao cho:

    - Các phần tử từ đầu đến i-1 nhỏ hơn hay bằng pivot

    - Các phần tử từ i+1 đến j lớn hơn pivot

    - Phần tử ở vị trí i bằng pivot.

    - Hình 2 là mã giả của thuật toán Lomuto phân đoạn dãy số a, lo là chỉ số đầu mút trái; hi là chỉ số đầu mút phải.

    Lý thuyết Tin học 11 (Cánh diều) Bài 9: Lập trình thuật toán sắp xếp nhanh (ảnh 1)

    3. Thuật toán sắp xếp nhanh áp dụng phân đoạn Hoare

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

    - Tác giả thuật toán sắp xếp nhanh là Hoare

    - Đổi chỗ nhảy qua điểm phân tách (pivot), rà soát từ hai phía, 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 để 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.

    Lý thuyết Tin học 11 (Cánh diều) Bài 9: Lập trình thuật toán sắp xếp nhanh (ảnh 1)

    - Hình 4 là mã giả của thuật toán sắp xếp nhanh áp dụng phân đoạn Hoare. Hình 5 là 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.

    Lý thuyết Tin học 11 (Cánh diều) Bài 9: Lập trình thuật toán sắp xếp nhanh (ảnh 1)

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

    Đ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 8: Lập trình một số thuật toán sắp xếp

    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,401 23/09/2023
    Trang trước
    Chia sẻ
    Trang sau  

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