Giải SGK Chuyên đề Tin học 11 Bài 9. Sắp xếp trộn

Kỹ thuật chia để trị có thể được áp dụng cho bài toán sắp xếp, và thực tế nó đã được sử dụng để thiết kế các thuật toán sắp xếp hiệu quả như QuickSort và MergeSort.

Tuy nhiên, trong thực tế, cách tiếp cận này không phải lúc nào cũng làm tăng hiệu quả của thuật toán sắp xếp. QuickSort và MergeSort, mặc dù sử dụng phương pháp chia để trị, thường là những thuật toán có hiệu quả cao. Nhưng nếu áp dụng phương pháp chia để trị cho một thuật toán sắp xếp khác như BubbleSort hoặc InsertionSort, chẳng hạn, thì không có nhiều lợi ích. Trong những trường hợp đó, việc sử dụng phương pháp chia để trị có thể làm giảm hiệu quả của thuật toán sắp xếp.

- 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:

Ta biết rằng i ban đầu bằng 0 và tăng lên 1 sau mỗi lần lặp, do đó i sẽ tăng từ 0 đến m-1 (tổng cộng m bước lặp).

Tương tự, j ban đầu bằng 0 và tăng lên 1 sau mỗi lần lặp, nên j sẽ tăng từ 0 đến n-1 (tổng cộng n bước lặp).

Vì vậy, số bước lặp tối đa của vòng lặp này là min(m, n) (tức là số phần tử ít hơn trong hai dãy B và C). Do đó, vòng lặp sẽ lặp tối đa min(m, n) lần.

Mô tả các bước thực hiện chương trình 2 nếu dãy gốc A chỉ có một phần tử:

Nếu dãy có 1 phần tử thì trả về kết quả là dãy A ngay.

Gọi T(n) là thời gian chạy của thuật toán sắp xếp trộn.

Với n = 1, dòng lệnh 2 trả lại ngay dãy gốc A, do đó T(1) = 1.

Trường hợp tổng quát

- Tại bước chia (dòng 5), cần O(1) thời gian để thực hiện.

- Các dòng 6, 7 sẽ mất 2T(n/2) thời gian.

- Dòng lệnh 8 thực hiện trộn hai dãy với thời gian O(n).

Tổng kết lại chúng ta các công thức sau tính thời gian T(n).

T(1)=1

T(n) = 2T(n/2) + O(n), n > 1 (1)

Không mất tổng quát, giả sử tồn tại hằng số C > 0 sao cho:

T(n) = 2T (n/2)+ Cn, n > 1 (2)

Các công thức (1), (2) được gọi là công thức truy hồi để tính độ phức tạp thời gian T(n)
của thuật toán trộn.

Người ta tính được: T(n) = O(nlogn).

Thời gian chạy của thuật toán sắp xếp trộn nếu A = [3, 1] →n = 2:

T(2) = O(2log2) ≈ 2× 0.3 = 0.6

Mô tả thực hiện các bước của sắp xếp trộn với dãy A = [5, 1, 7, 4

T(4) = O(4log4) ≈ 2× 0.6 = 1.2

Đây là một ví dụ về cách viết chương trình bằng ngôn ngữ Python để trộn hai dãy số được lưu trữ trong tệp văn bản "Data.inp" và ghi kết quả vào tệp "Data.out":

- Đầu tiên, chương trình sử dụng hàm open() để mở tệp "Data.inp" với chế độ đọc dữ liệu (‘r’).

- Sau đó, chương trình đọc hai dòng dữ liệu từ tệp bằng cách sử dụng phương thức readline(), và loại bỏ các ký tự trắng ở đầu và cuối dòng bằng phương thức strip().

- Tiếp theo, chương trình sử dụng phương thức split() để tách các số trong hai dòng dữ liệu thành một danh sách các số nguyên. Hàm int() được sử dụng để chuyển đổi các chuỗi số sang kiểu số nguyên.

- Sau đó, chương trình trộn hai danh sách số lại với nhau bằng cách sử dụng phương thức sorted() để sắp xếp danh sách theo thứ tự tăng dần.

- Cuối cùng, chương trình sử dụng hàm open() để mở tệp "Data.out" với chế độ ghi dữ liệu ('w'), và sử dụng phương thức write() để ghi danh sách số trộn được vào tệp. Hàm join() được sử dụng để chuyển đổi các số trong danh sách trở lại thành chuỗi, và ký tự dấu cách được sử dụng để ngăn cách giữa các số.

Chương trình hoàn chỉnh như sau:

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: