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 11 Cánh Diều Bài 9: Lập trình thuật toán sắp xếp nhanh 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 9: Lập trình thuật toán sắp xếp nhanh

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

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.

>>> 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 9: Lập trình thuật toán sắp xếp nhanh 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.