Advertisement
Guest User

Untitled

a guest
Oct 27th, 2017
254
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.87 KB | None | 0 0
  1. using System;
  2. using System.Linq;
  3.  
  4. namespace _03.Inversion_Count
  5. {
  6.     internal class Program
  7.     {
  8.      
  9.         private static void Main()
  10.         {
  11.             var a = Console.ReadLine()
  12.                     .Split()
  13.                     .Select(int.Parse)
  14.                     .ToArray();
  15.             int countInversion = mergeSort(a, 0, a.Length - 1);
  16.             Console.WriteLine(countInversion);
  17.         }
  18.      
  19.         public static int mergeSort(int[] a, int p, int r)
  20.         {
  21.             int countInversion = 0;
  22.             if (p < r)
  23.             {
  24.                 int q = (p + r) / 2;
  25.                 countInversion = mergeSort(a, p, q);
  26.                 countInversion += mergeSort(a, q + 1, r);
  27.                 countInversion += merge(a, p, q, r);
  28.             }
  29.             return countInversion;
  30.         }
  31.  
  32.         public static int merge(int[] a, int p, int q, int r)
  33.         {
  34.             //p=0, q=1, r=3
  35.             int countingInversion = 0;
  36.             int n1 = q - p + 1;
  37.             int n2 = r - q;
  38.             int[] temp1 = new int[n1 + 1];
  39.             int[] temp2 = new int[n2 + 1];
  40.             for (int index0 = 0; index0 < n1; index0++) temp1[index0] = a[p + index0];
  41.             for (int index0 = 0; index0 < n2; index0++) temp2[index0] = a[q + 1 + index0];
  42.  
  43.             temp1[n1] = Int32.MaxValue;
  44.             temp2[n2] = Int32.MaxValue;
  45.             int i = 0, j = 0;
  46.  
  47.             for (int k = p; k <= r; k++)
  48.             {
  49.                 if (temp1[i] <= temp2[j])
  50.                 {
  51.                     a[k] = temp1[i];
  52.                     i++;
  53.                 }
  54.                 else
  55.                 {
  56.                     a[k] = temp2[j];
  57.                     j++;
  58.                     countingInversion = countingInversion + (n1 - i);
  59.                 }
  60.             }
  61.             return countingInversion;
  62.         }
  63.     }
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement