Find the number of inversions in an array

Go down

Find the number of inversions in an array

Post  viterbi on Tue Sep 13, 2011 10:11 am

inversion means for i< j, a[i] > a[j], in other words, they are the parts that are not well sorted. For example, in array {1, 5, 7, 9, 10, 6, 20}, the number of inversions is 3: {7, 6}, {9, 6}, {10, 6}
1____long long reversal_num(int* a, int num) {
2__________if (num<=1) return 0;
3__________int nl = num/2;
4__________int nr = num-nl;
5__________long long left_inv = reversal_num(a, nl);
6__________long long right_inv = reversal_num(a+nl, nr);
7____
8__________int* left = new int[nl+1];
9__________int* right = new int[nr+1];
10_________for (int i=0; i<nl; i++) left[i] = a[i];
11_________for (int i=nl; i<num; i++) right[i-nl] = a[i];
12_________left[nl] = numeric_limits<int>::max();
13_________right[nr] = left[nl];
14___
15_________int i = 0;
16_________int j = 0;
17_________long long inv_num = left_inv+right_inv;
18___
19_________for (int p=0; p<num; p++)
20_______________if (left[i] <= right[j]) a[p] = left[i++];
21_______________else {
22_____________________a[p] = right[j++];
23_____________________inv_num += nl-i;
24_______________}
25___
26_________delete[] left;
27_________delete[] right;
28_________return inv_num;
29___}

viterbi

Posts : 32
Join date : 2011-09-03

View user profile

Back to top Go down

Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum