44.implement-Selection-Sort.md

44. implement Selection Sort

Selection Sort is a simple comparison-based sorting algorithm. It divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list, and a sublist of the remaining unsorted items that occupy the rest of the list. The algorithm repeatedly selects the smallest (or largest, depending on sorting order) element from the unsorted sublist, swaps it with the leftmost unsorted element, and moves the sublist boundaries one element to the right.

Problem

https://bigfrontend.dev/problem/implement-Selection-Sort

Problem Description

Even for Front-End Engineer, it is a must to understand how basic sorting algorithms work.

Now you are asked to implement Selection sort, which sorts an integer array in ascending order.

Do it in-place, no need to return anything.

Follow-up

What is time cost for average / worst case ? Is it stable?

Solution

/**
 * @param {number[]} arr
 */
function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let smallestIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[smallestIndex]) {
        smallestIndex = j;
      }
    }
    if (smallestIndex !== i) {
      [arr[smallestIndex], arr[i]] = [arr[i], arr[smallestIndex]];
    }
  }
}

Use Cases:

1. Small Data Sets: Suitable for small datasets where the overhead of more complex algorithms is not justified.
2. Memory-Constrained Environments: Due to its in-place nature, it is useful when memory space is at a premium.
3. Simple Requirements: When the simplicity of implementation is more important than performance.