Last active
August 1, 2018 04:06
-
-
Save CharmedSatyr/11b791ad9dbcc0562895d551b3888c4f to your computer and use it in GitHub Desktop.
Selection Sort implemented in JavaScript (2 methods)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* Selection sort works by selecting the minimum value in a list | |
* and swapping it with the first value in the list. It then | |
* starts at the second position, selects the smallest value in | |
* the remaining list, and swaps it with the second element. It | |
* continues iterating through the list and swapping elements | |
* until it reaches the end of the list. | |
*/ | |
// METHOD 1: Using 2 `for` loops (ES5) | |
function selectionSort(array) { | |
// Clone the array | |
var arr = array.slice(); | |
// 1) Find the minimum value in the array | |
// Loop through the arr | |
for (var i = 0; i < arr.length; i++) { | |
// Start off with the assumption that i is the index of the | |
// minimum value in the arr | |
var mindex = i; | |
// Loop through the arr from after i to the end | |
for (var j = i + 1; j < arr.length; j++) { | |
// If there is another number that's less than arr[i] | |
// or its successor minvals | |
if (arr[j] < arr[mindex]) { | |
// update the mindex | |
mindex = j; | |
} | |
} | |
// 2) Swap the minimum value with the item at index i | |
// If arr[i] wasn't already the minimum value in for-j's scope | |
if (i !== mindex) { | |
// Swap the current item and the minimum value | |
var tmp = arr[i]; | |
arr[i] = arr[mindex]; | |
arr[mindex] = tmp; | |
} | |
} | |
// Return the sorted array | |
return arr; | |
} | |
// METHOD 2: Use 1 `forEach` loop (ES6) | |
const selectionSort = array => { | |
// Clone the array | |
const arr = [...array]; | |
// Loop through the arr | |
arr.forEach((n, i) => { | |
// Find the minimum value from the current index to the end | |
const scope = arr.slice(i); | |
const minval = Math.min(...scope); | |
// Save the index of the minval in the arr | |
// Note the minval is in scope; do not indexOf out of scope | |
// or you'll find duplicates | |
const mindex = scope.indexOf(minval) + i; | |
// If the current value is greater than the minimum value | |
if (n > minval) { | |
// Swap the two in place | |
[arr[i], arr[mindex]] = [minval, n]; | |
} | |
}); | |
// Return the sorted arr | |
return arr; | |
}; | |
// Tests | |
console.log(selectionSort([5, 3, 2, 1, 3])); // [ 1, 3, 3, 3, 5 ] | |
console.log(selectionSort([5, 3, 1])); // [ 1, 3, 5 ] | |
console.log(selectionSort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92])); | |
// [ 1, 1, 2, 2, 4, 8, 32, 43, 43, 55, 63, 92, 123, 123, 234, 345, 5643 ] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment