Difference between revisions of "TADM2E 4.19"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Recovering wiki)
Line 22: Line 22:
 
   And every inversion becomes corrected.
 
   And every inversion becomes corrected.
 
    
 
    
If P contains "x" inversions.. then it also contained "n(n-1)/2 - x" in order pairs.
+
If P contains "x" inversions.. then it also contained "n(n-1)/2 - x" in order pairs.
Thus Pr contains "x" in order pairs and "n(n-1)/2 - x" inversions.
+
Thus Pr contains "x" in order pairs and "n(n-1)/2 - x" inversions.
  
 
Summing up the inversions in P and Pr we get n(n-1)/2
 
Summing up the inversions in P and Pr we get n(n-1)/2

Revision as of 18:22, 11 September 2014

1) Starting from left to right, the number of inversions

 for 1st number is n-1
 for 2nd number is n-2
 ...
 ..
 ....nth number is n-n = 0

Total number of inversions is the sum of all of the above sum of integers from 0 to n - 1 = n(n-1)/2

2. We know that the maximum num of inversions is n(n-1)/2.

 Consider a permutation P.
 a1 a2 ai..ak...aj..am.... an-1 an
 ai and aj are out of order
 ak and am are in order.  
 For Pr,
 ai and aj will get reversed, and will become in order.
 ak and am will get reversed and will become out of order.
 Every In order pair becomes an inversion.
 And every inversion becomes corrected.
  

If P contains "x" inversions.. then it also contained "n(n-1)/2 - x" in order pairs. Thus Pr contains "x" in order pairs and "n(n-1)/2 - x" inversions.

Summing up the inversions in P and Pr we get n(n-1)/2

3. To calculate the max inversions in part 1, every ith position had n - i inversions. i.e following a number, all other numbers will be out of order. In the average case, we can argue that about 1/2 of the number will be out of order....

 for 1st number  (n-1)/2
 for 2nd number   (n-2)/2
 ...
 ..
 ....nth number is (n-n)/2 = 0

Total number of inversions is the sum of all of the above sum of integers from 0 to (n - 1)/2 = n(n-1)/4...