Массив
Массивы – это простейшая структура данных, представляющая собой набор элементов одного типа, расположенных последовательно в памяти. Хранит набор значений (элементов массива), идентифицируемых по индексу или набору индексов, принимающих целые (или приводимые к целым) значения из некоторого заданного непрерывного диапазона.
Преимущества:
- Быстрый доступ к элементам по индексу
- Непрерывная область памяти
Недостатки:
- Фиксированный размер
- Неэффективное добавление/удаление элементов
Применение: Массивы подходят для хранения набора данных с фиксированным размером, где операции вставки и удаления элементов не требуются.
Сортировки массивов
Сортировка пузырьком / Bubble sort
Или сортировка простыми обменами. Обходим массив от начала до конца, попутно меняя местами неотсортированные соседние элементы. В результате первого прохода на последнее место «всплывёт» максимальный элемент. Теперь снова обходим неотсортированную часть массива (от первого элемента до предпоследнего) и меняем по пути неотсортированных соседей. Второй по величине элемент окажется на предпоследнем месте. Если за проход не произошло ни одного обмена, то массив отсортирован. Продолжая в том же духе, будем обходить всё уменьшающуюся неотсортированную часть массива, запихивая найденные максимумы в конец. Очевидно, не более чем после n итераций массив будет отсортирован.
<?php
/**
* Worst O(n^2)
* Average O(n^2)
* Best O(n)
*/
function bubbleSort(array $array): array {
$length = count($array);
for ($i = $length - 1; $i > 0; $i--) {
$changes = false;
for ($j = 0; $j < $i; $j++) {
if ($array[$j] > $array[$j + 1]) {
[$array[$j], $array[$j + 1]] = [$array[$j + 1], $array[$j]];
$changes = true;
}
}
if (!$changes) {
return $array;
}
}
return $array;
}
print_r(bubbleSort([5, 25, 10, 7, 6, 20, 21, 1, 2, 13]));
Сортировка вставками / Insertion sort
Элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.
<?php
/**
* Worst O(n^2)
* Average O(n^2)
* Best O(n)
*/
function insertSort(array $arr): array {
$count = count($arr);
for ($i = 1; $i < $count; $i++) {
for ($j = $i; $j >= 1 && $arr[$j] < $arr[$j-1]; $j--) {
[$arr[$j], $arr[$j-1]] = [$arr[$j-1], $arr[$j]];
}
}
return $arr;
}
print_r(insertSort([3,4,1,2,5,9,6,7,8]));
Сортировка выбором / Selection sort
На очередной итерации будем находить минимум в массиве после текущего элемента и менять его с ним, если надо. Таким образом, после i-ой итерации первые i элементов будут стоять на своих местах. Нужно отметить, что эту сортировку можно реализовать двумя способами – сохраняя минимум и его индекс или просто переставляя текущий элемент с рассматриваемым, если они стоят в неправильном порядке.
<?php
/**
* Worst O(n^2)
* Average O(n^2)
* Best O(n^2)
*/
function selectionSort(array $arr): array
{
$count = count($arr);
for ($i = 0; $i < $count - 1; $i++) {
$min = $i;
for ($j = $i + 1; $j < $count; $j++) {
if ($arr[$j] < $arr[$min]) {
$min = $j;
}
}
if ($min != $i) {
[$arr[$i], $arr[$min]] = [$arr[$min], $arr[$i]];
}
}
return $arr;
}
$array = [3,4,1,2,5,9,6,7,8];
print_r(selectionSort($array));
Быстрая сортировка / Quicksort
- Выбрать из массива элемент, называемый опорным(pivot). Это может быть любой из элементов массива. От выбора опорного элемента не зависит корректность алгоритма, но в отдельных случаях может сильно зависеть его эффективность. В ранних реализациях, как правило, опорным выбирался первый элемент, что снижало производительность на отсортированных массивах. Для улучшения эффективности может выбираться средний, случайный элемент или (для больших массивов) медиана первого, среднего и последнего элементов. Медиана всей последовательности является оптимальным опорным элементом, но её вычисление слишком трудоёмко для использования в сортировке.
- Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующих друг за другом: «элементы меньшие опорного», «равные» и «большие». На практике массив обычно делят не на три, а на две части: например, «меньшие опорного» и «равные и большие»; такой подход в общем случае эффективнее, так как упрощает алгоритм разделения
- Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.
<?php
/**
* Worst O(n^2)
* Average O(n logn)
* Best O(n logn)
*/
function quick(array $arr) : array {
if (count($arr) < 2) {
return $arr;
}
$pivot = (int)(count($arr) / 2); // самый тупой выбор опорника
$less_arr = [];
$more_arr = [];
for ($i = 0; $i <count($arr); $i++) {
if ($i == $pivot) {
continue;
}
if ($arr[$i] < $arr[$pivot]) {
$less_arr[] = $arr[$i];
} else {
$more_arr[] = $arr[$i];
}
}
return array_merge(quick($less_arr), [$arr[$pivot]], quick($more_arr));
}
print_r(quick([3, 4, 1, 2, 5, 9, 6, 7, 8]));
Сортировка слиянием / Merge sort
Сортировка, основанная на парадигме «разделяй и властвуй». Разделим массив пополам, рекурсивно отсортируем части, после чего выполним процедуру слияния: поддерживаем два указателя, один на текущий элемент первой части, второй – на текущий элемент второй части. Из этих двух элементов выбираем минимальный, вставляем в ответ и сдвигаем указатель, соответствующий минимуму. Слияние работает за O(n), уровней всего logn, поэтому асимптотика O(n logn). Эффективно заранее создать временный массив и передать его в качестве аргумента функции. Эта сортировка рекурсивна, как и быстрая, а потому возможен переход на квадратичную при небольшом числе элементов.
<?php
/**
* Worst O(n log n)
* Average O(n log n)
* Best O(n log n)
*/
function merge(array $arr) : array {
if (count($arr) < 2) {
return $arr;
}
if (count($arr) == 2) {
if ($arr[0] < $arr[1]) {
return $arr;
} else {
return [$arr[1], $arr[0]];
}
}
$halved = array_chunk($arr, ceil(count($arr)/2)); // пополам
// разбиваем и сортируем каждую половину
$h1 = merge($halved[0]);
$h2 = merge($halved[1]);
//сливаем
$res = [];
for ($i = 0, $j = 0; $i < count($h1) || $j < count($h2); ) {
if (!isset($h1[$i])) {
$res[] = $h2[$j];
$j++;
continue;
}
if (!isset($h2[$j])) {
$res[] = $h1[$i];
$i++;
continue;
}
if ($h1[$i] < $h2[$j]) {
$res[] = $h1[$i];
$i++;
} else {
$res[] = $h2[$j];
$j++;
}
}
return $res;
}
var_dump(merge([3,34,1,33,5,213213,99,1,1,0,0, -123]));
Сортировка кучей
ßКуча (heap) — это не что иное, как двоичное дерево с некоторыми дополнительными правилами, которым оно должно следовать: во-первых, оно всегда должно иметь структуру кучи, где все уровни двоичного дерева заполняются слева направо, и, во-вторых, оно должно быть упорядочено в виде max-кучи или min-кучи. В качестве примера я буду использовать min-кучу.
Алгоритм пирамидальной сортировки — это метод сортировки, который полагается на такие структуры данных как двоичные кучи. Поскольку мы знаем, что кучи всегда должны соответствовать определенным требованиям, мы можем использовать это для поиска элемента с наименьшим значением, последовательно сортируя элементы, выбирая корневой узел кучи и добавляя его в конец массива.
Работает в худшем, в среднем и в лучшем случае (то есть гарантированно) за O(n*log n) операций при сортировке n элементов. Количество применяемой служебной памяти не зависит от размера массива O(1). Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает/тонет по многим путям.
<?php
// Реализация пирамидальной сортировки на Php
// Процедура для преобразования в двоичную кучу поддерева с корневым узлом i, что является
// индексом в arr[]. n - размер кучи
function heapify(&$arr, $n, $i)
{
$largest = $i; // Инициализируем наибольший элемент как корень
$l = 2*$i + 1; // левый = 2*i + 1
$r = 2*$i + 2; // правый = 2*i + 2
// Если левый дочерний элемент больше корня
if ($l < $n && $arr[$l] > $arr[$largest])
$largest = $l;
//Если правый дочерний элемент больше, чем самый большой элемент на данный момент
if ($r < $n && $arr[$r] > $arr[$largest])
$largest = $r;
// Если самый большой элемент не корень
if ($largest != $i)
{
$swap = $arr[$i];
$arr[$i] = $arr[$largest];
$arr[$largest] = $swap;
// Рекурсивно преобразуем в двоичную кучу затронутое поддерево
heapify($arr, $n, $largest);
}
}
//Основная функция, выполняющая пирамидальную сортировку
function heapSort(&$arr, $n)
{
// Построение кучи (перегруппируем массив)
for ($i = $n / 2 - 1; $i >= 0; $i--)
heapify($arr, $n, $i);
//Один за другим извлекаем элементы из кучи
for ($i = $n-1; $i >= 0; $i--)
{
// Перемещаем текущий корень в конец
$temp = $arr[0];
$arr[0] = $arr[$i];
$arr[$i] = $temp;
// вызываем процедуру heapify на уменьшенной куче
heapify($arr, $i, 0);
}
}
/* Вспомогательная функция для вывода на экран массива размера n */
function printArray(&$arr, $n)
{
for ($i = 0; $i < $n; ++$i)
echo ($arr[$i]." ") ;
}
$arr = array(12, 11, 13, 5, 6, 7);
$n = sizeof($arr)/sizeof($arr[0]);
heapSort($arr, $n);
printArray($arr , $n);
Дополнительно: