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.