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à:
Bằng cách nhấp vào Đăng nhập, bạn đồng ý Chính sách bảo mật và Điều khoản sử dụng của chúng tôi. Nếu đây không phải máy tính của bạn, để đảm bảo an toàn, hãy sử dụng Cửa sổ riêng tư (Tab ẩn danh) để đăng nhập (New Private Window / New Incognito Window).
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 nhauz;
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:
Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi
Vui | Buồn | Bình thường |