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

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.

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.

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.

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

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