selection sort

The key to Selection Sort is to the find the exact element for every place in the array that you are sorting. In detail, if we are to sort an array into ascending order, we can divide the whole procedure into the following steps:

1. find the smallest element in the array, and place it in the 0th place;
2. find the second element in the array, and place it in the 1st place;
3. find the third element in the array, and place it in the 2nd place;
4. ….
5. find the second largest element in the array, and place it in the penultimate (last but one) place;
6. now we have reached the end of the array, and we are guaranteed that the largest element is actually in its proper place. And we’re done!

In essence, the entire procedure can be summed up as: first, select the smallest element in the unsorted array; second, exchange that element with the leftmost element, so that the selected element is in its right place in a sorted array; third, continue the process with the unsorted array, until you reach the end of the array. In simpler terms, it is just select and sort; that’s why it’s called selection sort.