Câu lệnh in ra màn hình: print(".....")
Các bước thực hiện
- Phân tích bài toán.
- Độ phức tạp thuật toán.
Câu lệnh in ra màn hình: print(".....")
Các bước thực hiện
- Phân tích bài toán.
- Độ phức tạp thuật toán.
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.
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?
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[3] <= pivot: thành 1f a[3]} >= 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.
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 Python 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.
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.
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ị”.