โจทย์: นับ Inversions ในอาร์เรย์ (คู่ i
ตัวอย่าง
arr = [1, 5, 3, 8, 7]
Inversions: (5,3), (8,7) → 2 pairs
วิธีที่ 1: Naive O(n²)
def count_inversions(arr):
n = len(arr)
inv_count = 0
for i in range(n):
for j in range(i + 1, n):
if arr[i] > arr[j]:
inv_count += 1
return inv_count
print(count_inversions([1, 5, 3, 8, 7])) # 2
วิธีที่ 2: Merge Sort Based O(n log n)
def merge_sort_count(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, left_inv = merge_sort_count(arr[:mid])
right, right_inv = merge_sort_count(arr[mid:])
merged = []
i = j = 0
split_inv = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
split_inv += len(left) - i # ทุกตัวใน left[i:] > right[j]
merged.extend(left[i:])
merged.extend(right[j:])
return merged, left_inv + right_inv + split_inv
def count_inversions_fast(arr):
_, count = merge_sort_count(arr)
return count
print(count_inversions_fast([1, 5, 3, 8, 7])) # 2
ผลลัพธ์
Total number of inversions are: 2
ประยุกต์ใช้
- วัดความ " gần Sorted"
- Ranking Correlation (Kendall Tau)
- Collaborative Filtering
ความซับซ้อน: Naive O(n²), Merge Sort O(n log n)
