12.5. Graphical Representation of Inversions

Try these first

1. 1.

   Define what an inversion is.

   Hint

   Think about two people's different preferences.

2. 2.

   What is the time complexity of a brute-force method to count inversions?

   Hint

   Consider how many comparisons are made.

3. 3.

   What is an inversion?

   • A pair ranked similarly
   • A ranking disagreement
   • A sorting algorithm

   Hint

   Recall the definition we discussed.

4. 4.

   True or False: The brute force method is the most efficient way to count inversions.

   • True
   • False

   Hint

   Think about the performance of the two methods.

5. 5.

   Given the array [10, 20, 30, 40], if a new number '25' is added, how many inversions are created?

   Hint

   Check the new number against existing numbers to see if they form inversions.

6. 6.

   Using your knowledge of merge sort, detail the steps to count inversions for the array [7, 5, 6, 4].

   Hint

   Break down the problem and count during each merge step.