Selection Sort

Core idea

The algorithm divides the array into a sorted prefix and an unsorted suffix.

On every pass, it scans the unsorted part, finds the minimum element, and swaps it into the next position of the sorted prefix.

It is easy to reason about and performs a predictable number of comparisons, which makes it a useful teaching algorithm.

// Проходим все элементы и на каждой итерации ищем минимальное значение
// если нашли меньше, чем текущее, то меняем местами.
// O(n^2)

function selectionSort (arr) {
 for (let i = 0; i < arr.length; i++) {
   let min = i;
   for (let j = i + 1; j < arr.length; j++) {
     if (arr[min] > arr[j]) {
       min = j;
     }
   }

   if (min !== i) {
     const tmp = arr[i];
     arr[i] = arr[min];
     arr[min] = tmp;
   }
 }
 return arr;
}