Cùng thực hiện các bước cụ thể triển khai ý tưởng và cài đặt chương trình cho thuật toán
Hoạt động 2 trang 41 Chuyên đề Tin học 11: Cùng thực hiện các bước cụ thể triển khai ý tưởng và cài đặt chương trình cho thuật toán sắp xếp trộn
- Các bước sắp xếp trộn (merge sort) như sau:
1. Nếu mảng chỉ có một phần tử hoặc không có phần tử nào, thì mảng đó đã được sắp xếp và ta không cần phải làm gì thêm.
2. Chia mảng thành hai phần bằng cách tìm chỉ số giữa (midpoint).
3. Đệ quy sắp xếp phần đầu tiên của mảng (từ đầu đến giữa).
4. Đệ quy sắp xếp phần thứ hai của mảng (từ giữa đến cuối).
5. Trộn (merge) hai phần đã được sắp xếp thành một mảng mới. Khi trộn, ta so sánh phần tử đầu tiên của từng mảng và chọn phần tử nhỏ hơn để đưa vào mảng mới. Sau đó, ta lặp lại quá trình này cho đến khi hết phần tử trong một trong hai mảng. Cuối cùng, ta đưa tất cả các phần tử còn lại của mảng còn lại vào mảng mới.
6. Trả về mảng đã được sắp xếp.
Các bước này sẽ được lặp lại cho đến khi tất cả các phần tử của mảng đã được sắp xếp.
- Cài đặt:
Xem thêm lời giải bài tập Chuyên đề học tập Tin học lớp 11 Kết nối tri thức hay, chi tiết khác:
Bài 7: Thiết kế thuật toán theo kĩ thuật chia để trị
Bài 8: Thực hành thiết thuật toán tìm kiếm theo kĩ thuật chia để trị
Bài 10: Thực hành giải toán bằng kĩ thuật chia để trị