Сортировка выбором — это алгоритм сортировки, который проходит через несортированную часть массива, чтобы найти самый низкий или самый маленький элемент и поместить его в начало. Алгоритм сортировки выбором имеет два подмассива. Одним из них является отсортированный подмассив или часть, которая, как известно, находится в порядке. Другой — несортированный подмассив или подмассив, который еще не отсортирован. Алгоритм ищет самый младший элемент в несортированном массиве и помещает его в начало этого подмассива. На следующем проходе первый элемент в несортированном подмассиве становится последним элементом в отсортированном подмассиве.
Пример
Отсортируйте заданный массив {5, 1, 4, 3, 2}.
Для начала сравните 5 с остальным массивом. 1 меньше 5, поэтому мы будем отслеживать 1 как наименьшее значение. 4 меньше 5, но 4 не меньше наименьшего значения, поэтому мы идем дальше. Это повторяется для чисел 3 и 2, которые меньше 5, но не меньше 1. После проверки всех элементов в массиве мы переключаем 5 с наименьшим значением 1.
Теперь мы снова начинаем со второго значения в массиве. Если мы пройдем процесс сравнения значений и сохранения наименьшего значения, мы обнаружим, что на этот раз наименьшее значение равно 2. Мы поменяем местами 5 на 2.
Начиная с третьего элемента, мы снова пройдемся и найдем наименьшее значение. Как только он будет найден, мы заменим его на третий элемент массива.
Мы пробежимся еще раз, чтобы завершить проверку. На этот раз список уже составлен, так что ничего не изменится.
Этот алгоритм имеет временную сложность O(n²).
Реализация кода
Чтобы реализовать этот алгоритм, вы создадите функцию, которая будет принимать массив целых чисел и размер этого массива в качестве параметров.
В этой функции у вас будет цикл for для просмотра массива. Вы также создадите переменную для отслеживания самого нижнего элемента в массиве.
Затем вы создадите вложенный цикл for для поиска элементов в массиве. Если элемент, на котором вы находитесь, ниже самого низкого значения, вы установите текущий элемент на самое низкое значение.
После того, как вложенный цикл for завершен, вы замените наименьшее значение текущим элементом, в котором находится первый цикл for.
Мы можем проверить это в функции main, запустив ее, чтобы отсортировать массив в порядке возрастания.
Это полный скрипт с некоторыми дополнительными функциями подкачки и печати массива.
