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?