Chỉ so sánh hai phần tử chưa lấy ở đầu mỗi dãy
Giả sử B và C đã không giảm. Dùng i,j chỉ phần tử kế tiếp của B,C; k chỉ chỗ ghi trong dãy kết quả A. Ban đầu cả ba bằng 0.
So sánh B[i] với C[j], lấy giá trị nhỏ hơn; khi bằng nhau, mã dưới lấy B[i] trước. Tăng chỉ số của dãy vừa lấy và tăng k. Khi một dãy hết, chép nốt phần còn lại của dãy kia. Các giá trị trùng vẫn được giữ đủ số lần.
Mỗi lần lấy đúng một phần tử
```python
def merge(B, C):
m, n = len(B), len(C)
A = [0] * (m + n)
i = j = k = 0
while i < m and j < n:
if B[i] <= C[j]:
A[k] = B[i]
i += 1
else:
A[k] = C[j]
j += 1
k += 1
while i < m:
A[k] = B[i]
i += 1
k += 1
while j < n:
A[k] = C[j]
j += 1
k += 1
return A
```
Hai vòng while cuối chép phần chưa lấy; nếu dãy đó đã hết thì vòng tương ứng không chạy. Hàm trả A, không sắp xếp lại hay xóa phần tử trong B,C. Một dãy rỗng vẫn trộn được; cả hai rỗng thì trả [].
Truy vết với hai dãy khác độ dài
Cho B=[−3,2,2,8], C=[0,2,5].
| So sánh | Giá trị đưa vào A | Dãy vừa lấy |
|---|---|---|
| −3 và 0 | −3 | B |
| 2 và 0 | 0 | C |
| 2 và 2 | 2 | B |
| 2 và 2 | 2 | B |
| 8 và 2 | 2 | C |
| 8 và 5 | 5 | C |
| C đã hết | 8 | Chép nốt B |
Kết quả là [−3,0,2,2,2,5,8]. Có ba số 2 vì B có hai số 2 và C có một số 2. Hai dãy không cần bằng độ dài.
Với độ dài m,n, tổng số phần tử đưa vào kết quả là m+n, nên thời gian trộn là O(m+n). Nếu cả hai dãy không rỗng, vòng so sánh chính chạy không quá m+n−1 lần: sau mỗi lần lấy một phần tử và sẽ dừng ngay khi một dãy hết.
Bài luyện
Trộn B=[−3,2,2,8] và C=[0,2,5] bằng mã trong bài nhận dãy nào?
Dãy không giảm và giữ đủ bảy phần tử.
Đây là nối dãy, chưa được trộn theo thứ tự.
Đã bỏ mất các lần xuất hiện trùng của số 2.
Còn thiếu một số 2.
Lời giải
Lần lượt lấy −3,0,2,2,2,5; lúc này C hết nên chép 8 từ B. Kết quả có đủ ba số 2 và bảy phần tử.
Bài luyện
Khi B[i]==C[j], mã trong bài cập nhật thế nào sau khi ghi giá trị?
Đây là cách chọn C, khác nhánh <= đang dùng.
Điều kiện <= chọn phần tử của B trước.
Mỗi lượt chỉ lấy một phần tử; tăng cả i,j sẽ bỏ một phần tử trùng.
Không dịch chỉ số nguồn sẽ lấy lặp phần tử đó.
Lời giải
Vì B[i]<=C[j] đúng khi bằng nhau, hàm ghi B[i], tăng i rồi tăng k. C[j] vẫn chưa lấy, nên j giữ nguyên để không mất lần xuất hiện đó.
Bài luyện
Một dãy đã hết, phần còn lại của dãy kia được xử lí thế nào?
Các phần tử ở giữa cũng cần được giữ.
Số0 ban đầu chỉ để tạo chỗ ghi, không thay dữ liệu.
Phần còn lại đã có thứ tự và vẫn thuộc dữ liệu cần giữ.
Sẽ làm mất phần tử.
Lời giải
Khi một dãy hết, không còn cần so sánh hai phía. Phần chưa lấy của dãy kia đã không giảm và có thể đưa liên tiếp vào A.
Bài luyện
Với m=4,n=3 và cả hai dãy không rỗng, vòng so sánh chính có nhiều nhất bao nhiêu lần lặp?
m+n là số phần tử phải ghi, gồm cả phần chép nốt.
Không so sánh từng cặp của tích hai độ dài.
Vòng có thể chạy quá 3 lần nếu hai dãy xen kẽ.
Giới hạn là m+n−1=6.
Lời giải
Sau mỗi lần so sánh, một phần tử được lấy. Nếu đã lấy m+n−1 phần tử thì ít nhất một dãy đã hết, vòng chính dừng. Ví dụ trong bảng đạt đúng 6 lần, sau đó chép phần tử còn lại.
Đang học