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

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:

• Khởi động trang 40 Chuyên đề Tin học 11: Ta đã biết tìm kiếm nhị phân trên các dãy đã sắp xếp có độ phức tạp thời gian ....

• Hoạt động trang 40 Chuyên đề Tin học 11: Quan sát và thực hiện các bước theo ý tưởng của thuật toán sắp xếp trộn để ....

• 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 ....

• Luyện tập 2 trang 44 Chuyên đề Tin học 11: Viết lại chương trình hoàn chỉnh thực hiện sắp xếp trộn với dãy A ....

• Vận dụng 1 trang 44 Chuyên đề Tin học 11: Viết chương trình hoàn chỉnh nhập dãy số bất kì từ tệp văn bản ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 11 Kết nối tri thức hay, chi tiết khác:

• Chuyên đề Tin học 11 Bài 10: Thực hành giải toán bằng kĩ thuật chia để trị

• Chuyên đề Tin học 11 Bài 11: Bài toán tìm kiếm theo kĩ thuật duyệt

• Chuyên đề Tin học 11 Bài 12: Thực hành kĩ thuật duyệt cho bài toán tìm kiếm

• Chuyên đề Tin học 11 Bài 13: Kĩ thuật duyệt quay lui

• Chuyên đề Tin học 11 Bài 14: Thực hành kĩ thuật duyệt quay lui

Săn SALE shopee Tết:

• Mỹ phẩm SACE LADY giảm tới 200k
• SRM Simple tặng tẩy trang 50k
• Combo Dầu Gội, Dầu Xả TRESEMME 80k

---