Добро пожаловать в пост №3 из серии, посвященной изучению алгоритмов с помощью JavaScript.
Что такое сортировка выбором?
Алгоритм сортировки выбором делит входной список на две части: отсортированный подсписок элементов, который создается слева направо, и подсписок оставшихся неотсортированных элементов. Первоначально отсортированный подсписок пуст, а несортированный подсписок представляет собой весь входной список. Далее алгоритм находит наименьший элемент в несортированном подсписке, заменяет его крайним левым несортированным элементом и перемещает границы подсписка на один элемент вправо.
Временная эффективность сортировки выбором является квадратичной, поэтому существует ряд методов сортировки, которые имеют лучшую временную сложность, чем сортировка выбором.
Одна вещь, которая отличает сортировку выбором от других алгоритмов сортировки, заключается в том, что она делает минимально возможное количество перестановок, n - 1 в худшем случае.
Выполнение
Код
У нас есть 3 функции:
swap — просто меняет местами элементы.
findMinValueIndex — находит минимальное значение в массиве и возвращает его индекс.
sort — наша основная функция, которая выполняет итерацию по массиву, находя минимальный индекс элемента из несортированного массива, и если minValueIndex отличается от нашего текущего индекса, они меняются местами.
