Tin học 11 Cánh diều Chủ đề FCS Bài 9: Lập trình thuật toán sắp xếp nhanh

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.

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.

Kết quả phân đoạn: đoạn trái = \({i|lo \le i \le p -1}\), đoạn phải = \({j|p+1 \le j \le hi}\)

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

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

Hình 2. Mã giả thực hiện phân đoạn Lomuto

Mã lệnh Python thuật toán sắp xếp nhanh sử dụng phân đoạn Lomuto

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. Mã giả thực hiện phân đoạn Hoare

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

Hình 5. Mã lệnh thực hiện phân đoạn Hoare

Em hãy giải thích tại sao lại nói thuật toán sắp xếp nhanh (QuickSort) theo chiến lược “chia đề trị”?

Hướng dẫn giải:

- Thuật toán QuickSort được xây dựng theo chiến lược "chia để trị" bởi vì nó phân chia dãy số cần sắp xếp thành các phần nhỏ hơn, sau đó sắp xếp từng phần đó và kết hợp các phần đã sắp xếp lại thành dãy số đã được sắp xếp.

- Cụ thể, thuật toán QuickSort chia dãy số cần sắp xếp thành hai phần dựa trên một phần tử được gọi là pivot. Tất cả các phần tử nhỏ hơn pivot được đưa về bên trái pivot, còn các phần tử lớn hơn pivot được đưa về bên phải pivot. Sau đó, thuật toán đệ quy được áp dụng lên từng phần của dãy số này, cho đến khi các phần con chỉ còn duy nhất một phần tử. Cuối cùng, các phần đã sắp xếp lại với nhau để tạo ra dãy số đã được sắp xếp.

Vì vậy, chiến lược "chia để trị" của QuickSort cho phép thuật toán chia nhỏ vấn đề lớn hơn thành các vấn đề nhỏ hơn, giúp cho việc giải quyết các vấn đề này trở nên đơn giản và hiệu quả hơn."

Học xong bài này, em sẽ:

- Hiểu được ý tưởng của thuật toán sắp xếp nhanh.

- Viết được chương trình thực hiện sắp xếp nhanh một dãy số dựa trên các mã lệnh thuật toán phân đoạn cho trước.

Như vậy là các em đã xem qua bài giảng Bài 9 Chủ đề FCS SGK Tin học 11 Cánh diều Khoa học máy tính. Để củng cố kiến thức bài học mời các em tham gia bài tập trắc nghiệm Trắc nghiệm Tin học 11 Cánh diều Chủ đề FCS Bài 9.

Câu 4-10: Mời các em đăng nhập xem tiếp nội dung và thi thử Online để củng cố kiến thức về bài học này nhé!

Các em có thể xem thêm phần hướng dẫn Giải bài tập Tin học 11 Cánh diều Chủ đề FCS Bài 9 để giúp các em nắm vững bài học và các phương pháp giải bài tập.

Khởi động trang 127 SGK Tin học 11 Cánh diều - CD

Nhiệm vụ 1 trang 130 SGK Tin học 11 Cánh diều - CD

Nhiệm vụ 2 trang 130 SGK Tin học 11 Cánh diều - CD

Vận dụng trang 130 SGK Tin học 11 Cánh diều - CD

Câu hỏi 1 trang 130 SGK Tin học 11 Cánh diều - CD

Câu hỏi 2 trang 130 SGK Tin học 11 Cánh diều - CD

Trong quá trình học tập nếu có thắc mắc hay cần trợ giúp gì thì các em hãy comment ở mục Hỏi đáp, Cộng đồng Tin học của HOC247 sẽ hỗ trợ cho các em một cách nhanh chóng!

Chúc các em học tập tốt và luôn đạt thành tích cao trong học tập!