Selection sort, is a technique which involves repeatedly "selecting" the (next)smallest element from the set of (remaining)unsorted elements in the total data set, and adding it to the end of a sorted set composing of all the previously found small elements (which will be smaller than the element we are trying to add) from the total data set.
As you can imagine, initially all the elements of the total data set are unsorted and we have to assume one of them to be the smallest. Naturally the first element of this unsorted set, which is basically the total data set, when we start, is a good place to make that assumption. So that leads to our step 1
- Assume the element at first unsorted position as the next smallest element that needs to be found and remember its position as well. This is the initial assumption.
Now obviously, there is no guarantee that our element at first unsorted position will be the next smallest element in the unsorted part of the total data set. We need to validate that assumption by comparing our assumed next smallest element with the rest of the elements in the unsorted part of the total data set, which leads us to step 2
- Compare your assumed next smallest element with rest of the elements, one at a time.
So what if we found an other element in the unsorted part of the total data set, that is smaller than our assumed element ? Well, simple. Just update our assumption(var) of the of the next smallest element and its position
But, what if you found an other one ? Well just update your assumption again. Keep updating your assumption(var) of the next smallest element and its position, every time your found a element smaller than your currently assumed next smallest element until you reach the end of the list. Now, let us formalize this as our step 3:
- For every element smaller than your assumed next smallest element that you encountered before the end of the unsorted part of the total data set, update your assumption of the of the next smallest element and its position.
- Swap the next smallest element found (no longer assumed) with the initially assumed smallest element in the total data set.
At this point we have 1 element, which is the smallest element of the entire set at the start of our set, initializing our sorted set. So it is time to find the next smallest element from our unsorted set, to add to our sorted set, usually positioned at the starting or left part of the total data set.
All that is left at this point is to repeat all of the above steps with the assumption that the first element of the unsorted part of the total data set (in this case the second element of the total data set) is the smallest element.
This animation shows the steps in action (green arrow is comparisons, red is swaps):
Very often I find it easier, if we can understand, how the core steps of the algorithm interacts with a very small data set , then it will make it much easier to understand the whole algorithm.
So watch the demo below to understand the basic concept of SelectionSort algorithm:
How many times do we have to repeat this ?
The obvious answer is, till there are no more unsorted elements left in the total data set. But since, we know the algorithm keep finding the smallest position with every iteration, and that when our sorted part of the total data set, encroaches the element just before the last element, we can be assured that the last remaining element is the next smallest element, and there will be no need to search any further. So that will be a good point to stop our search for the next smallest element.
This animation shows the steps in action (green arrow is comparisons, red is swaps):
Very often I find it easier, if we can understand, how the core steps of the algorithm interacts with a very small data set , then it will make it much easier to understand the whole algorithm.
So watch the demo below to understand the basic concept of SelectionSort algorithm:
How many times do we have to repeat this ?
The obvious answer is, till there are no more unsorted elements left in the total data set. But since, we know the algorithm keep finding the smallest position with every iteration, and that when our sorted part of the total data set, encroaches the element just before the last element, we can be assured that the last remaining element is the next smallest element, and there will be no need to search any further. So that will be a good point to stop our search for the next smallest element.
To summarize, the algorithm, watch the my video below about the workings of a SelectionSort :
To convert, this SelectionSort algorithm into a program, watch the my video below about Writing a SelectionSort Program:
To convert, this SelectionSort algorithm into a program, watch the my video below about Writing a SelectionSort Program:
