Cả phần còn lại bên trái đều tạo nghịch đảo
Hai đoạn left…mid và mid+1…right đã được sắp xếp không giảm. Nếu A[i]>A[j], mọi phần tử A[i],…,A[mid] đều lớn hơn A[j]. Vì các phần tử này thuộc nửa trái của miền ban đầu, mỗi phần tử ghép với A[j] tạo một nghịch đảo chéo.
Có mid−i+1 phần tử như vậy. Cộng số này rồi lấy A[j] vào dãy tạm. Nếu A[i]<=A[j], lấy A[i] và không cộng; dấu bằng không tạo nghịch đảo.
Vừa trộn, vừa trả số cặp chéo
```python
def merge_count(A, left, mid, right, temp):
i, j, k = left, mid + 1, left
count = 0
while i <= mid and j <= right:
if A[i] <= A[j]:
temp[k] = A[i]
i += 1
else:
temp[k] = A[j]
count += mid - i + 1
j += 1
k += 1
while i <= mid:
temp[k] = A[i]
i += 1
k += 1
while j <= right:
temp[k] = A[j]
j += 1
k += 1
for k in range(left, right + 1):
A[k] = temp[k]
return count
```
Tham số temp là dãy tạm đủ chỗ cho A, được tạo một lần trước quá trình đệ quy. Sau khi trộn, hàm ghi lại A[left:right+1] qua vòng chép và trả số cặp chéo. Phần tử còn lại cũng phải được chép để hai nhánh trên tiếp tục nhận dữ liệu đã sắp xếp.
Nhìn một lần cộng nhiều cặp
Giả sử đang trộn nửa trái [2,6] và nửa phải [1,6], left=0,mid=1,right=3. Lần đầu i=0,j=2: A[i]=2>A[j]=1. Hai phần tử2 và 6 của nửa trái đều lớn hơn 1 nên cộng mid−i+1=1−0+1=2.
Sau đó lấy 2, rồi lấy 6 bên trái khi bằng 6 bên phải mà không cộng thêm. Bước trộn này trả 2; số cặp nghịch đảo bên trong từng nửa đã được đếm ở lời gọi nhỏ, không tính lại ở đây.
Bài luyện
Trong ví dụ, vì sao khi gặp giá trị 1 bên phải cần cộng 2?
Chỉ số j chưa phải số cặp cần cộng.
Chỉ đếm chiều có chỉ số trước nhỏ hơn chỉ số sau.
Hai phần tử tạo hai cặp chéo khác nhau.
Số cộng phụ thuộc phần còn lại bên trái, không chỉ độ dài phải.
Lời giải
Nửa trái đã sắp nên từ 2 trở đi mọi giá trị còn lại ít nhất bằng 2, đều lớn hơn 1. Có mid−i+1=2 phần tử, tương ứng hai nghịch đảo.
Bài luyện
Khi A[i]==A[j], mã thực hiện điều gì?
Sẽ đếm sai các cặp bằng nhau.
Trộn phải giữ đủ dữ liệu.
Số phần tử không đồng nghĩa số nghịch đảo.
Nhánh <= giữ giá trị trái mà không tính dấu bằng là nghịch đảo.
Lời giải
Nghịch đảo yêu cầu giá trị trước lớn hơn giá trị sau. Khi bằng nhau, nhánh <= đưa A[i] vào temp và không cộng count.
Bài luyện
Vì sao bước cuối phải chép dãy tạm lại vào A?
Thứ tự của các đoạn là điều kiện để cộng theo nhóm.
Số đếm đã được tính riêng trong count.
Không được bỏ các lần xuất hiện trùng.
Hàm trộn tạo thứ tự không giảm.
Lời giải
Quy tắc cộng mid−i+1 dựa trên các đoạn đã được sắp. Ghi kết quả trộn lại vào A bảo đảm điều kiện đó ở mức đệ quy tiếp theo.
Đang học