Mergesort

https://www.dot.state.mn.us/zippermerge/images/zippermergecrop.png

Have u seen merging of traffic from two lanes into one?  You may understand that in principle, cars on both lanes are supposed to interleave in an alternate manner into the single lane, but in reality, likely the more aggressive, impatient drivers will get to go first into that lane. Well, that's the idea in mergesort. You have 2 sorted lists, and you are to move them all into a single sorted list. Frontmost elements from both lists are compared, and the 'stronger' one (however you define that) go into the single list.

Here's a trivial example. Suppose you have 2 lists, where in each list, you have just a single person. You want to move them both into a single list, sorted by height. It's simple - simply check who is taller; move that guy first into the single list.

For example, the guy on the left is shorter, so he goes in first.

followed by the taller guy in the other list.

Now consider the case where each list contains 2 guys in ascending order. Again, we compare the frontmost (or leftmost) guys from both lists. The sorter one goes first.

The frontmost guy on the right list gets to go first of course. Now the next guy in the right list become frontmost, and he will be compared with the current frontmost guy in the left list.

The guy in the left list gets to go in next. And we continue the comparison.

The guy in the left list goes next.

We then clear up the list on the right - move in the remaining guy, and we have a family.

Hence, that's the key idea in mergesort - take 2 sorted list, simply build a single sorted list by taking the shorter of the frontmost elements in both lists. In Python, this logic translates as follows:

        i=0  # index to the current frontmost element in left list
        j=0  # index to the current frontmost element in right list
        k=0 # index to current position in output list
     
        # compare the frontmost elements in left and right list
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]          # add the frontmost element from left list
                i=i+1                              # index to a new frontmost element  in left list
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1                  # update index to current position in output list


And suppose we are done processing the right list, but there are still elements left in the left list. We need to simply funnel those remaining elements into the output list, one after another.  No comparison or check is needed as those remaining elements are no smaller than any element in the output list. The code looks as follows:

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

And the same logic applies should there be elements remaining in the right list:

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1

The above code can be contained into a single function, with the header say as follows:

def mergeSort(lefthalf, righthalf):

Mergesort with a Single List


In real application, of course, we do not regularly get 2 sorted lists. Likely, we get a single list of random items and asked to do a sort on it. How do we do a mergesort with a single list? Consider the following:

There is only a single list, but we can think of it as 2 sublists:

And for each of the sublists, we can do further subdivision, producing more sublists:

Eventually, we have sublists splitting into smaller sublists comprising of only a single element each, and eventually no more recursive subdivision can be done. We now can start merging sublists in a bottom up manner.

Note how the single-element sublists at the bottom of the tree get to be merged into a single sorted sublist 1 level above:

Continue the bottom-up merging:

Eventually you have 2 sublists to be merged, as show below:

Merging those 2, we get the overall sorted list, as follows:

The above recursive logic can of course be implemented as a recursive function. Assuming a split down the middle at each subdivision, we have the following function:

def mergeSort(alist):

    if len(alist)>1:
        mid = len(alist)//2                 # split at this index
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)               # recursive call
        mergeSort(righthalf)

        alist = mergeSort(lefthalf, righthalf)   # this merge two lists into a single sorted list

    return alist;

Bubble Sort

https://nakedsecurity.sophos.com/2017/05/22/news-in-brief-bitcoin-price-bubbles-up-uber-uses-ai-to-boost-its-take-wannacry-hero-censures-tabloids/

What do you notice about bubbles? Played around with soapie bubbles in the bathtub? Bubbles float to the top, and pop. Imagine that bubbles float to the top in order of ascending size. First, the biggest one will go up and pop. Then the next larger one and so on. That's the basic idea in bubble sort, probably the most primitive form of sorting algorithm available at your disposal.


Let's explore this algorithm with a simple example. Suppose we have a list of 5 persons, as shown below. We want to sort the persons in order of increasing heights from shortest to tallest, left to right. With bubble sort, the tallest one will go to the last position first. To do this, we start at the first position - we fix our eye there - and compare the person at that position with the one at the next. We do a swap if the current person is taller than the next.

We go on with the same comparison at consecutive positions. No swap however between the 2nd and 3rd position, as the one at the 3rd position is taller than the one at the 2nd.

Should we now swap between position 3 and 4? Yes, as we can see below.

Finally, we check between position 4 and 5 - the eye at position 4. Should a swap be done? Obviously - the 4th guy is way taller than the little guy in the 5th spot.

Eventually the tallest guy will have bubbled to the last position. That position is now fixed - you don't to bother with that anymore.

You now need to fix the position number 4. The next biggest guy needs to be there. To do that we just repeat the process above, but this time round, we iterate only till we are at position 3 (instead of 4 as in the first round).

The bubbleSort logic can be translated to the following Python code:

def bubbleSort(nlist):
    for passnum in range(len(nlist)-1,0,-1):
        for i in range(passnum):
            if nlist[i]>nlist[i+1]:
               swap(nlist, i, i+1)

where swap is a function (you must define it) that swaps the position i and i+1 in the nlist.

Note that the outer loop iterates N times, where N is length of the data list, while the inner loop will go N-1 times during the first outer iteration, then N-2 during the second outer iteration, and so on.

Linked List

In another post, I talked about how an array can be used to implement a list ADT. Another way to implement the ADT is with a linked list, the implementation of which relies on pointers or memory references. Hence, to do a linked list, first and foremost, you have to understand the concept of pointers.

A pointer is a variable that stores the address of another variable. To understand this, consider a person as a variable. Suppose a gal named Betty stores a certain integer value, say the latest sales figure. Betty is then a 'normal' variable, one that hold an actual value of interest. Now consider a certain guy named Mat. He does not hold such value. He cannot tell you what's the latest sales count. He can however point you to Betty; he knows Betty's address and hence can point you to her. Mat is a pointer variable.

In C or C++, we can declare a pointer mat pointing to an integer variable betty as shown in the example below:

int betty;
int *mat = &betty;

'&' is to be read as address of, and 'int *' as 'pointer to integer'. Hence mat is a pointer to integer that stores the address of betty.

In a language such as Python, there is no explicit syntax for pointer or address. However, objects such as list or dict in Python are all implemented as pointer variables, and so when you do a copy operation such as follows, you are really copying addresses, not the actual data.

a = [1,2]
b = a

If you change the value of b, eg. with a statement such as follows:

b[0] = 5

the corresponding value in a will change too, since a and b have the same address.


Now, imagine this. Suppose each person has 2 values. One is an actual value, say his/her sales figure, and another is a pointer value that points to another person. We can achieve this in C or C++ with a struct that looks something like as follows:

struct Salesperson {
    int sales;
    Salesperson *next;
    }

There is no struct in Python, but we can use a dict to achieve a similar effect:

betty = { 'sales': 0, 'next': None}

Hence, as shown in the picture below, Alif holds a sales value and at the same time, he points to Mat. Mat holds his own value and he is pointing as well to Betty. What we get is a linked list.

A linked list consists of nodes (the persons above), linked up by pointers. The first node in the list (Alif in the pic), is the header. The last node (Betty) points to no other node (in python, we write it as None). What we have in the computer memory is something like as follows:

Unlike an array, consecutive locations in a linked list is unlikely to be in contiguous memory location, as shown below:

Operations on Linked List


Now, consider 2 basic operations on a linked list: 1) inserting a new node, and 2) deleting an existing node. We have of course to start from nothingness - a blank linked list, one where the header points to nothing:

In Python, this blissful state of nothingness would be created as follows:
header = None

Insertion into an Empty List

Naturally, the only meaningful operation in this state is the addition of a new node. Now suppose a node 'Ben' to be inserted:



ben = {'name': 'Ben', 'next': None}

Note that I choose to focus on just 2 fields  - a name and a pointer that points to the next node. The next value here is None since 'Ben' is by itself. To make 'Ben' be part of the list, since the list is still empty, all we need to do is to make header points to it:

header = ben




Insertion at the Head

Now suppose we have another node to be added:

alif = {'name': alif, 'next': None}



'Alif' can be after 'Ben' in the list, or it can be before, but to maintain an alphabetical order, it should of course be in front. We check on this with the following conditional:

if header['name'] > alif['name']:
 



If the above condition is true, and it is of course true, then we need to do some stitching: stitch the nodes together such that 'Alif'' is pointing to 'Ben', and header is pointing to 'Alif'.  One must be careful not to break up the list. The following order of action is correct:

• make 'Alif' points to 'Ben'
• make header points to 'Alif'

Why would it not work if you were to reverse the order of the operations?

Inserting at the End

Suppose now we have a node 'Charlie' to be inserted into the list:

You note that 'Charlie' is not less than the node currently pointed to by the header. So insertion at the head is out of question.You need to do some hard work then; track through the list to find the rightful position for 'Charlie'. You note that 'Alif' is not the last node..

and that the next node do not have a name greater than 'Charlie'. 

So you move on to 'Ben'. You can see that 'Ben' is currently last in the list. It means that ''Charlie' will be the new last.

It's simple to insert a node to the end of a linked list. Simply point the next var in the current last node to the node to be inserted, as shown below:

Insertion Somewhere in Between

We now a list of 3 nodes. Let's go further - we shall add one more node, 'Bung'.

Again, we start by placing a tracker at header, and we check if 'Bung' deserves to go in front there. It does not. So we start to iterate through the list until we find the right spot. We note that 'Alif' is not the last node, and the next node is not with a name bigger than 'Bung'.

So we move the tracker to the next node, and apply the same check. This time, with the tracker at 'Ben', we do note that the next node will be with a name bigger than 'Bung'. So we know that 'Bung' must be inserted between the current node and the next.

So some stitching work needs to be done here. We first stick 'Bung' to next node - 'Charlie' -,as shown below:

Then we make 'Ben' point to 'Bung' instead of to 'Charlie':

We are done here.

Permutation

Given a list or a sequence of items, a permutation of the list is a certain re-ordering of the items within the list. Hence, if you have a list like [1,2,3,4,5], its permutations would be: [2,1,3,4,5], [1,2,3,5,4], [1,2,5,3,4] and so on. In fact, you can permute anything, as exemplified by the pictures below:

  

Now, given a list with N elements, how many possible permutations are there? Convince yourself that it is N! (that is, N factorial). For example, if N=3, then you have 3! = 3x2 = 6 possible permutations. If you have N=100, then the number of permutations is 9.332621544 E+157, which is of course an absurdly large number.

What I want to focus on in this post is the question of how do we generate all possible permutations of a list?  Consider the problem in the context of my 3 pens. How do I permute my 3 pens?  I can start with 1 pen; it can be any one of the 3 pens:

Say I start with the green pen at position 1.

 The black pen can go to position 2.

 Or it can be the white pen occupying position 2. In other words, in this position, I can consider any pen except the green pen itself.

Suppose I choose the black pen to be in position 2. Then in position 3, I can consider every pen, except for the first and second pen. And of course, since I have only 3 pens, that can only be the white pen. 

So the steps are as follows, for a 3 pen permutation:

The logic above should work. Only problem is that it's hardcoded for N=3 list. In the event of different N, we will need to change the code, the instructions. In fact, anything hardcoded is undesirable in a code, especially in our context here. We need something better. How do we go about doing this, doing without hardcoding?


Permutation through Recursion

Let's consider what logically happen in the course of a permutation. What can be the logical structure of the process? Suppose I label my pens as a, b and c. I can visualize permutation to be a tree structure, as follows:

Think of the tree as comprising of nodes connected by edges. At the root in the picture above, we have "a b c", the list of pens that we are to permute. 3 possibilities for the starting position, as denoted in the second layer of the tree: "a b c", "b a c" and "c b a". "b a c" is derived from "a b c" by swapping a and b, and "c b a" by swapping a and c. I need to explicit about it all, be clear about all these details since everything later will need to be transferred to code.

Now for each node in the second layer, freeze the first position (it's underlined) and consider the  sublist beyond the first position. For example, for node "a b c" in the second layer, we consider only the sublist "b c"; a is frozen in its place That node has 2 child in the 3rd layer - corresponding to the "b c" and "c b", where "c b" is derived from "b c" by swapping b and c. Similar processing applies for other nodes in the second layer: freeze the first position, recursively process the remaining sublist.

Hence, permutation can be done recursively. How will the recursive tree look like when we have 4 pens (or items)? The tree will look bigger of course.

In fact, it will grow factorially with increasing list size.

In pseudocode, the permutation task can be laid out as follows:

      permute(item_list, left, right):

                  if  left == right:

                       display item_list

                  else

                        for i from left to right:

                              temp_list = item_list

                              swap items in temp_list at index i and index left

                              permute(temp_list, i, right)

Ok so far?

I have another example to illustrate the concept above. Consider a 4-a-side football team:

We have 4 positions - striker, midfielder, defender and goalkeeper - and we have 4 players - blue guy, black guy, red hunk and a guy with blue head and black body (mixed blood). We need to make sure that everyone is playing at the optimal positions. The only way (computationally) is to have everyone try every possible position - in other words, try out every possible permutation of the players.

So we do it in this way: 

4 possibilities for the striker position: red guy be striker, red guy swaps position with black guy, red guy swaps with blue guy and red guy swaps with mixed-blood guy, as shown above.

Next, for each of these possibilities, we consider only the midfield, defender and goalie positions. Apply the same reasoning to the midfield position, as we did to the striker position.  Consider the case below: there are 3 possibilities for the midfield positions - black guy at midfield, black guy swaps position with blue, black guy swap positions with mixed-blood. Then for each of those 3 possibilities, we continue recursively the same logic.

Heap Algorithm

A different permutation algorithm, one that is usually more efficient implementation-wise, is that by Heap (1963).  I will illustrate the main idea with the footballing example:

Let's fix the goalie position. Form all permutation of the other 3 positions - striker, midfield and defender.

After generating all possible permutations of that first 3 positions, say we have as follows (actually we do have exactly as follows, as shall be seen later):

Now swap the goalie position with the striker - goalie (mixed-blood guy) becomes striker, and the red guy becomes goalie.

Now again, form all possible permutations of the first three positions - striker, midfield and defender.

Repeat the process above, a number of times, as codified in the following algorithm, the so-called Heap algorithm:

In the pseudocode above, permute(L,N) forms a permutation of a list L of size N.

Now, on to a more technical explanation. To permute a list L =  <L_1, L_2, ..., L_N> of size N, we iteratively do the following: recursively permute a sublist <L_1, L_2, ... L_(N-1)>. After the permutation of the sublist, we swap L_N with one of the elements in the sublist.  

The tricky part, somewhat non-intuitive part in the algorithm is that of choosing the element in the sublist to swap with.  We need to make sure that someone who had already tried the goalie position before do not get selected to be the goalie again. Heap (1963) provided the following rules:

• If N is odd, replace L_N with L_1
• If N is even, replace L_N with L_i where i is the iteration number.

To see these rules in action, consider the following permutations, where the list, L = <1,2,3>, is of size N=3.

The numbers in blue on the right hand side are the iteration indices. At the first iteration, iteration 1, we permute the sublist <1, 2>. Since only 2 elements involved then, its just a matter of swapping the two. So, the list becomes <2,1,3>.  We then swap the last element in L, 3, with the first, 2, and we get L=<3,1,2>.   Next, in the second iteration, we permute the sublist <3,1> and L becomes <1,3,2>. Swap 2 with 1 and we get L=<2,3,1>. In the last iteration, do a permutation of <2,3> and we get L = <3,2,1>.  You can see that the number of permutations is 6, which is the factorial of 3. 

Now, consider the case where N=4.

One more iteration is missing in the picture above. But what is to b noted, in this case, N an even number, the swap at each iteration must be between L_N and L_i, where i is the current iteration number.

What makes the Heap's swapping rules tricky is that it is unclear why it work. The rules must be such that the swap will put an element which has never been last before in the last position. Or the question is: How in the world do you make sure that an ex-goalie does not become a goalie again??? Let's visualize the movement of the elements for different values of N.

Consider the case of N=3.

after iteration 1 : 2 1 3

after iteration 2 : 1 3 2

after iteration 3 : 3 2 1

Numbers in the last position are in blue, and numbers in red are those that have been in the last position before. Note that the first element, after each iteration except for the last one, is always 'free', that is, it has not been a goalie before.

In the case of N=4, we have the following:

after iteration 1 : 3 2 1 4

after iteration 2 : 1 2 4 3

after iteration 3 : 4 3 1 2

after iteration 4 : 2 3 4 1
Notice how at every i-th iteration, the i-th is free - occupied by a black digit, one that had never been a goalie before.

Now, lets go further, to N=5:

after iteration 1 : 2 3 4 1 5

after iteration 2 : 3 4 1 5 2

after iteration 3 : 4 1 5 2 3

after iteration 4 : 1 5 2 3 4

after iteration 5 : 5 2 3 4 1

Again, as we so earlier for the case of N=3, after every iteration, except for the last one, the 0-th position is free.

Similar observations (as per even case) follow for the case of N=6 and N=8, as shown below:

N = 6

after iteration 1 : 5 2 3 4 1 6

after iteration 2 : 1 2 3 4 6 5

after iteration 3 : 6 5 3 4 1 2

after iteration 4 : 1 5 2 4 6 3

after iteration 5 : 6 5 2 3 1 4

after iteration 6 : 4 5 2 3 6 1

N = 8

after iteration 1 : 7 2 3 4 5 6 1 8

after iteration 2 : 1 2 3 4 5 6 8 7

after iteration 3 : 8 7 3 4 5 6 1 2

after iteration 4 : 1 7 2 4 5 6 8 3

after iteration 5 : 8 7 2 3 5 6 1 4

after iteration 6 : 1 7 2 3 4 6 8 5

after iteration 7 : 8 7 2 3 4 5 1 6

after iteration 8 : 6 7 2 3 4 5 8 1




Further Reading on Heap Algorithm

• Ruslan Ledesma Garza, Why does Heap's Algorithm work?http://ruslanledesma.com/2016/06/17/why-does-heap-work.html
• Martin, Eric. "Notes on Cryptarithm Solver and Permutations." Principles of Programming. University of South Wales,  retrieved 21 Jan 2018. https://webcms3.cse.unsw.edu.au/COMP9021/15s2/resources/1544
• Permutation Generation Methods. R. Sedgewick, Computing Surveys, 9(2) (1977), pp.137-164