Алгоритм сортировки Selection Sort (сортировка выбором)

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

Описание алгоритма

1. Найти наименьший элемент в неотсортированной части массива.
2. Поменять местами этот элемент с первым элементом в неотсортированной части.
3. Сдвинуть границу отсортированной части массива на один элемент вправо.
4. Повторять, пока весь массив не станет отсортированным.

Сложность

• В лучшем, среднем и худшем случаях временная сложность Selection Sort составляет O(n^2), где n — количество элементов в массиве.
• Пространственная сложность алгоритма составляет O(1), так как для его работы требуется лишь константное дополнительное пространство для выполнения обменов элементов.

Пример на PHP

Ниже приведен пример реализации алгоритма сортировки выбором на языке PHP:

<?php
function selectionSort(array &$arr) {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        // Находим минимальный элемент в неотсортированной части массива
        $minIndex = $i;
        for ($j = $i + 1; $j < $n; $j++) {
            if ($arr[$j] < $arr[$minIndex]) {
                $minIndex = $j;
            }
        }

        // Обмен, если нашли элемент меньше, чем текущий минимум
        if ($minIndex != $i) {
            $temp = $arr[$i];
            $arr[$i] = $arr[$minIndex];
            $arr[$minIndex] = $temp;
        }
    }
}

// Тестирование функции сортировки
$testArray = array(64, 34, 25, 12, 22, 11, 90);
selectionSort($testArray);
echo "Отсортированный массив: \n";
print_r($testArray);

Комментарии к коду

В данном примере функция selectionSort принимает массив по ссылке (чтобы изменения в массиве отражались в исходном массиве) и сортирует его. Цикл внутри функции итерирует через массив, находит минимальный элемент в неотсортированной части и обменивает его с первым элементом этой части. В конце, мы тестируем функцию на массиве и выводим результат.