Алгоритмы сортировки
Алгоритмы сортировки упорядочивают элементы по определённому критерию.
Сортировка вставками
В алгоритме Insertion sort элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.
В первой итерации внешнего цикла будет только один цикл внутреннего, во втором цикле будет 2 внутренних цикла т.е с ростом количества циклов растет и количество внутреннего цикла.
Временная сложность алгоритма — O(n2)
С исходным кодом алгоритма и его интерактивной презентацией вы сможете ознакомиться на специальном ресурсе.
Код на 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(n2)
С исходным кодом алгоритма и его интерактивной презентацией вы сможете ознакомиться на специальном ресурсе.
Код на 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;
}
Сортировка выбором
Сортировка выбором — здесь, чтобы отсортировать массив, находим элемент с минимальным значением, затем сравниваем его со значением первой неотсортированной позиции. Если этот элемент меньше, то он становится новым минимумом и их позиции меняются.
Шаги алгоритма:
- находим номер минимального значения в текущем списке
- производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции)
- теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы
Временная сложность алгоритма — O(n2)
С исходным кодом алгоритма и его интерактивной презентацией вы сможете ознакомиться на специальном ресурсе.
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(n2) в худшем случае.
А лучший случай если массив также отсортирован и мы выбираем всегда средний элемент. Тогда высота стека вызовов будет равна O(log n). Каждый уровень также занимает время O(n). Вместе выходит O(n log n).
Временная сложность алгоритма — O(n log n)
Алгоритм состоит из трёх шагов:
- Выбор опорного элемента из массива.
- Перераспределение элементов в массиве таким образом, что элементы меньше опорного помещаются перед ним, а больше или равные — после.
- Рекурсивное применение первых двух шагов к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один или отсутствуют элементы.
С исходным кодом алгоритма и его интерактивной презентацией вы сможете ознакомиться на специальном ресурсе.
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/