Find the number of inversions in an array

View previous topic View next topic 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

View previous topic View next topic Back to top

- Similar topics

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