Question

please write in c++

Algorithm Design problem:

Counting inversions: given an array of n integers, find out the total number of inversions in the given sequence. For example, for the sequence of 2, 4, 1, 3, 5, there are three inversions (2,1), (4,1), and (4,3).

1. Give a brute-force algorithm with running time of O(n^2).
2. Using the technique of divide-and-conquer, design an algorithm with running time of O(nlog n).

Answer 1

Program: In this program, we write two functions to count the inversions in an array. The first function runs in a time complexity of O(n^2) and the second function runs in O(nlogn) time complexity.

Function 1 algorithm:

• Traverse the array from start to end
• Create another for loop and for every element find the count of elements smaller than the current element
• Keep updating the count while checking for each element
• Return the count of inversions.

Function 2 algorithm:

• The idea is based on merge sort, divide the array into two halves in each step until the base case is reached which is when there is only one element in the given half.
• Create a function mergeSort to divide the array into two halves and find the answer by summing the number of inversions in the first half, number of inversion in the second half and the number of inversions by merging the two.
• Create a function merge that counts the number of inversions when two halves of the array are merged, create indices i and j to keep track of the first(left) half and second(right) half of array. If a[i] is greater than a[j], then there are (mid – i) inversions. since left and right subarrays are sorted, as a result all the remaining elements in left-subarray (a[i+1], a[i+2] … a[mid]) will be greater than a[j].
• Return the inversion count

Code:

#include <iostream>
using namespace std;

// Method 1: Time complexity O(n^2)
int inversionCount1(int arr[], int n){

    int invCount = 0;
    // Traverse through the array till the end

    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {

            // count the number of elements smaller than current element
            // update count
            if (arr[i] > arr[j]) {
                invCount++;
            }
        }
    }

    // Return count
    return invCount;
}


// Method 2: Time Complexity O(nlogn)
// Using merge sort

// Function merge
int merge(int arr[], int temp[], int left, int mid, int right){

    // Create indices for left and right array i.e i ad j
    int i = left, j = mid, k = left;

    // Initialize inversion count
    int invCount = 0;

    // Run a loop while loop until i and j are in range
    while ((i <= mid - 1) && (j <= right)) {

        // If left array element is small than assign that in the array
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        }
        else {
            temp[k++] = arr[j++];

            // Else update inversion count
            invCount = invCount + (mid - i);
        }
    }

    // Check if any element is present in left side array
    while (i <= mid - 1) {
        temp[k++] = arr[i++];
    }

    // Check if any element is present in right side array
    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // Store the values in temp
    for (i = left; i <= right; i++) {
        arr[i] = temp[i];
    }

    return invCount;
}

int mergeSort(int arr[], int temp[], int left, int right){

    // Initialise inversion count
    int mid, invCount = 0;

    // Check if left is less than right
    if (right > left) {

        // Calculate mid
        mid = (right + left) / 2;

        // Update count
        invCount += mergeSort(arr, temp, left, mid);
        invCount += mergeSort(arr, temp, mid + 1, right);
        invCount += merge(arr, temp, left, mid + 1, right);
    }

    // Return count
    return invCount;
}


// Inversion count2 : using merge Sort
int inversionCount2(int arr[], int array_size){

    // Create temporary array
    int temp[array_size];

    // Call mergesort
    return mergeSort(arr, temp, 0, array_size - 1);
}

int main(){

    int arr[] = {2, 4, 1, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int ans1 = inversionCount1(arr, n);
    int ans2 = inversionCount2(arr, n);

    cout << ans1 << endl;
    cout << ans2 << endl;
    return 0;
}

Output: