If I take an array of numbers:
let arr = [3,2,22,6,12,8,9,7,1,2]
and pass them to javascript's sort method:
console.log(arr.sort((a,b) => { return a - b }))
I'll get:
output: arr [1, 2, 2, 3, 6, 7, 8, 9, 12, 22]
For purposes of understanding "algorithms", I'm forgoing the built in functions and breaking down the steps involved in a sort.
Most programmers are familiar with iterating over an array and comparing every element in the array to every other element in the array. I'll refer to that as a basic sort. The below accomplishes what arr.sort() above does and is done by using two loops.
It basically looks for the smallest in the array and once found sets it in a new array.
let arr = [3,22,2,6,12,8,9,7,1,2]
let sortedArr = []
let positionSetArr = [] // Track the position the value had in the original array so as not to repeat it but allow for duplicate values at different positions
for (let i = 0; i < arr.length; i++) {
let currentSmallest = 1000000 // a number way out of range
let positionSet = null
for(let j = 0; j < arr.length; j++) {
let val = arr[j]
if (val < currentSmallest && !positionSetArr.includes(j)) {
currentSmallest = val
positionSet = j // For example, the value 2 is in position 3 and 9. The position 3 won't be repeated but the value 2 at position 9 can still be set
}
}
positionSetArr.push(positionSet) // This and !positionSetArr.includes(j) above ensures that once a position is set, it won't get set again
sortedArr.push(currentSmallest)
}
console.log(sortedArr) // arr [1, 2, 2, 3, 6, 7, 8, 9, 12, 22]
The above basic sort lacks the following that define a Selection Sort.
A Selection Sort is 1.) in-place, 2.) unstable, and 3.) comparison algorithm.
1.) in-place: it transforms the input collection using no auxiliary data structures and that the input is overridden by the output. The above uses sortedArr and nothing is overridden in that. The above also uses a number "way out of range".
2.) unstable: the order of duplicate elements isn't preserved after sorting. The basic sort has the original order preserved in the original 'arr' variable.
3.) comparison algorithm: during its execution, it only reads list elements through a single abstract comparison operation, usually a "less than or equal to" operator. The above uses a !positionSet.includes(j).
Here is an example of a Selection Sort:
let arr = [5, 4, 7, 4];
console.log("arr:", arr)
console.log("arr length:", arr.length)
for(let origPosition = 0; origPosition < arr.length; origPosition++) {
console.log("--- " + origPosition + " outer loop position")
// Find the smallest number in the subarray
let currentMinPosition = origPosition;
for(let comparePosition = origPosition + 1; comparePosition < arr.length; comparePosition++){
let compareVal = arr[comparePosition]
let currentMinVal = arr[currentMinPosition]
console.log("--- " + comparePosition + " inner loop position")
console.log("currentMinPosition:", currentMinPosition)
console.log("currentMinVal:" + currentMinVal)
console.log("compareValPosition: " + comparePosition)
console.log("compareVal:" + compareVal)
console.log("compareVal " + compareVal + " < currentMinVal " + currentMinVal + ":", compareVal < currentMinVal)
if (compareVal < currentMinVal) {
currentMinPosition = comparePosition;
console.log("currentMinPosition set to " + currentMinPosition + " (representing value: " + arr[currentMinPosition] + ")")
}
}
if (currentMinPosition != origPosition) {
console.log("Swap value " + arr[origPosition] + " that is at position " + origPosition + " with value " + arr[currentMinPosition] + " at position " + currentMinPosition)
let tmp = arr[origPosition];
arr[origPosition] = arr[currentMinPosition];
arr[currentMinPosition] = tmp;
console.log("resultant arr:", arr)
}
}
console.log(arr)
The inner loop treats everything that is below its starting position as already sorted by doing this:
for(let comparePosition = origPosition + 1; comparePosition < arr.length; comparePosition++){
Once you understand that, the whole thing should fall into place. For example, to translate it into english, "compare every value against position 0 and when the smallest value is found, swap position 0 with it. Once that is done, do the same to position 1 and never go back to an earlier position."
Here's the output from the console.log above:
arr: [ 5, 4, 7, 4 ]
arr length: 4
--- 0 outer loop position
--- 1 inner loop position
currentMinPosition: 0
currentMinVal:5
compareValPosition: 1
compareVal:4
compareVal 4 < currentMinVal 5: true
currentMinPosition set to 1 (representing value: 4)
--- 2 inner loop position
currentMinPosition: 1
currentMinVal:4
compareValPosition: 2
compareVal:7
compareVal 7 < currentMinVal 4: false
--- 3 inner loop position
currentMinPosition: 1
currentMinVal:4
compareValPosition: 3
compareVal:4
compareVal 4 < currentMinVal 4: false
Swap value 5 that is at position 0 with value 4 at position 1
resultant arr: [ 4, 5, 7, 4 ]
--- 1 outer loop position
--- 2 inner loop position
currentMinPosition: 1
currentMinVal:5
compareValPosition: 2
compareVal:7
compareVal 7 < currentMinVal 5: false
--- 3 inner loop position
currentMinPosition: 1
currentMinVal:5
compareValPosition: 3
compareVal:4
compareVal 4 < currentMinVal 5: true
currentMinPosition set to 3 (representing value: 4)
Swap value 5 that is at position 1 with value 4 at position 3
resultant arr: [ 4, 4, 7, 5 ]
--- 2 outer loop position
--- 3 inner loop position
currentMinPosition: 2
currentMinVal:7
compareValPosition: 3
compareVal:5
compareVal 5 < currentMinVal 7: true
currentMinPosition set to 3 (representing value: 5)
Swap value 7 that is at position 2 with value 5 at position 3
resultant arr: [ 4, 4, 5, 7 ]
--- 3 outer loop position
[ 4, 4, 5, 7 ]
A good walk thru of Selection Sort.