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ù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
Giải Chuyên đề Tin 11 Bài 9: Sắp xếp trộn - Kết nối tri thức
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
Lời giải:
- 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:
Lời giải bài tập Chuyên đề Tin 11 Bài 9: Sắp xếp trộn hay, chi tiết khác:
Câu hỏi 1 trang 41 Chuyên đề Tin học 11: Hãy thực hiện thao tác trộn hai dãy sau ....
Câu hỏi 2 trang 41 Chuyên đề Tin học 11: Thực hiện sắp xếp dãy 3, 2, 7, 1, 6, 5 theo các bước ....
Câu hỏi 1 trang 43 Chuyên đề Tin học 11: Trong chương trình 1 (trộn hai dãy B, C), vòng lặp tại ....
Câu hỏi 2 trang 43 Chuyên đề Tin học 11: Mô tả các bước thực hiện chương trình 2 nếu ....
Hoạt động 3 trang 43 Chuyên đề Tin học 11: Phân tích, trao đổi, thảo luận để tính độ phức tạp ....
Câu hỏi 1 trang 44 Chuyên đề Tin học 11: Tính thời gian chạy của thuật toán sắp xếp trộn nếu ....
Câu hỏi 2 trang 44 Chuyên đề Tin học 11: Mô tả thực hiện các bước của sắp xếp trộn với dãy ....
Câu hỏi 2 trang 44 Chuyên đề Tin học 11: Mô tả thực hiện các bước của sắp xếp trộn với dãy ....
Luyện tập 1 trang 44 Chuyên đề Tin học 11: Viết chương trình thực hiện công việc sau ....