Inversion Count in Arrays
Sat Apr 06 2024 Brute Force Method:
Implemented a straightforward yet computationally intensive method to count inversions. By comparing each element with every other element that follows it in the array, this method identifies and tallies inversion pairs, encapsulating the essence of brute force techniques.
Merge Sort and Count:
Adopted a more sophisticated and efficient approach, leveraging the merge sort algorithm's divide-and-conquer strategy. This method not only sorts the array but also counts inversions in three critical steps
1function inversionBrute(arr) {
2 let element = [];
3 for (let i = 0; i < arr.length - 1; i++) {
4 for (let j = i + 1; j < arr.length; j++) {
5 if (arr[i] > arr[j]) {
6 element.push([arr[i], arr[j]]);
7 }
8 }
9 }
10 return element;
11}
12
13//console.log(inversionBrute(arr));
14
15function mergeSortAndCount(arr) {
16 if (arr.length < 2) {
17 return [arr, 0];
18 }
19 let mid = Math.floor(arr.length / 2);
20 let left = arr.slice(0, mid);
21 let right = arr.slice(mid);
22 const [sortedLeft, leftInv] = mergeSortAndCount(left);
23 const [sortedRight, rightInv] = mergeSortAndCount(right);
24 const [mergedArr, splitInv] = mergeAndCount(sortedLeft, sortedRight);
25 return [mergedArr, leftInv + rightInv + splitInv];
26}
27function mergeAndCount(left, right) {
28 let i = 0,
29 j = 0,
30 inversions = 0;
31 const sortedArr = [];
32
33 while (i < left.length && j < right.length) {
34 if (left[i] <= right[j]) {
35 sortedArr.push(left[i++]);
36 } else {
37 inversions += left.length - i;
38 sortedArr.push(right[j++]);
39 }
40 }
41 return [sortedArr.concat(left.slice(i)).concat(right.slice(j)), inversions];
42}
43const arr1 = [2, 4, 1, 3, 5];
44const [sorted1, inversions1] = mergeSortAndCount(arr1);
45console.log(`Inversions: ${inversions1}`);
46
47const arr2 = [2, 3, 4, 5, 6];
48const [sorted2, inversions2] = mergeSortAndCount(arr2);
49console.log(`Inversions: ${inversions2}`);
50