Bubble Sort

Bubble Sort

Bubble sort, derives its name by drawing an analogy between how the biggest elements in the data set "bubble" up to the end of the list, similar to how bubbles raises up in water.

The process involves comparing each element with the one immediately to the right of it and swapping them if the one on left happens to be bigger than the one in right, starting with the first element. Now you repeat the step with the second element, third element and so on until you reach the end of the list. We will call this single trip from the first element to the last element as a "pass".

To summarize, the core of our algorithm please take a look at the steps below:

When our current index (=ci) is pointing to element at position k, that is larger than element at k+1 position

                                                                                       compare
                     Large Element at position K  ⥨ Element at position K+1
                                     ↑
                                          current index

Then, we move element at position k, to position k+1, and element at position k to k+1.

                                                         swap
                     Element at position K  ⥨  Large Element at position K+1
                            ↑
                                   current index 

Then, we move our current index to point to position k+1 and compare it with whatever is next to it, in k+2 position

                                                                                            compare
                     Large Element at position K+1  ⥨  Large/small Element at position K+2
                                 ↑
                                             current index moved

However, When our current index is pointing to element at position k, that is smaller than element at k+1 position
                                                   compare
                     Element at position K  ⥨ Large Element at position K+1 
                                     ↑
                                                       current index

  
Then, we simply move our current index to point to position k+1 and compare it with whatever is next to it, in k+2 position

                                                                                                compare
                     Large Element at position K+1  ⥨  Large/small Element at position K+2
                                 ↑
                                             current index moved



So, the steps involved for current index, ci pointing to k are :

1. Compare element at position k with one at position k+1 the one next to it, where k is anywhere between 0 and the last element
2. If value at position k is bigger than value at position k+1, swap value at position k with value at k+1
3. Now, set your ci to k 
4. Repeat step 1 to step 3, until you reached the end of the list.

At the end of the first pass, you will end up with the biggest element of the data set at the end of the list, since with each swap in the first pass, we made sure that we are positioning the biggest element to the right, and then moving it to the right again when we compare it with the element to the right of it, and found it to be bigger. So at the end of the first pass, the biggest element of the data-set "bubbled" up to the end of the list.

This bubbled up biggest element at the last position will now, be the first element of a sub-set of elements, we will refer to as "sorted" set going forward.

Now, we repeat the pass, starting with the first element, and ending with the element right before the last element.

It will be of great help if you can have a look at the animation below to understand the workings better.(green is comparisons, red is swap, yellow line separates the sorted part (to right of the line) from the unsorted part (to the left))

Now, why are we stopping at the element before the last element ?

Well, why do you want to do anything with the last element which we already established is the biggest element of the set ?

So at the end of second pass, we will obviously end up with the second biggest element at a position towards the end of the list. We will call these two elements as part of the sorted set.  So at the end of the second pass, the second biggest element of the data-set "bubbled" up to the end of the list, next to the first biggest element and became part of the so-called sorted set. This new (second)biggest element will now be the first element of the sorted set, along with the previously found (first)biggest element.

Naturally, it should occur to us now, that if we repeat the pass, enough times, that is until the 2nd element from left is part of the sorted set, we have ourselves a sorted set.

This obviously means that the we have to remember the position of first element in the sorted set, and stop the sorting when that position is 1 (since arrays start at position 0, element 1 will be the second position). At that point the element position 0 will be smallest of all, since sorted set will have all the biggest elements we found so far, and we will have a fully sorted set in our hands

Nothing, can obviously beat the demonstration of it, so here we go :

The steps involved in the conversion of the above technique into a program are explained in the video below: