Implement selectionSort(array) — order an array of numbers ascending using selection sort. The idea is simple: repeatedly find the smallest value in the part of the array you haven't sorted yet, and move it to the front of that unsorted part. After the first pass the smallest value sits at index 0; after the second, the next smallest sits at index 1; and so on until the whole array is in order. Return a new sorted array — do not change the array you were given.
// array: number[] — the numbers to sort (not mutated).
// returns: number[] — a NEW array with the same values, sorted ascending.
function selectionSort(array: number[]): number[];selectionSort([3, 1, 2]);
// → [1, 2, 3]selectionSort([64, 25, 12]);
// → [12, 25, 64][]; a single-element array returns a copy of itself. Already-sorted and reverse-sorted inputs must both come out sorted.Array.prototype.sort.You'll sort an array by repeatedly grabbing the smallest value that isn't in place yet and putting it at the front of the unsorted part.
Imagine sorting a hand of playing cards by repeatedly scanning the cards you haven't dealt with, finding the lowest one, and sliding it to the left edge of your hand. Each scan locks one more card into its final position. Selection sort is exactly that: the array splits into a sorted prefix on the left and an unsorted region on the right. Every pass finds the minimum of the unsorted region and moves it to the boundary, so the sorted prefix grows by one each time until nothing is left unsorted.
Picture the array as two zones. The left zone is done — those values are in their final sorted positions and you never touch them again. The right zone is unsorted. On each pass you look only at the unsorted zone, find its smallest value, and swap it into the leftmost unsorted slot. That slot now joins the sorted zone, and the boundary slides one step to the right.
A natural first version reaches for Math.min to find the smallest, indexOf to locate it, and splice to pull it out into a result array:
function selectionSort(array) {
const rest = [...array]; // copy so we don't mutate the input
const result = [];
while (rest.length > 0) {
const min = Math.min(...rest); // smallest value in what's left
const at = rest.indexOf(min); // where is it?
rest.splice(at, 1); // remove it from the unsorted pile
result.push(min); // append it to the sorted output
}
return result;
}This is correct, and for an interview it might even pass. But it does a lot of redundant work. Math.min(...rest) walks the whole remaining array, then indexOf(min) walks it again to find the position, then splice shifts every element after that position down by one to close the gap — and splice reallocates as the array shrinks. You're scanning two-to-three times per pass and reshuffling memory on every step. The classic selection sort does the same job with a single scan per pass and one swap, no splice and no second array.
function selectionSort(array) {
// Work on a copy so the caller's array is never reordered.
const result = [...array];
// After pass `i`, result[0..i] holds the final sorted prefix. The last
// element falls into place once everything before it is sorted, so we stop
// at length - 1.
for (let i = 0; i < result.length - 1; i++) {
// Assume the first unsorted slot holds the smallest, then look for proof
// otherwise across the rest of the unsorted region.
let minIndex = i;
for (let j = i + 1; j < result.length; j++) {
if (result[j] < result[minIndex]) {
minIndex = j;
}
}
// Only swap when the minimum is somewhere else; if it's already at i, this
// skip avoids a pointless self-swap.
if (minIndex !== i) {
[result[i], result[minIndex]] = [result[minIndex], result[i]];
}
}
return result;
}
module.exports = { selectionSort };The shift from the naive version is that we never remove or re-allocate anything. Instead of Math.min + indexOf (two scans) plus splice (a shift), the inner loop tracks the index of the smallest value in one pass, and a single swap drops it into place. The outer index i marks the boundary: everything before i is already final, so each pass only scans from i onward. The minIndex !== i guard skips the swap when the smallest value is already at the boundary — a small win when the data is partly sorted.
Trace selectionSort([64, 25, 12, 22]). We copy the input into result and the outer loop runs for i = 0, 1, 2.
start result = [64, 25, 12, 22]
i = 0 scan slots 0..3 → smallest is 12 at index 2
minIndex (2) !== 0, so swap result[0] and result[2]
result = [12, 25, 64, 22]
i = 1 scan slots 1..3 → smallest is 22 at index 3
minIndex (3) !== 1, so swap result[1] and result[3]
result = [12, 22, 64, 25]
i = 2 scan slots 2..3 → smallest is 25 at index 3
minIndex (3) !== 2, so swap result[2] and result[3]
result = [12, 22, 25, 64]
return [12, 22, 25, 64]
After i = 2, the loop stops — the last slot (index 3) is already correct, because the three smaller values were pulled out ahead of it. That's why the loop runs to length - 1 and not length: the final element has nothing left to compete with.
array directly (or do const result = array), the caller's array changes and the new-reference tests fail. Copy first with const result = [...array] and sort the copy.[...array] already fixes this — it always makes a fresh array — but if you add an early return array for the "already sorted" case, you hand back the original reference and break the not.toBe(input) check.j = i + 1, comparing each candidate against result[minIndex] (not against result[i]). Comparing against a fixed result[i] finds a value smaller than the boundary but not necessarily the true minimum of the region.i to result.length wastes a final pass over a one-element region, and length - 1 is the correct stop: once the first n - 1 values are placed, the last one is already where it belongs.minIndex and read result[minIndex] when comparing — the index is what the swap needs.[5a, 5b, 1] (two distinct objects both keyed 5) puts 1 first and can leave 5b before 5a. Insertion sort and a careful bubble sort preserve equal-element order; selection sort does not.n - 1 swaps — fewer writes than bubble sort, which can swap on nearly every comparison. When writing to memory is far more expensive than reading (e.g. flash storage with limited write cycles), minimizing swaps can matter more than the comparison count.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
Implement selectionSort(array) — order an array of numbers ascending using selection sort. The idea is simple: repeatedly find the smallest value in the part of the array you haven't sorted yet, and move it to the front of that unsorted part. After the first pass the smallest value sits at index 0; after the second, the next smallest sits at index 1; and so on until the whole array is in order. Return a new sorted array — do not change the array you were given.
// array: number[] — the numbers to sort (not mutated).
// returns: number[] — a NEW array with the same values, sorted ascending.
function selectionSort(array: number[]): number[];selectionSort([3, 1, 2]);
// → [1, 2, 3]selectionSort([64, 25, 12]);
// → [12, 25, 64][]; a single-element array returns a copy of itself. Already-sorted and reverse-sorted inputs must both come out sorted.Array.prototype.sort.You'll sort an array by repeatedly grabbing the smallest value that isn't in place yet and putting it at the front of the unsorted part.
Imagine sorting a hand of playing cards by repeatedly scanning the cards you haven't dealt with, finding the lowest one, and sliding it to the left edge of your hand. Each scan locks one more card into its final position. Selection sort is exactly that: the array splits into a sorted prefix on the left and an unsorted region on the right. Every pass finds the minimum of the unsorted region and moves it to the boundary, so the sorted prefix grows by one each time until nothing is left unsorted.
Picture the array as two zones. The left zone is done — those values are in their final sorted positions and you never touch them again. The right zone is unsorted. On each pass you look only at the unsorted zone, find its smallest value, and swap it into the leftmost unsorted slot. That slot now joins the sorted zone, and the boundary slides one step to the right.
A natural first version reaches for Math.min to find the smallest, indexOf to locate it, and splice to pull it out into a result array:
function selectionSort(array) {
const rest = [...array]; // copy so we don't mutate the input
const result = [];
while (rest.length > 0) {
const min = Math.min(...rest); // smallest value in what's left
const at = rest.indexOf(min); // where is it?
rest.splice(at, 1); // remove it from the unsorted pile
result.push(min); // append it to the sorted output
}
return result;
}This is correct, and for an interview it might even pass. But it does a lot of redundant work. Math.min(...rest) walks the whole remaining array, then indexOf(min) walks it again to find the position, then splice shifts every element after that position down by one to close the gap — and splice reallocates as the array shrinks. You're scanning two-to-three times per pass and reshuffling memory on every step. The classic selection sort does the same job with a single scan per pass and one swap, no splice and no second array.
function selectionSort(array) {
// Work on a copy so the caller's array is never reordered.
const result = [...array];
// After pass `i`, result[0..i] holds the final sorted prefix. The last
// element falls into place once everything before it is sorted, so we stop
// at length - 1.
for (let i = 0; i < result.length - 1; i++) {
// Assume the first unsorted slot holds the smallest, then look for proof
// otherwise across the rest of the unsorted region.
let minIndex = i;
for (let j = i + 1; j < result.length; j++) {
if (result[j] < result[minIndex]) {
minIndex = j;
}
}
// Only swap when the minimum is somewhere else; if it's already at i, this
// skip avoids a pointless self-swap.
if (minIndex !== i) {
[result[i], result[minIndex]] = [result[minIndex], result[i]];
}
}
return result;
}
module.exports = { selectionSort };The shift from the naive version is that we never remove or re-allocate anything. Instead of Math.min + indexOf (two scans) plus splice (a shift), the inner loop tracks the index of the smallest value in one pass, and a single swap drops it into place. The outer index i marks the boundary: everything before i is already final, so each pass only scans from i onward. The minIndex !== i guard skips the swap when the smallest value is already at the boundary — a small win when the data is partly sorted.
Trace selectionSort([64, 25, 12, 22]). We copy the input into result and the outer loop runs for i = 0, 1, 2.
start result = [64, 25, 12, 22]
i = 0 scan slots 0..3 → smallest is 12 at index 2
minIndex (2) !== 0, so swap result[0] and result[2]
result = [12, 25, 64, 22]
i = 1 scan slots 1..3 → smallest is 22 at index 3
minIndex (3) !== 1, so swap result[1] and result[3]
result = [12, 22, 64, 25]
i = 2 scan slots 2..3 → smallest is 25 at index 3
minIndex (3) !== 2, so swap result[2] and result[3]
result = [12, 22, 25, 64]
return [12, 22, 25, 64]
After i = 2, the loop stops — the last slot (index 3) is already correct, because the three smaller values were pulled out ahead of it. That's why the loop runs to length - 1 and not length: the final element has nothing left to compete with.
array directly (or do const result = array), the caller's array changes and the new-reference tests fail. Copy first with const result = [...array] and sort the copy.[...array] already fixes this — it always makes a fresh array — but if you add an early return array for the "already sorted" case, you hand back the original reference and break the not.toBe(input) check.j = i + 1, comparing each candidate against result[minIndex] (not against result[i]). Comparing against a fixed result[i] finds a value smaller than the boundary but not necessarily the true minimum of the region.i to result.length wastes a final pass over a one-element region, and length - 1 is the correct stop: once the first n - 1 values are placed, the last one is already where it belongs.minIndex and read result[minIndex] when comparing — the index is what the swap needs.[5a, 5b, 1] (two distinct objects both keyed 5) puts 1 first and can leave 5b before 5a. Insertion sort and a careful bubble sort preserve equal-element order; selection sort does not.n - 1 swaps — fewer writes than bubble sort, which can swap on nearly every comparison. When writing to memory is far more expensive than reading (e.g. flash storage with limited write cycles), minimizing swaps can matter more than the comparison count.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.