Сортировка выбором на PHP

Порой нам нужно привести массив в порядок и сделать из него стройный ряд цифр от меньшего к большему или наоборот.

Тут нам на помощь приходят различные алгоритмы сортировки.
Сейчас мы рассмотрим один такой алгоритм под названием "Сортировка выбором".
Данный алгоритм достаточно прост в понимании и реализации, но имеет не самую оптимальную временную сложность тета от n^2, в прочем есть очень не много алгоритмов сортировки, которые имеют лучшие показатели в этом плане, но они сложнее в реализации.

Расскажу сначала не много про суть сортировки выбором.
Представим, что у нас есть ряд цифр 3, 5, 4, 1 и нам надо отсортировать их по возрастанию.
Следуя данному алгоритму, мы берем первую цифру 3, и сравниваем ее с каждой последующей (5, 4, 1), как только мы находим наименьшую цифру, а это будет 1, то меняем их местами, то есть 1 ставим в начало, а 3 в конец. Теперь мы уверены, что на первом месте у нас минимальная цифра в ряду, и можем взять второе число и проделать с ним тоже самое, и так до предпоследнего числа включительно, последнее у нас и так будет самое большое.

Итак, приведу код функции сортировки

function selectionSort3($m, $masCount)
{
    for($i=0; $i < $masCount-1; $i++)
    {
        $small = $i;
        
        for($k=$i+1; $k < $masCount; $k++)
        {
            if($m[$k] < $m[$small])
            {
                $small = $k;
            }
        }
        
        $buf = $m[$i];
        $m[$i] = $m[$small];
        $m[$small] = $buf;
    }
    
    return $m;
}

Теперь пройдемся по самому коду.
На вход функция принимает два параметра m - массив и masCount - количество элементов в массиве.

Первым делом мы организуем внешний цикл, который проходится от начала до masCount-1 (как мы помним последний элемент всегда будет самым большим).

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

Далее открываем внутренний цикл, который пробежится по тому же массиву с целью выявления меньшего элемента, чем тот, который в индексе small (i). Стоит отметить, что нам не нужно проходить внутренний цикл от начала массива до его конца, а нужно делать смещение, которое зависит от i. То есть например мы взяли второй элемент массива, и ищем элемент, который меньше его, так как первый у нас уже самый маленький, мы начинаем поиск с третьего элемента (i=2, 2+1=3).

Во внутреннем цикле мы просто сравниваем значение под индексом small с текущем значением во внутреннем цикле под индексом k. Если значение в k меньше, чем значение в small, то мы присваиваем small значение k, тем самым в small всегда остается наименьший индекс из диапазона массива от i+1 до masCount.

После выхода из внутреннего цикла (все еще оставаясь во внешнем), мы меняем местами значения у индексов i и small.
То есть значение в small ставим в i, а значение i ставим в элемент массива под индексом small (большее значение отбрасываем в правую часть массива).
Заметьте, что делается это через буфферную переменную buf, которая хранит значение под индексом i, на время перестановки.

После выхода из внешнего цикла мы возвращаем уже отсортированный по возрастанию массив.

Если нам надо отсортировать массив по убыванию, то достаточно поменять знак условии $m[$k] < $m[$small] на противоположенный, то есть $m[$k] > $m[$small], тем самым у нас будет массив отсортированный по убыванию.


comments powered by Disqus