Thus far we have seen several examples of divide and conquer
algorithms (Merge Sort, Quick Sort, Trominos Tiling, Schoolbook
Integer Multiplication, Karatsuba’s Algorithm, Maximum Sum
Subarray), and showed different ways to use the base case,
divide, conquer, combine
anatomy to solve this diversity of
problems, and use the Master Theorem to help use reason about
running time. We additionally showed some examples where providing
additional return values can help us to write our algorithms by
improving running time (Improved Maximum Sum Subarray) or enabling
correctness (Binary Tree Diameter).
Next, for this reading (our final one on divide and conquer) we
will continue on this theme of more tasks per stackframe saves
time overall
by looking at algorithms where sorting will be
helpful. More precisely, these next algorithms we discuss will
have similar behaviors in that they are not themselves sorting
tasks (i.e. our target output is not a sorted list), but sorting
along the way
will be very useful.
We’ll look at one example in this reading, then a second example in class (teaser, the one we’ll discuss in class is Nathan’s FAVORITE divide and conquer algorithm).
For the reading, we’ll be writing an algorithm to determine the number of inversions in a list. We define a list inversion as the number of out of order items in a given list. Suppose we wanted a list to be sorted in ascending order (i.e. smallest to largest). In that case a list inversion is a pair of indices i<j where arr[i]>arr[j], in other words a pair of values where the larger one appears before the smaller one. The number of inversions in a list is the count of all such pairs.
For example, the list [1,3,2] has 1 inversion, that being the pair of indices (1,2), because the values 3 and 2 are out of order.
The list [2,3,1] has 2 inversions, those being the pairs of indices (0,2) and (1,2), because the value 1 is out of order with the values 2 and 3.
The list [3,2,1] has 3 inversions, those being the pairs of indices (0,1), (0,2), and (1,2), because all pairs of values are out of order.
The list [1,2,3] has 0 inversions, because all items are in order.
To help us gather an intuition, all of the following are true of list inversions:
n choose 2)
We will leverage this last statement to produce an algorithm. To find the number of list inversions, we will do the following:
To put this in psuedocode, we’ll get:
public int inversions(List arr){ inversions = 0 for(int i = 0; i < arr.size(); i++){ for(int j = i+1; j < arr.size(); j++){ if(arr[i] > arr[j]){ inversions += 1; } } } return inversions; }
Given the two nested for loops, this algorithm will run in time O(n^2). Now let’s use divide and conquer to bring this down to O(n \log n)!
To write our divide and conquer algorithm, we will look at one
more way of thinking about an inversion in a list. From our
definition of an inversion, that i<j but arr[i]>arr[j], we can see that the
number of inversions involving index j paired with a smaller index matches
the number of values j must
overtake
to sort the list. So if j is involved in 3 inversions, then there are 3 values
that j should overtake
when sorting the list!
Let’s see some examples of this.
For the list [1,2,4,3] we will look at j=3 (so the value 3). In this case 3 participates in one such inversion (with index 2), and in the sorted list [1,2,3,4] its value overtakes just one other value.
In the list [4,3,2,1] the index 3 is the larger index in 3 inversions, 2 is the larger index in 2 inversions, 1 is the larger index in 1 inversion, and 0 is the larger index in 0 inversions. Comparing to the sorted list [1,2,3,4], the value 1 overtakes 3 other values 4, 3, and 2), the value 2 overtakes 2 other values (3 and 4), and the value 3 overtakes one value (4).
By way of analogy, we could consider this like a formula 1 race. If we have 4 cars racing that begin in the order [4,3,2,1], and the final race results are [1,2,3,4], then it must be that car number 1 overtook all three other drivers, car number 2 overtook numbers 3 and 4, etc.
Our divide and conquer algorithm will work by counting the
total number of these overtakings
when sorting a list. To
highlight the important insight here for today, the primary
structure of this algorithm will just be a sorting algorithm. On
top of that sorting algorithm, we will observe how many values
each element overtakes
throughout.
To get us started in designing this algorithm, we’ll begin with our favorite divide and conquer sorting algorithm - Merge Sort!
As a refresher, here are the base case, divide, conquer,
combine
steps for merge sort:
Now, for each step, we want to recognize when we have an element overtake another:
With all of these insights, we can now give our divide and conquer algorithm!
(Note to reader: there is nothing following the walkthrough of the example below, so feel free to stop reading once you have the idea down!)
Let’s look at what this algorithm does for the list [1,3,5,7,6,4,0,2]
After dividing we will have two sublists, the left being [1,3,5,7], and the right being [6,4,0,2]. Note that the left sublist is already sorted, and so it has 0 inversions. After sorting, the right sublist will be [0,2,4,6]. To get to this order both of 0 and 2 had to overtake both of 6 and 4, and 4 must overtake 6. Therefore so it has 5 inversions.
This means that after conquering we have leftInversions=0 and rightInversions=5, and our left and right sublists are both sorted.
Finally we need to combine. To do this we’ll merge [1,3,5,7] with [6,4,0,2]. Let’s step through this carefully.
====Before merging==== left = [1,3,5,7]
right = [0,2,4,6]
inversions = 5
we also have a list we’re merging into that we’ll call merged. It is currently empty
====First element====
The first element removed will be the value 0 from the right sublist. When we do this, 0 has now overtaken every single value in left, which is 4 values. We therefore add 4 to our count of inversions.
left = [1,3,5,7]
right = [2,4,6]
inversions = 9
merged = [0]
====Second element====
The next element removed will be the value 1 from the left sublist. When we do this, 1 was already the leftmost value, and so we do not add to the number of inversions.
left = [3,5,7]
right = [2,4,6]
inversions = 9
merged = [0,1]
====Third element====
The next element removed will be the value 2 from the right sublist. When we do this, 0 has now overtaken every single value in left, which is 3 values. We therefore add 3 to our count of inversions.
left = [3,5,7]
right = [4,6]
inversions = 12
merged = [0,1,2]
====Fourth element====
The next element removed will be the value 3 from the left sublist. When we do this, 3 was already the leftmost value, and so we do not add to the number of inversions.
left = [5,7]
right = [4,6]
inversions = 12
merged = [0,1,2,3]
====Fifth element====
The next element removed will be the value 4 from the right sublist. When we do this, 4 has now overtaken every single value in left, which is 2 values. We therefore add 2 to our count of inversions.
left = [5,7]
right = [6]
inversions = 14
merged = [0,1,2,3,4]
====Sixth element====
The next element removed will be the value 5 from the left sublist. When we do this, 5 was already the leftmost value, and so we do not add to the number of inversions.
left = [5,7]
right = [6]
inversions = 14
merged = [0,1,2,3,4,5]
====Seventh element====
The next element removed will be the value 6 from the right sublist. When we do this, 6 has now overtaken every single value in left, which is now just 1 value. We therefore add 1 to our count of inversions.
left = [7]
right = []
inversions = 15
merged = [0,1,2,3,4,5,6]
====Last element====
The last element removed will be the value 7 from the left sublist. When we do this, 7 was already the leftmost value, and so we do not add to the number of inversions.
left = []
right = []
inversions = 15
merged = [0,1,2,3,4,5,6,7]
At this point, our merge step is done, so we return the merged list as well as the value 15.