CODEWITHSUNDEEP
c++algorithmmergesort
Mutating Algorithm
Mutating Algorithm

Reputation: 2758

Count Inversions using Merge Sort in C++

So I understand the general idea behind counting inversions in an array using merge sort. You recursively count the number of inversions in the left subarray and right subarray during the merging process.

Here is some code I wrote to do that.

int count_and_merge(vector<int>& array, const vector<int>& left_subarray, const vector<int>& right_subarray) {

    vector<int> merged {};

    array.clear();

    int left_index = 0, right_index = 0, sorted_index = 0;
    int inversions = 0;

    while(left_index < left_subarray.size() and right_index < right_subarray.size()) {

        if(left_subarray[left_index] <= right_subarray[right_index])
            array.push_back(left_subarray[left_index++]);
        else {

            array.push_back(right_subarray[right_index++]);
            inversions += left_subarray.size() - left_index;

        }

    }

    while(left_index < left_subarray.size()) array.push_back(left_subarray[left_index++]);
    while(right_index < right_subarray.size()) array.push_back(right_subarray[right_index++]);

    return inversions;

}

int count_inversions_and_sort(vector<int>& array) {

    if(array.size() <= 1) return 0;

    int n = array.size();

    vector<int> left_subarray(array.begin(), array.begin() + n / 2),
                right_subarray(array.begin() + n / 2, array.end());
    
    int left_subarray_inversions  = count_inversions_and_sort(left_subarray),
        right_subarray_inversions = count_inversions_and_sort(right_subarray);

    return left_subarray_inversions + right_subarray_inversions + count_and_merge(array, left_subarray, right_subarray); 

}

What I'm having difficulty understanding is why it's necessary to clear the array in the count_and_merge function before appending elements to it? Is there another way to do it without clearing the array? I ask because I'm used to writing merge sort with array[sorted_index++] = left_subarry[left_index++]

Upvotes: 2

Views: 271

Answers (1)

Y.T.
Y.T.

Reputation: 2749

Why it's necessary to clear the array in the count_and_merge function before appending elements to it?

It is necessary in the shown example since you append elements after array. However, you want array to remain the same length but be sorted.

I ask because I'm used to writing merge sort with array[sorted_index++] = left_subarry[left_index++]

I don't see a reason why you can't use that instead of std::vector::push_back(). The original content in array isn't really important since the needed information is contained in left_subarray and right_subarray. Therefore, you can directly overwrite to array. If fact, if you use this implementation, you don't even need std::vector::clear() beforehand.

Upvotes: 1

Related Questions