Data Structures and Algorithms Show (1): Bubble Sort

AI has been getting closer and closer to human life. I believe it is a time for everybody to know more about the computer related technology. Just like we need to know how to do shopping or even works online which are not necessary skills half century ago. People need to be able to understand how the things going on inside all kinds of hardware like mobile phone, PC, vehicle and so on.

Of course, currently, Artificial Intelligence is not smart as human brain yet. In fact, the way that AI thinks is quite different with human brain. Although I believe Google and other tech giants are trying to make AI more like human brain, AI still deeply depends on data structures and algorithms which were designed by human. So, let us say, learn and understand data structures and algorithms will give you a opportunity to know how incredible results can be achieved by computers and software inside.

Unfortunately, the only thing can be understood by machines are 0 and 1. Human cannot think like a machine and vice versa. So some great engineers invented middle languages to fill the gap between human and machine. These languages abstract the commands can be performed by machines and let normal people have easier way to work with machines.

As a blogger who uses computer everyday, dig a little bit deeper than a normal user into machines' world would be helpful to the blog works. Personally, I reckon JavaScript is the best choice to start as everyone has a web browser to surf today. And I want to show and teach data structures and algorithms in a interactive way, to see if we can make the process more understandable. After all, those languages and conceptions are not totally same with stuffs in human world.

Enough blabs. Let us start with sort. It looks like that Sort is not a natural thing exists in the universe. Human sort things for many different purposes, such as management and science research. What is the core part of the sort? I bet you know it. Yes, it is comparison. The simplest example of sort is numbers, we have the ability to sort numbers in ascent or descent way. Computer do the sort things with the same method. Want a more complex example? How about a group of people? Of course, people are not number, how to work it out? Simple, Instead of sorting people, we sort people's attributes. Sorting by age, weight, or even name. It all depends on the requirement.

In machines, a group of numbers or objects(represented with a lot of 0 and 1) waiting for sorting are normally stored in a list. We call this list Array if all the members in the list all sit together like a line. Have to say, Array is the most fundamental data structure in this domain. We will start with the simplest(and the slowest maybe) sort algorithm which called Bubble Sort.

Just like the name, Bubble Sort compare two adjacent elements from the beginning of the Array, exchange two elements if the second one is smaller than the first one (or vice versa. depends on ascending or descending order we want). Then compare the second and third elements until the last two elements compared and exchanged if necessary. If you have (n) elements in the Array, repeat the process (n-1) times. And every time the biggest or smallest number will float to the end of the Array, which means the number does not need to be compared next time.

Now, the key part is coming, let us use D3 and AngularJS to show the whole process. I hope it is easy to explain the algorithm and can learn Bubble Sort, JavaScript, D3 and AngularJS from it.

for (var i = 0; i < list.length - 1; i++) {

for (var j = 0; j < list.length - 1 - i; j++) {

if (list[j] > list[j + 1]) {

var temp = list[j];

list[j] = list[j + 1];

list[j + 1] = temp;

}

}

}

Bubble sort is very simple sort algorithm and should be easy to understand. I have show the whole process of the sort and the example codes. I hope you can have an idea how computer do the magic for us.

If you are interested, you can press F12(on PC) to see the JavaScript source code in this blog page. In fact, to achieve the animation, D3 and AngularJS help a lot.

To let blogger support AngularJS, you need to modify the blog theme to put AngularJS libraries into the template. You can check my another blog to learn how to do it (http://notaiyet.blogspot.com/2017/06/make-your-own-javascript-codes-work-on.html). The following content should be included in the template:

<link rel="stylesheet" href="https://ajax.googleapis.com/ajax/libs/angular_material/1.1.0/angular-material.min.css" />

<!-- Angular Material requires Angular.js Libraries -->

<script src="https://ajax.googleapis.com/ajax/libs/angularjs/1.5.5/angular.min.js"></script>

<script src="https://ajax.googleapis.com/ajax/libs/angularjs/1.5.5/angular-animate.min.js"></script>

<script src="https://ajax.googleapis.com/ajax/libs/angularjs/1.5.5/angular-aria.min.js"></script>

<script src="https://ajax.googleapis.com/ajax/libs/angularjs/1.5.5/angular-messages.min.js"></script>

<!-- Angular Material Library -->

<script src="https://ajax.googleapis.com/ajax/libs/angular_material/1.1.0/angular-material.min.js"></script>

<script src="https://d3js.org/d3.v4.min.js"></script>

There is one more thing I want to mention: keep your blog page a backup somewhere. For some reason, blogger will change your HTML a little bit. In that case, some AngularJS tags may be moved to some unwilling places and cause some problems. But you always can go to the HTML editor page in blogger and paste correct HTML code from your backup and save it directly. Remember to check the preview page to confirm that "Compose" editor do not cause any damage to you.

Good luck to your digital diving journey!