Bài 9. Lập trình thuật toán sắp xếp nhanh trang 127, 128, 129
Khởi động
Nếu cần chọn một trong hai việc sau đây, em sẽ chọn việc làm nào? Vì sao?
1) Từ mô tả thuật toán bằng liệt kê các bước, viết chương trình Phython thực hiện thuật toán.
2) Từ chương trình Phython thực hiện thuật toán, viết lại ngắn gọn ý tưởng chính của thuật toán.
Phương pháp giải:
Dựa vào kiến thức đã học.
Lời giải chi tiết:
Nếu cần chọn một trong hai việc, em sẽ chọn:
1) Từ mô tả thuật toán bằng liệt kê các bước, viết chương trình Python thực hiện thuật toán.
Vì như vậy dễ nắm được các bước thực hiện và giúp bài toán có phương pháp giải chính xác hơn.
? mục 2 HĐ
Em hãy cho biết lược đồ phân đoạn Lomuto theo mã giả cho trong Hình 2 có đáp ứng yêu cầu phân đoạn để sắp xếp nhanh như trình bày ở mục 1 hay không.
Phương pháp giải:
Dựa vào đề bài và kiến thức đã học trong phần 1.
Lời giải chi tiết:
Lược đồ phân đoạn Lomuto theo mã giả trong hình 2 có đáp ứng yêu cầu phân đoạn để sắp xếp nhanh như đã trình bày ở phần 1.
? mục 4 NV1
Viết chương trình thực hiện sắp xếp nhanh một dãy số và chạy thử kiểm tra.
a) Dựa trên mã lệnh thuật toán cho trong Hình 3.
b) Dựa trên mã lệnh thuật toán cho trong Hình 5.
Phương pháp giải:
Dựa vào đề bài và kiến thức đã học.
Lời giải chi tiết:
a) Dựa trên mã lệnh thuật toán cho trong Hình 3:
b) Dựa trên mã lệnh thuật toán cho trong Hình 5:
? mục 4 NV2
Bổ sung thêm các câu lệnh in kết quả trung gian vào các chương trình nói trên để có thể quan sát diễn biến từng bước thực hiện sắp xếp nhanh một dãy số.
Phương pháp giải:
Dựa vào đề bài và kiến thức đã học.
Lời giải chi tiết:
Câu lệnh in kết quả trung gian, sử dụng câu lệnh: print(“…”)
Vận dụng
Em hãy thực hiện các công việc sau:
a) Sửa lại thủ tục phân đoạn đề có hàm quickSort_ down sắp xếp theo thứ tự giảm dần.
Gợi ý. Sửa đối phép so sánh trong câu lệnh 1f a[j] <= pivot: thành if a[j] >= pivot:
b) Tiếp tục sửa lại để có hàm quickSort_tuple_down sắp xếp danh sách các cặp. ví dụ (tên học sinh, điểm môn học) theo điệm môn học giảm dần.
Gợi ý: Sửa đổi đầu vào thành danh sách các cặp (tên học sinh, điểm môn học) và thực hiện so sánh theo điểm môn học.
Phương pháp giải:
Dựa vào đề bài và kiến thức đã học.
Lời giải chi tiết:
a) Sửa lại thủ tục phân đoạn đề có hàm quickSort_ down sắp xếp theo thứ tự giảm dần:
b) Tiếp tục sửa lại để có hàm quickSort_tuple_down sắp xếp danh sách các cặp. ví dụ (tên học sinh, điểm môn học) theo điệm môn học giảm dần.
Luyện tập 1
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ị”.
Phương pháp giải:
Dựa vào đề bài và kiến thức đã học.
Lời giải chi tiết:
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.
Luyện tập 2
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?
Phương pháp giải:
Dựa vào đề bài và kiến thức đã học.
Lời giả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.