Create Next App

Сортировка выбором (Selection Sort)

Проходит позиции i слева направо; для каждой ищет минимум в хвосте [i..end] и ставит его на позицию i (меняет местами с arr[i]). В немутирующей версии минимум каждый раз вырезается из копии массива и добавляется в новый результат.

Сложность:

Время – O(n^2), Память – O(n)

selection-sort.ts

1function selectionSort(arr: number[]): number[] {
2    const res: number[] = [], copy = [...arr];
3    while (copy.length) {
4        let min = 0;
5        for (let i = 1; i < copy.length; i++) if (copy[i] < copy[min]) min = i;
6        res.push(copy.splice(min, 1)[0]);
7    }
8    return res;
9}
10
11selectionSort([100,9,14,6,0]) // -> [0,6,9,14,100]
12selectionSort([8,3,2,7,11]) // -> [2,3,7,8,11]
13