Theo em thì diễn biến từng bước sắp xếp nhanh một dãy số cụ thế dùng phân đoạn Lomuto sẽ giống hay sẽ khác với dùng phân đoạn Hoare?

Cùng Toploigiai Trả lời câu hỏi trang 130 (Theo em thì diễn biến từng bước sắp xếp nhanh một dãy số cụ thế dùng phân đoạn Lomuto sẽ giống hay sẽ khác với dùng phân đoạn Hoare?) Bài 9: Lập trình thuật toán sắp xếp nhanh SGK Tin 11 Cánh Diều.

Câu hỏi: Theo em thì diễn biến từng bước sắp xếp nhanh một dãy số cụ thế dùng phân đoạn Lomuto sẽ giống hay sẽ khác với dùng phân đoạn Hoare?

Trả lời ngắn gọn: 

Diễn biến từng bước sắp xếp nhanh một dãy số cụ thể dùng phân đoạn Lomuto sẽ khác với dùng phân đoạn Hoare. Tuy nhiên cả hai phương pháp đều áp dụng chiến lược chia để trị và đều sử dụng phương pháp đệ quy.

Trả lời chi tiết:

Diễn biến từng bước sắp xếp nhanh một dãy số cụ thể dùng phân đoạn Lomuto sẽ khác với dùng phân đoạn Hoare. Sự khác biệt giữa phương pháp phân đoạn Lomuto và phân đoạn Hoare trong thuật toán QuickSort là ở việc chọn pivot, cách phân đoạn và cách sắp xếp các phần tử. 

Cụ thể, phương pháp phân đoạn Lomuto sẽ chọn pivot là phần tử cuối cùng của mảng, phân đoạn theo pivot và sau đó đưa pivot về giữa hai phân đoạn, tiếp tục thực hiện thuật toán QuickSort trên hai phân đoạn trái và phải của pivot. Trong khi đó, phương pháp phân đoạn Hoare sẽ chọn pivot là phần tử ở giữa mảng, đưa hai con trỏ từ đầu và cuối mảng trỏ tới nhau và dịch chuyển chúng sao cho phần tử bên trái pivot lớn hơn pivot, phần tử bên phải pivot nhỏ hơn pivot, sau đó đưa pivot về vị trí mới và thực hiện QuickSort trên hai phân đoạn trái và phải của pivot.