4. Let A be an array of n distinct numbers. Two elements of A are inverted if i

Question

4. Let A be an array of n distinct numbers. Two elements of A are inverted if i but Au] > A. For example, in the array 12,3,1 the elements 3 and 1 are inverted. (a) (5 pts) List all the pairs of elements that are inverted in A 2.3,8.6,1), (b) (5 pts) Write down an array with flve numbers that has the maximum number of possible inversions. Let A and A2 be two arrays of n elements, such that Ai had more inver- Why? (10 pts) sions than A2. Which algorithm will be faster to sort using INSERTION-SORT Justify your answer) (c) (d) (10 pts) Describe a simple algorithm that outputs the number of inversions of an array. It can have any complexity. You don't need to write pseudocode (although you can), but your answer must be clear and easy to follow.

Explanation / Answer

4.
a) {2,3,8,6,1}
    inverted members are
    2,1
    3,1
    8,6
    8,1
    6,1

b) {5,4,3,2,1} This will have maximum number of inversions.It is
    an array in descending order.

c) The insertion sort will be faster in A2 becaue A2 is having less number
    of inversions.Insertion sort starts from the beginging.It starts with
    first element as sorted list and then continues to grow that. So A1 will
    have more number of shifting to the begining as comapred to A2. A1 is     more unsorted than A2.

d) A simple approach will be as follows:

   Pick the A[i] the element from the list and traverse from i+1 to n to
   find out all the numbers which are smaller than A[i]. We will store these
   numbers and can write all the inversions.We need to repeate it for all n.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.