The selection sort is a simple sorting algorithm. As its name indicates, it selects the lowest element from the list and moves it where it should be.
-
Start with the element in position 0.
-
Find the minimum item in the rest of the array. If a new minimum is found, swap them.
-
Repeat step #1 and #2 with the next element until the last one.
For implementing the selection sort, we need two indexes.
link:../../../src/algorithms/sorting/selection-sort.js[role=include]-
Converts any collection to an array or clone existing array.
-
Visit all elements in the array starting from the 1st element (index 0).
-
Everything to the left side is considered sorted in its final position. So, select
leftas the initial minimum value. -
Compare the
selectionto every element to the right side. -
If it finds a value smaller than the selection, then update the
selection. -
Put the next smallest item to its final position
|
Tip
|
Selection sort minimizes the number of swaps. It does one swap per iteration while insertion sort and bubble sort could swap many times with the same array. |
One index is for the position in question (selection/left) and another for finding the minimum in the rest of the array (right).
-
[In-place]: ✅ Yes
-
[Stable]: ️️❌ No
-
[Adaptive]: ️️❌ No
-
[Online]: ️️❌ No
-
Time Complexity: ⛔️ part01-algorithms-analysis.asc O(n2)
-
Space Complexity: ✅ part01-algorithms-analysis.asc O(1)
Why selection sort is not stable?
To recap, stable means that items with the same value keep their initial position.
Let’s see what would happen with the selection sort if we (select) sort the following array 2, 5, 2, 1. To distinguish them, let’s say 2a and 2b, so 2a, 5, 2b, 1.
Initially, we select the first element, 2a and check if there’s anything less than 2 in the array. We find out that position 3 has an item with a smaller value (1), so we swap them.
Now, we have: 1, 5, 2b, 2a.
There you have it, 2b now comes before 2a.