Count Inversions (Revisited) 🎯

Welcome back to CodeYourCraft! Today, we're going to delve into a fascinating topic called Count Inversions. This concept is crucial for understanding various algorithms and data structures. Let's get started!

What are Inversions? 📝

An inversion in an array occurs when two elements a[i] and a[j] are out of their original order (ascending) and a[i] is greater than a[j]. For example, in the array [5, 4, 3, 2, 1], the inversions are (5, 1), (5, 2), (5, 3), and (5, 4).

Why Count Inversions? 💡

Counting inversions is a fundamental problem in computer science. It helps us understand the properties of arrays, and it's a stepping stone to more complex algorithms like Merge Sort and Fast Fourier Transform (FFT).

Counting Inversions - Brute Force Approach 📝

The simplest way to count inversions is to use a brute force approach. We'll iterate through the array, keeping a running count of inversions. Here's a Python example:

python

def count_inversions(arr):
    count = 0
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] > arr[j] and arr[i] != arr[j]:
                count += 1
    return count

💡 Pro Tip: This approach has a time complexity of O(n^2), which is quite slow. We'll learn a more efficient method later.

Counting Inversions - Merge Sort Based Approach 🎯

Merge Sort is a powerful sorting algorithm with a time complexity of O(n log n). We can modify Merge Sort to count inversions at the same time.

Here's a Python implementation:

python

def merge(arr, left, mid, right):
    inversions = 0
    left_arr = arr[left:mid]
    right_arr = arr[mid:right]

    left_index = right_index = inversions = 0

    for i in range(left, right+1):
        while left_index < len(left_arr) and (right_index < len(right_arr) or left_arr[left_index] > right_arr[right_index]):
            if left_arr[left_index] <= right_arr[right_index] and (not left_arr[left_index] == right_arr[right_index]):
                inversions += len(left_arr) - left_index
            left_index += 1

        if right_index < len(right_arr):
            right_index += 1

        if left_index < len(left_arr):
            left_index += 1

    i = left
    j = right_index
    k = 0
    while i < mid and j < right:
        if left_arr[i] <= right_arr[j]:
            arr[k] = left_arr[i]
            i += 1
        else:
            arr[k] = right_arr[j]
            j += 1
            inversions += len(left_arr) - i
        k += 1

    while i < mid:
        arr[k] = left_arr[i]
        i += 1
        k += 1

    while j < right:
        arr[k] = right_arr[j]
        j += 1
        k += 1

    return inversions

def count_inversions_merge_sort(arr):
    if len(arr) <= 1:
        return 0

    mid = len(arr) // 2
    left = count_inversions_merge_sort(arr[:mid])
    right = count_inversions_merge_sort(arr[mid:])
    total = left + right + merge(arr, 0, mid, len(arr)-1)

    return total

📝 Note: This method has a time complexity of O(n log n), making it more efficient than the brute force approach.

Quiz 🎓

That's it for today! By understanding inversions and learning to count them, you're taking a significant step forward in mastering data structures and algorithms. Keep practicing and learning with CodeYourCraft! 🔝

Stay tuned for more exciting topics! 🚀