Description
- It has maximum of N swap operation
- Suitable for cases where swap operations are expensive (memory intensive)

Time & Space Complexity
- Time:
- Best: O(n^2)
- Average: O(n^2)
- Worst: O(n^2)
- Space:
- O(1)
Implementation
js
function selectionSort(array) {
let minIndex
for (let i = 0; i < array.length; i++) {
minIndex = i
for (let j = i; j < array.length; j++) {
// Find the minimum value's index
if (array[j] < array[minIndex])
minIndex = j
}
// Swap the minimum value with the first element
const temp = array[minIndex]
array[minIndex] = array[i]
array[i] = temp
}
}
Possible Test Cases
js
const array1 = [] // Given array is empty
const array2 = [3] // Given array contains only a single element
const array3 = [0, 0, 0, 0] // Given array contains only zeros
const array4 = [2, 2, 2, 2] // Given array contains same elements
const array5 = [1, 2, 3, 4, 5] // Given array is already sorted
const array6 = [5, 4, 3, 2, 1] // Given array is reversed
const array7 = [-2, -5, 3, 1, 0] // Given array contain both positive and negative numbers
const array8 = generateRandom(10000) // Given array contains large number of elements
js
function generateRandom(count) {
// Create array of integers
const nums = [...new Array(count).keys()]
// Shuffle
for (let i = nums.length - 1; i > 0; i--) {
const randomIndex = Math.floor(Math.random() * i) % i
// Swap
const temp = nums[i]
nums[i] = nums[randomIndex]
nums[randomIndex] = temp
}
return nums
}
Working Example
Type yarn test
on console to run vitest.