Сортировка выбором на языке C

Сортировка выбором (Selection Sort) является одним из простейших алгоритмов сортировки. Он основан на поиске минимального элемента в массиве и его замене с элементом, находящимся на первой позиции. Затем процедура повторяется для оставшейся части массива, и на каждом шаге в ней находится минимальный элемент и меняется с первым элементом этой части.

Рассмотрим пример кода на языке Python, реализующий сортировку выбором:

python
def selection_sort(arr):
    length = len(arr)
    for i in range(length):
        min_idx = i
        for j in range(i+1, length):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

В данном коде функция `selection_sort` принимает массив `arr` и сортирует его методом выбора. Для этого мы проходимся по всем элементам массива, находим минимальный элемент в оставшейся части массива и меняем его с первым элементом этой части.

Для каждого элемента массива сохраняем его текущий индекс `i` и ищем минимальный элемент с индексами `j`, начиная со следующего элемента после `i`. Если нашли элемент, который меньше текущего минимального элемента, то обновляем значение `min_idx`.

В конце одной итерации внешнего цикла текущий минимальный элемент меняем с элементом на первой позиции `i`.

После завершения внешнего цикла возвращаем отсортированный массив `arr`.

Временная сложность сортировки выбором составляет `O(n^2)`, а пространственная сложность – `O(1)`, и это делает его неоптимальным для больших массивов. Однако, это один из простейших алгоритмов сортировки, его легко реализовать и он может быть использован для сортировки небольших массивов.