Data Structures and Algorithms Show(3): Insertion Sort

Insertion Sort gets its name because every element in the array try to find a position closer to the start position of the array. The movement is just like a insertion action. The sort process start from the second element in the array. if the element is smaller than those elements before it, then those elements will be shifted toward its position. As a result, this element can be inserted to the place which is empty after the shift. The sort process completes when the last element in the array go through the steps.

With the first glance, it may look like this sort algorithm that is better than Bubble Sort but worse than Selection Sort. Surprise enough, Insertion Sort is even a little bit better than Selection Sort.

Any way, we need to know that all these three sort algorithms are not using by most of the programs in our computer because they are not efficient enough. They all need two layers loops to compare and move elements. In the worse scenario, an array with n elements may need n*n times steps to achieve the result. It could be 1 million if n is 1000.

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

var select = list[i];

var insPos = i;

for (var j = i - 1; j >= 0; j--) {

if (select < list[j]) {

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

insPos = j;

}else{

break;

}

}

list[insPos] = select;

}

Data Structures and Algorithms Show (2): Selection Sort

In my last blog (http://notaiyet.blogspot.com/2017/07/a-fantastic-way-to-show-and-teach-data.html), we have a Bubble Sort Show to help us to understand what is bubble sort and the basic theory of sort action: comparison. Although bubble sort is a good example to explain the comparison during the sort process, it is not a good sort algorithm. You may have known the reason that there are too many times exchange operations happen from the beginning to the end.

If you have n elements need to be sorted, in the worst case, bubble sort might need n*n times' comparisons and n*n times' exchange operations.

Fortunately, Selection Sort can help a little bit with less exchange actions despite n*n times' comparisons is still a have to. 

In selection sort, there are n rounds of comparisons if n elements exist in the array. the first round comparison starts with the first element in the array. The position of smaller element during the comparison will be recorded. The position of the smallest element can be located after all the elements have passed through the comparison. Then the smallest element will be placed into first position of the array. The second round will start with the second element in the array and go through the same process. The sort is done when the last second element finish the comparison and the exchange. In worst scenario, selection sort only need n times' exchange, not n*n times. No doubt, This is a better sort algorithm then bubble sort. Although it is still not good enough.

So, finding out the smallest(or the biggest) element in the array is a key conception of Selection Sort. Now, we are ready for the Selection Sort Show. You will see how the smallest element can be located during the every round of comparison and be put to the right place.

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

var min = i;

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

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

min = j + 1;

}

}

// need to put the smallest element to the front if the front one is not the smallest one.

if (min != i) {

var temp = list[min];

list[min] = list[i];

list[i] = temp;

}

}

It is not difficult to realize that Selection Sort is a little bit faster than Bubble Sort, right?