JavaScript: Find the number of inversions of a specified array of integers

JavaScript Basic: Exercise-102 with Solution

Count Inversions in Array

Write a JavaScript program to find the number of inversions of a given array of integers.

Note: Two elements of the array a stored at positions i and j form an inversion if a[i] > a[j] and i < j.

Sample Solution:

JavaScript Code:

// Function to count the number of inversions in an array (naive approach)
function number_of_InversionsNaive(arr) {
    var ctr = 0; // Counter for inversions

    // Loop through the array elements
    for (var i = 0; i < arr.length; i++) {
        for (var j = i + 1; j < arr.length; j++) {
            // If an inversion is found, increment the counter
            if (arr[i] > arr[j]) 
              ctr++;
        }
    }

    return ctr; // Return the count of inversions
}

// Test cases
console.log(number_of_InversionsNaive([0, 3, 2, 5, 9]));   // Output: 1
console.log(number_of_InversionsNaive([1, 5, 4, 3]));     // Output: 3
console.log(number_of_InversionsNaive([10, 30, 20, -10])); // Output: 4  

Output:

1
3
4

Live Demo:

See the Pen javascript-basic-exercise-102 by w3resource (@w3resource) on CodePen.

Flowchart:

ES6 Version:

// Function to count inversions in an array
const number_of_InversionsNaive = (arr) => {
    let ctr = 0; // Counter to track inversions

    // Loop through the array to count inversions
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            // Increment the counter if an inversion is found
            if (arr[i] > arr[j]) {
                ctr++;
            }
        }
    }

    return ctr; // Return the total count of inversions
}

console.log(number_of_InversionsNaive([0, 3, 2, 5, 9]));   // Example usage
console.log(number_of_InversionsNaive([1, 5, 4, 3]));   // Example usage
console.log(number_of_InversionsNaive([10, 30, 20, -10]));  // Example usage 

For more Practice: Solve these Related Problems:

• Write a JavaScript program that counts inversions in an array using a modified merge sort algorithm.
• Write a JavaScript function that computes the number of inversion pairs by comparing each element with every other element in a brute-force manner.
• Write a JavaScript program that returns the inversion count of an array and tests the function with worst-case (reverse sorted) inputs.

Go to:

• JavaScript basic Exercises Home ↩
• JavaScript Exercises Home ↩

PREV : Check Latin Letters with No Adjacent Upper/Lower Case.
NEXT : Max Integer by Removing One Digit.

Improve this sample solution and post your code through Disqus.