CODEWITHSUNDEEP
c++arraysalgorithmsorting
Shravan40
Shravan40

Reputation: 9908

Counting Inversions in an array via merge sort

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.

#include <iostream>
#include <cstdlib>
using namespace std;

int merge(int arr[],int temp[], int left, int mid, int right)
{
    int inv_count = 0;
    int i = left;
    int j = mid;
    int k = right;
    while((i <= mid-1) && (j <= right))
    {
        if(arr[i] <= arr[j])
        {
            temp[k++] = arr[i++];
        }
        else
        {
            temp[k++] = arr[j++];
            inv_count += (mid - i);
        }
    }
    while(i <= mid-1)
        temp[k++] = arr[i++];
    while(j <= right)
        temp[k++] = arr[j++];
    for(i = left; i <= right; i++)
        arr[i] = temp[i];
    return inv_count;
}

int _merge_sort(int arr[], int temp[], int left, int right)
{
    int mid, inv_count = 0;
    if(right > left)
    {
        mid = (right+left)/2;
        inv_count = _merge_sort(arr,temp,left,mid);
        inv_count += _merge_sort(arr,temp,mid+1,right);
        inv_count += merge(arr,temp,left,mid+1,right);
    }
    return inv_count;
 }

int merge_sort(int arr[], int array_size)
{
    int *temp = (int *)malloc(sizeof(int)*array_size);
    return (_merge_sort(arr,temp,0,array_size-1));
}

int main()
{
    int arr[]= {1, 25, 12, 56, 36, 3, 0, 10, 8, 7};
    for(int i = 0; i < 10; i++)
        cout<<arr[i]<<"\t";
    cout<<"\n";
    cout<<merge_sort(arr,10)<<"\n";
    for(int i = 0; i < 10; i++)
        cout<<arr[i]<<"\t";
    cout<<"\n";
    return 0;
}

Expected output for given array is 27 but i am getting 6. Plus my original array data got modified ( It's not sorted values has been changed).

Upvotes: 0

Views: 990

Answers (1)

Kostya
Kostya

Reputation: 1572

You need to replace int k = right by int k = left in function merge. I think expected output for this array is 27. Various implementations of merge sort had been discussed here implementing merge sort in C++

Upvotes: 3

Related Questions