12. Divide and Conquer: Counting Inversions

Try these first

1. 1.

   Define what an inversion is in a list.

   Hint

   Think about the order of elements in an array.

2. 2.

   What does the divide and conquer method entail?

   Hint

   Remember the steps of the algorithm.

3. 3.

   What is an inversion in a sequence?

   • A pair of items that are in sequential order
   • A pair of items that are not in sequential order
   • Any two items in a sequence

   Hint

   Think about how we define ordering in a list.

4. 4.

   True or False: A divide and conquer strategy can be used to count inversions efficiently.

   • True
   • False

   Hint

   Recall the efficiency compared to a brute force method.

5. 5.

   Determine the number of inversions for the following array: [2, 3, 8, 6, 1]. Explain the process you used.

   Hint

   List pairs in order and check their indices.

6. 6.

   Consider two rankings, A = [3, 1, 2] and B = [1, 3, 2]. Calculate the number of inversions and describe how you derived the count.

   Hint

   Focus on how elements are ranked in both A and B.