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

javascript

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
    let temp = array[minIndex];
    array[minIndex] = array[i];
    array[i] = temp;
  }
}

# Possible Test Cases

javascript

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

javascript

const generateRandom = (count) => {
  // Create array of integers
  let nums = [...Array(count).keys()];

  // Shuffle
  for (let i = nums.length - 1; i > 0; i--) {
    let randomIndex = Math.floor(Math.random() * i) % i;

    // Swap
    let temp = nums[i];
    nums[i] = nums[randomIndex];
    nums[randomIndex] = temp;
  }

  return nums;
};

# Working Example

Type yarn test on console to run vitest.