Алгоритмы сортировки

Алгоритмы сортировки упорядочивают элементы по определённому критерию.

Сортировка вставками

В алгоритме Insertion sort элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.

В первой итерации внешнего цикла будет только один цикл внутреннего, во втором цикле будет 2 внутренних цикла т.е с ростом количества циклов растет и количество внутреннего цикла.

Временная сложность алгоритма — O(n²)

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

Код на PHP

function insertionSort($array)
{
    for ($j = 1; $j < count($array) - 1; $j++) {
        $key = $array[$j];
        $i = $j;
        
        while ($i > 0 and $array[$i-1] > $key) {
            $array[$i] = $array[$i-1];
            $i = $i - 1;
        }
        
        $array[$i] = $key;
    }
    
    return $array;
}

Сортировка пузырьком

Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки.

В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как сортировка перемешиванием, пирамидальная сортировка и быстрая сортировка.

В отличии от сортировки вставкой с увеличением внешней итерации, количество циклов у внутреннего уменьшается.

Временная сложность алгоритма — O(n²)

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

Код на PHP (Для простоты не выносил count(), не писал list($a, $b) = array($b, $a))

function bubbleSort($arr)
{
    for ($i = 0; $i < count($arr); $i++) {
        for ($j = 0; $j < count($arr) - 1 - $i; $j++) {
            if ($arr[$j] > $arr[$j+1]) {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $tmp;
            }
        }
    }
    return $arr;
}

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

Сортировка выбором — здесь, чтобы отсортировать массив, находим элемент с минимальным значением, затем сравниваем его со значением первой неотсортированной позиции. Если этот элемент меньше, то он становится новым минимумом и их позиции меняются.

Шаги алгоритма:

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

Временная сложность алгоритма — O(n²)

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

function selectionSort($arr)
{
    for ($i=0; $i<count($arr); $i++ ) {
        $min = $i;
        
        for ($j=$i; $j<count($arr); $j++) {
            if ($arr[$min] > $arr[$j]) {
                $min = $j;
            }
        }
        
        $dump = $arr[$i];
        $arr[$i] = $arr[$min];
        $arr[$min] = $dump;
    }
    
    return $arr;
}

Быстрая сортировка

Быстрая сортировка — в целом это один из самых быстрых алгоритмов сортировки массивов, однако на практике он чаще всего применяется с разного рода модификациями. Является примером принципа «разделяй и властвуй».
Идея алгоритма заключается в том, что выбирается опорный элемент, относительно которого будет происходит сортировка. Равные и бОльшие элементы помещаются справа, меньшие – слева. Затем к полученным подмассивам рекурсивно применяются два первых пункта.

Быстродействие быстрой сортировки сильно зависит от выбора опорного элемента. Худший случай, если массив уже отсортирован и мы в качестве опорного выбираем первый (нулевой) элемент. Тогда общая высота стека будет равна длине массива, потому что  при каждом уровне рекурсии массив будет делиться на пустой, опорный и элементы больше опорного. Мы же выбраем первый элемент в отсортированном массиве. Других элементов меньше чем первый не может быть. Для завершения одного уровня мы проходимся по всем элементам. Это значит, сложность одного уровня O(n). А если уровней будет столько же сколько длина массива, то сложность уровней O(n). Вместе будет O(n²) в худшем случае.

А лучший случай если массив также отсортирован и мы выбираем всегда средний элемент. Тогда высота стека вызовов будет равна O(log n). Каждый уровень также занимает время O(n). Вместе выходит O(n log n).

Временная сложность алгоритма — O(n log n)

Алгоритм состоит из трёх шагов:

1. Выбор опорного элемента из массива.
2. Перераспределение элементов в массиве таким образом, что элементы меньше опорного помещаются перед ним, а больше или равные — после.
3. Рекурсивное применение первых двух шагов к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один или отсутствуют элементы.

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

function quickSort($array)
{
    if (count($array) < 2) {
        return $array;
    } else {
        $pivot = array_shift($array);
        $less = array_filter($array, function($i) use ($pivot) {
            return $i <= $pivot;
        });
        $greater = array_filter($array, function($i) use ($pivot) {
            return $i > $pivot;
        });
        
        return array_merge(quickSort($less), [$pivot], quickSort($greater));
    }
}

или так

function quickSort($array)
{
    if (count($array) < 2) {
        return $array;
    } else {
        $pivot = $array[0];
        $newArray = array_slice($array, 1);
        
        $less = $greater = [];
        
        foreach ($newArray as $item) {
            if ($item <= $pivot) {
                $less[] = $item;
            }
        }
        
        foreach ($newArray as $item) {
            if ($item > $pivot) {
                $greater[] = $item;
            }
        }
        
        return array_merge(quickSort($less), [$pivot], quickSort($greater));
    }
}

Ссылки на другие ресурсы по теме:

Алгоритмы сортировки на пальцах

https://tproger.ru/translations/sorting-for-beginners/

https://tproger.ru/digest/sorting-algorithms-visualized/

https://habr.com/post/335920/

https://habr.com/post/204600/

wikibooks