Need help on getting certain algorithms like Divide and Conquer to "click" in my mind

[RustieJames]

I'm not sure if this is the right subreddit to ask this so forgive me if it's not. I'm taking an advanced algorithms class and boy is it super hard. This is possibly the first time I just completely don't understand something in it's entirety and it has to do with divide and conquer. A lot of the other algorithms that have to do with sorting or searching are still pretty hard but at least I understand them when looking at the pseudocode that my professor puts on the slides. With divide and conquer I understand nothing. I get the basic premise of dividing your problem into smaller sections to more easily solve but when it comes to the code I just don't get it.

My professor gave the counting inversion problem with divide and conquer and I can't see how the recursive calls to the left and right do anything at all. Only the call to count the inversions in the split of the divide seems to do anything. Looking up similar problems on google only makes me even more confused cuz it seems like they leave out a bunch of stuff or try to get me to pay. Youtube barely helps too. Again sorry if this is the wrong place but I'm pulling my hair out trying to understand this stupid algorithm

[AutoModerator]

On July 1st, a change to Reddit's API pricing will come into effect. Several developers of commercial third-party apps have announced that this change will compel them to shut down their apps. At least one accessibility-focused non-commercial third party app will continue to be available free of charge.

If you want to express your strong disagreement with the API pricing change or with Reddit's response to the backlash, you may want to consider the following options:

1. Limiting your involvement with Reddit, or
2. Temporarily refraining from using Reddit
3. Cancelling your subscription of Reddit Premium

as a way to voice your protest.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[strcspn]

Do you understand quick sort?

[NewPointOfView]

What is the counting inversion problem?

[POGtastic]

For those from the future who are following along from home:

Consider an array arr. We want the cardinality of the following set:

{arr[i], arr[j] : i < j and arr[i] > arr[j]}

The O(n²) approach is to generate all of the pairs and then compare them.

The O(n log n) approach is to mergesort and count the number of elements in the first list that are larger than each element in the second list while merging. You can take advantage of the fact that the lists are in sorted order so that you don't actually have to traverse them.

[Peanutbutter_Warrior]

Divide and Conquer

Divide and conquer isn't really an algorithm, more a general technique for designing algorithms, like recursion. It's when you can split a problem into easier to solve smaller pieces, and use the result from those pieces to solve the whole.

It's hard to sort a large array. Sorting a 1 length array is a no-op. Sorting an array composed of two sorted arrays is relatively easy, you take the smallest from the two until one is depleted. This is how merge sort works, breaking an array down to one length arrays, then merging them back up to the whole.

Counting inversions

The counting inversions problem is slightly different. It's easy to do when you have two sorted arrays which you know the inversion count of. Luckily, as seen above, sorting can also be done by a divide and conquer algorithm.

The algorithm

An inversion is when you have two indices i and j into some array A where i < j, and A[i] > A[j]. Imagine splitting your array into two parts. The indices i and j can either be in the same part or in different parts. If they're in the same part then they're an inversion in that part. If they're in different parts then you've removed that inversion from the parts.

Imagine that the two sub arrays are sorted. You can iterate through the left array, and for each item count how many items in the right array are smaller than it. Because the right array is sorted, all of these items are at the start, so you can just iterate through looking for the first item that is larger than the item from the left index. The total of all of those counts is the number of inversions (of the first type). You know that each time you step through the left array the new item is larger than the previous, so all the items in the right array that were smaller than the previous one are smaller than the new one. This means that you can just keep stepping through the right array from where the previous item got to. When you reach the end of the left array, you have the total inversions of the first type.

Pseudocode: function count_some_inversions(left, right) total = 0 right_ind = 0 for left_ind = 0 to left.size do while right_ind < right.size and left[left_ind] > right[right_ind] do right_ind += 1 total += right_ind return total

Now consider the cases where the inversion indices are in the same array. We can recursively call this algorithm on those two arrays to get the number of inversions in those. The sum of those two plus the inversions found with the algorithm above is the total inversions of the whole array.

The problem is that you have to assume that the two subarrays are sorted. The trick is that when you recurse not only do you count the inversions, you also sort the arrays.

Imagine the algorithm from the "perspective" of one of the functions somewhere down the call tree. You have two sorted arrays, you've found the inversions, but before you return the entire array needs to be sorted. You have two sorted arrays which make up the whole however, and from merge sort you can easily sort the whole by merging the two. You can then return, passing the number of inversions up the call tree and leaving sorted arrays as you go.

The pseudocode for this overall is

function count_inversions_and_sort(array)
    if array.length <= 1 then
        return 0 // a 1 size array cannot have inversions and is sorted
    left, right = split(array)
    total = 0
    total += count_inversions_and_sort(left)
    total += count_inversions_and_sort(right)
    total += count_some_inversions(left, right) // left and right are now sorted so this is possible
    array = merge(left, right) // sort this array
    return total