Count Inversions in Array in DSA Python - Build from Scratch

Count Inversions in Array

📖 Scenario: You have a list of numbers representing the order of books on a shelf. You want to find out how many pairs of books are out of order compared to the sorted order. This helps you understand how messy the shelf is.

🎯 Goal: Build a program that counts the number of inversions in an array. An inversion is a pair of elements where the first element is bigger but appears before the smaller one.

📋 What You'll Learn

Create a list called books with the exact values [8, 4, 2, 1]

Create a variable called inversion_count and set it to 0

Use a nested for loop with variables i and j to compare elements in books

Increase inversion_count by 1 each time you find an inversion where books[i] > books[j] and i < j

Print the value of inversion_count

💡 Why This Matters

🌍 Real World

Counting inversions is useful in sorting algorithms and understanding how far a list is from being sorted, like checking how messy a shelf is.

💼 Career

This concept is important in software development for optimizing sorting and analyzing data order, useful in fields like data science and algorithm design.

1

Create the list of books

Create a list called books with these exact values: [8, 4, 2, 1]

DSA Python

# Create the list called books with values [8, 4, 2, 1]
# Your code here

Hint

Use square brackets [] to create a list and separate numbers with commas.

2

Set up the inversion counter

Create a variable called inversion_count and set it to 0

DSA Python

books = [8, 4, 2, 1]
# Create a variable inversion_count and set it to 0
# Your code here

Hint

This variable will keep track of how many inversions you find.

3

Count the inversions using nested loops

Use a nested for loop with variables i and j to compare elements in books. Increase inversion_count by 1 each time you find an inversion where books[i] > books[j] and i < j

DSA Python

books = [8, 4, 2, 1]
inversion_count = 0
# Use nested for loops to count inversions
# Your code here

Hint

Use range(len(books)) to loop over indices. Compare pairs where the first index is less than the second.

4

Print the total inversion count

Print the value of inversion_count

DSA Python

books = [8, 4, 2, 1]
inversion_count = 0
for i in range(len(books)):
    for j in range(i + 1, len(books)):
        if books[i] > books[j]:
            inversion_count += 1
# Print the inversion_count
# Your code here

Hint

Use print(inversion_count) to show the result.