Viết lại thuật toán sắp xếp trộn theo cách thực hiện trực tiếp trên dãy số A cho trước
Viết lại thuật toán sắp xếp trộn theo cách thực hiện trực tiếp trên dãy số A cho trước, cụ thể như sau.
Giải Chuyên đề Tin 11 Bài 9: Sắp xếp trộn - Kết nối tri thức
Vận dụng 2 trang 44 Chuyên đề Tin học 11: Viết lại thuật toán sắp xếp trộn theo cách thực hiện trực tiếp trên dãy số A cho trước, cụ thể như sau.
- Thủ tục trộn sẽ có dạng sau: merge(A,left,mid,right). Thủ tục này sẽ trộn hai phân đoạn của dãy A là A[left], ...., A[mid] và A[mid + 1]..... A[right]. Hai phân đoạn này phải được sắp xếp đúng trước đó.
- Thuật toán chính có dạng mergeSoft(A, left, right) như sau:
- Lệnh gọi hàm đệ quy là:
Lời giải:
1. Đầu tiên, ta cần import các thư viện time và random để thực hiện đo thời gian và sinh số ngẫu nhiên cho dãy số:
2. Tiếp theo, ta sẽ tạo một hàm để sắp xếp dãy số bằng thuật toán sắp xếp nổi bọt:
3. Sau đó, ta cần tạo một hàm để sắp xếp dãy số bằng thuật toán sắp xếp trộn:
4. Tiếp theo, ta sẽ đọc dãy số từ tệp văn bản và lưu vào một list:
5. Tiếp theo, ta tạo một bản sao của list này để thực hiện sắp xếp bằng hai cách khác nhau:
6. Sau đó, ta thực hiện sắp xếp bằng thuật toán sắp xếp nổi bọt và đo thời gian chạy:
7. Tiếp theo, ta thực hiện sắp xếp bằng thuật toán sắp xếp trộn và đo thời gian chạy:
8. In kết quả mảng sau khi sắp xếp:
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 ....
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 ....
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 ....
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 ....