Сортировка пузырьком (Bubble sort)
Сортировка пузырьком - это самый простой алгоритм сортировки. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, "всплывает" до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Например, у нас есть массив целых чисел:
3 7 4 4 6 5 8
При первом проходе по массиву мы сравниваем значения 3 и 7. Поскольку 7 больше 3, мы оставляем их как есть. После чего сравниваем 7 и 4. 4 меньше 7, поэтому мы меняем их местами, перемещая семерку на одну позицию ближе к концу массива. Теперь он выглядит так:
3 4 7 4 6 5 8
Этот процесс повторяется до тех пор, пока семерка не дойдет почти до конца массива. В конце она сравнивается с элементом 8, которое больше, а значит, обмена не происходит. После того, как мы обошли массив один раз, он выглядит так:
3 4 4 6 5 7 8
Поскольку был совершен по крайней мере один обмен значений, нам нужно пройти по массиву еще раз. В результате этого прохода мы перемещаем на место число 6:
3 4 4 5 6 7 8
И снова был произведен как минимум один обмен, а значит, проходим по массиву еще раз. При следующем проходе обмена не производится, что означает, что наш массив отсортирован, и алгоритм закончил свою работу.
- Реализация на PHP:
$array = [3, 7, 4, 4, 6, 5, 8];
for ($i = 0; $i < count($array); $i++) {
for ($j = $i + 1; $j < count($array); $j++) {
if ($array[$i] > $array[$j]) {
$temp = $array[$j];
$array[$j] = $array[$i];
$array[$i] = $temp;
}
}
}
echo implode($array, ', ');
- Визуализация:
Сортировка вставками (Insertion sort)
Сортировка вставками работает, проходя по массиву и перемещая нужное значение в начало массива. После того, как обработана очередная позиция, мы знаем, что все позиции до нее отсортированы, а после нее - нет. Важный момент: сортировка вставками обрабатывает элементы массива по порядку. Поскольку алгоритм проходит по элементам слева направо, мы знаем, что все, что слева от текущего индекса - уже отсортировано. Постепенно отсортированная часть массива растет, и, в конце концов, массив окажется упорядоченным.
Давайте взглянем на конкретный пример. Вот наш неотсортированный массив, который мы будем использовать:
3 7 4 4 6 5 8
Алгоритм начинает работу с индекса 0 и значения 3. Поскольку это первый индекс, массив до него включительно считается отсортированным.
Далее мы переходим к числу 7. Поскольку 7 больше, чем любое значение в отсортированной части, мы переходим к следующему элементу.
На этом этапе элементы с индексами 0...1 отсортированы, а про элементы с индексами 2...n ничего не известно.
Следующим проверяется значение 4. Так как оно меньше семи, мы должны перенести его на правильную позицию в отсортированную часть массива. Остается вопрос: как ее определить? Это осуществляется методом FindInsertionIndex. Он сравнивает переданное ему значение (4) с каждым значением в отсортированной части, пока не найдет место для вставки.
Итак, мы нашли индекс 1 (между значениями 3 и 7). Метод Insert осуществляет вставку, удаляя вставляемое значение из массива и сдвигая все значения, начиная с индекса для вставки, вправо. Теперь массив выглядит так:
3 4 4 7 6 5 8
Теперь часть массива, начиная от нулевого элемента и заканчивая элементом с индексом 2, отсортирована. Следующий проход начинается с индекса 3 и значения 4. По мере работы алгоритма мы продолжаем делать такие вставки.
3 4 4 5 6 7 8
Когда больше нет возможностей для вставок, массив считается полностью отсортированным, и работа алгоритма закончена.
- Реализация на PHP:
$array = [3, 7, 4, 4, 6, 5, 8];
for ($i = 1; $i < count($array); $i++) {
$x = $array[$i];
for ($j = $i - 1; $j >= 0 && $array[$j] > $x; $j--) {
$array[$j + 1] = $array[$j];
}
$array[$j + 1] = $x;
}
echo implode($array, ', ');
- Визуализация:
Сортировка выбором (Selection sort)
Сортировка выбором - это некий гибрид между пузырьковой и сортировкой вставками. Как и сортировка пузырьком, этот алгоритм проходит по массиву раз за разом, перемещая одно значение на правильную позицию. Однако, в отличие от пузырьковой сортировки, он выбирает наименьшее неотсортированное значение вместо наибольшего. Как и при сортировке вставками, упорядоченная часть массива расположена в начале, в то время как в пузырьковой сортировке она находится в конце.
Давайте посмотрим на работу сортировки выбором на нашем неотсортированном массиве:
3 4 7 4 6 5 8
При первом проходе алгоритм с помощью метода FindIndexOfSmallestFromIndex пытается найти наименьшее значение в массиве и переместить его в начало.
Имея такой маленький массив, мы сразу можем сказать, что наименьшее значение - 3, и оно уже находится на правильной позиции. На этом этапе мы знаем, что на первой позиции в массиве (индекс 0) находится самое маленькое значение, следовательно, начало массива уже отсортировано. Поэтому мы начинаем второй проход - на этот раз по индексам от 1 до n - 1.
На втором проходе мы определяем, что наименьшее значение - 4. Мы меняем его местами со вторым элементом, семеркой, после чего 4 встает на свою правильную позицию:
3 4 4 7 6 5 8
Теперь неотсортированная часть массива начинается с индекса 2. Она растет на один элемент при каждом проходе алгоритма. Если на каком-либо проходе мы не сделали ни одного обмена, это означает, что массив отсортирован. После еще двух проходов алгоритм завершает свою работу:
3 4 4 5 6 7 8
- Реализация на PHP:
$array = [3, 7, 4, 4, 6, 5, 8];
for ($i = 0; $i < count($array) - 1; $i++) {
$min = $i;
for ($j = $i + 1; $j < count($array); $j++) {
if ($array[$j] < $array[$min]) {
$min = $j;
}
}
$temp = $array[$i];
$array[$i] = $array[$min];
$array[$min] = $temp;
}
echo implode($array, ', ');
- Визуализация:
Сортировка слиянием (Merge sort)
Разделяй и властвуй.
До сих пор мы рассматривали линейные алгоритмы. Они используют мало дополнительной памяти, но имеют квадратичную сложность. На примере сортировки слиянием мы посмотрим на алгоритм типа "разделяй и властвуй" (divide and conquer).
Алгоритмы этого типа работают, разделяя крупную задачу на более мелкие, решаемые проще. Мы пользуемся ими каждый день. К примеру, поиск в телефонной книге - один из примеров такого алгоритма.
Если вы хотите найти человека по фамилии Петров, вы не станете искать, начиная с буквы А и переворачивая по одной странице. Вы, скорее всего, откроете книгу где-то посередине. Если попадете на букву Т, перелистнете несколько страниц назад, возможно, слишком много - до буквы О. Тогда вы пойдете вперед. Таким образом, перелистывая туда и обратно все меньшее количество страниц, вы, в конце концов, найдете нужную.
Насколько эффективны эти алгоритмы?
Предположим, что в телефонной книге 1000 страниц. Если вы открываете ее на середине, вы отбрасываете 500 страниц, в которых нет искомого человека. Если вы не попали на нужную страницу, вы выбираете правую или левую сторону и снова оставляете половину доступных вариантов. Теперь вам надо просмотреть 250 страниц. Таким образом мы делим нашу задачу пополам снова и снова и можем найти человека в телефонной книге всего за 10 просмотров. Это составляет 1% от всего количества страниц, которые нам пришлось бы просмотреть при линейном поиске.
Сортировка слиянием.
При сортировке слиянием мы разделяем массив пополам до тех пор, пока каждый участок не станет длиной в один элемент. Затем эти участки возвращаются на место (сливаются) в правильном порядке.
Давайте посмотрим на такой массив:
3 8 2 1 5 4 6 7
Разделим его пополам:
3 8 2 1 5 4 6 7
И будем делить каждую часть пополам, пока не останутся части с одним элементом:
3 8 2 1 5 4 6 7 3 8 2 1 5 4 6 7
Теперь, когда мы разделили массив на максимально короткие участки, мы сливаем их в правильном порядке:
3 8 1 2 4 5 6 7
Сначала мы получаем группы по два отсортированных элемента, потом "собираем" их в группы по четыре элемента и в конце собираем все вместе в отсортированный массив.
1 2 3 8 4 5 6 7 1 2 3 4 5 6 7 8
Для работы алгоритма мы должны реализовать следующие операции:
- Операцию для рекурсивного разделения массива на группы (метод Sort);
- Слияние в правильном порядке (метод Merge);
Стоит отметить, что в отличие от линейных алгоритмов сортировки, сортировка слиянием будет делить и склеивать массив вне зависимости от того, был он отсортирован изначально или нет. Поэтому, несмотря на то, что в худшем случае он отработает быстрее, чем линейный, в лучшем случае его производительность будет ниже, чем у линейного. Поэтому сортировка слиянием - не самое лучшее решение, когда надо отсортировать частично упорядченный массив.
- Реализация на PHP:
function merge_sort($array) {
if(count($array) == 1 ) return $array;
$middle = count($array) / 2;
$left = array_slice($array, 0, $middle);
$right = array_slice($array, $middle);
$left = merge_sort($left);
$right = merge_sort($right);
return merge($left, $right);
}
function merge($left, $right) {
$result = [];
while (count($left) > 0 && count($right) > 0) {
if($left[0] > $right[0]) {
$result[] = $right[0];
$right = array_slice($right , 1);
} else {
$result[] = $left[0];
$left = array_slice($left, 1);
}
}
while (count($left) > 0) {
$result[] = $left[0];
$left = array_slice($left, 1);
}
while (count($right) > 0) {
$result[] = $right[0];
$right = array_slice($right, 1);
}
return $result;
}
$array = [3, 7, 4, 4, 6, 5, 8];
echo implode(', ', merge_sort($array));
- Визуализация:
Быстрая сортировка (Quick sort)
Быстрая сортировка - это еще один алгоритм типа "разделяй и властвуй". Он работает, рекурсивно повторяя следующие шаги:
- Выбрать ключевой индекс и разделить по нему массив на две части. Это можно делать разными способами, но в данной статье мы используем случайное число.
- Переместить все элементы больше ключевого в правую часть массива, а все элементы меньше ключевого - в левую. Теперь ключевой элемент находится в правильной позиции - он больше любого элемента слева и меньше любого элемента справа.
- Повторяем первые два шага, пока массив не будет полностью отсортирован.
Давайте посмотрим на работу алгоритма на следующем массиве:
3 7 4 4 6 5 8
Сначала мы случайным образом выбираем ключевой элемент:
3 7 4 4 [6] 5 8
Теперь, когда мы знаем ключевой индекс (4), мы берем значение, находящееся по этому индексу (6), и переносим значения в массиве так, чтобы все числа больше или равные ключевому были в правой части, а все числа меньше ключевого - в левой. Обратите внимание, что в процессе переноса значений индекс ключевого элемента может измениться (мы увидим это вскоре).
Перемещение значений осуществляется методом partition:
3 5 4 4 [6] 7 8
На этом этапе мы знаем, что значение 6 находится на правильной позиции. Теперь мы повторяем этот процесс для правой и левой частей массива.
Мы рекурсивно вызываем метод quicksort на каждой из частей. Ключевым элементом в левой части становится пятерка. При перемещении значений она изменит свой индекс. Главное - помнить, что нам важно именно ключевое значение, а не его индекс.
3 [5] 4 4 [6] 7 [8] 3 4 4 [5] [6] 7 [8]
Снова применяем быструю сортировку:
[3] 4 4 [5] [6] [7] [8]
И еще раз:
[3] [4] 4 [5] [6] [7] [8]
У нас осталось одно неотсортированное значение, а, поскольку мы знаем, что все остальное уже отсортировано, алгоритм завершает работу.
- Реализация на PHP:
function quick_sort($array) {
$loe = $gt = [];
if(count($array) < 2) {
return $array;
}
$pivot_key = key($array);
$pivot = array_shift($array);
foreach($array as $val) {
if($val <= $pivot) {
$loe[] = $val;
} elseif ($val > $pivot) {
$gt[] = $val;
}
}
return array_merge(quick_sort($loe), array($pivot_key => $pivot), quick_sort($gt));
}
$array = [3, 7, 4, 4, 6, 5, 8];
echo implode(', ', quick_sort($array));
- Визуализация:
Пирамидальная сортировка (Heap sort)
Алгоритм, в основе которого лежит сравнение.
Алгоритм пирамидальной сортировки можно рассматривать как улучшенную версию алгоритма сортировки выбором: он делит входные данные на отсортированную и несортированную области, а затем последовательно уменьшает несортированную область, извлекая самый большой элемент и перемещая его в сортированную область. Улучшение состоит в том, что используется бинарная куча, а не алгоритм линейного поиска, чтобы найти наибольшее значение.
- Реализация на PHP:
function heapify(&$arr, $n, $i) {
$largest = $i;
$l = 2*$i + 1;
$r = 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($arr, $i, 0);
}
}
$arr = [3, 7, 4, 4, 6, 5, 8];
$n = sizeof($arr)/sizeof($arr[0]);
heapSort($arr, $n);
for ($i = 0; $i < $n; ++$i) {
echo ($arr[$i]." ");
}
- Визуализация:
Сортировка подсчётом (Counting sort)
Алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000.
- Реализация на PHP:
function counting_sort($my_array, $min, $max) {
$count = [];
for($i = $min; $i <= $max; $i++) {
$count[$i] = 0;
}
foreach($my_array as $number) {
$count[$number]++;
}
$z = 0;
for($i = $min; $i <= $max; $i++) {
while($count[$i]-- > 0) {
$my_array[$z++] = $i;
}
}
return $my_array;
}
$test_array = [3, 0, 2, 5, -1, 4, 1];
echo "Original array: ";
echo implode(', ', $test_array);
echo "Sorted Array: ";
echo implode(', ', counting_sort($test_array, -1, 5));
- Визуализация:
Поразрядная сортировка (Radix sort)
Массив несколько раз перебирается и элементы перегруппировываются в зависимости от того, какая цифра находится в определённом разряде. После обработки разрядов (всех или почти всех) массив оказывается упорядоченным. При этом разряды могут обрабатываться в противоположных направлениях - от младших к старшим или наоборот.
- Реализация на PHP:
// A function to do counting sort of arr[] according to the digit represented by exp.
function countSort(&$arr, $n, $exp) {
$output = array_fill(0, $n, 0);
$count = array_fill(0, 10, 0);
// Store count of occurrences in count[]
for ($i = 0; $i < $n; $i++) {
$count[ ($arr[$i] / $exp) % 10 ]++;
}
// Change count[i] so that count[i] now contains actual position of this digit in output[]
for ($i = 1; $i < 10; $i++) {
$count[$i] += $count[$i - 1];
}
// Build the output array
for ($i = $n - 1; $i >= 0; $i--) {
$output[$count[ ($arr[$i] / $exp) % 10 ] - 1] = $arr[$i];
$count[ ($arr[$i] / $exp) % 10 ]--;
}
// Copy the output array to arr[], so that arr[] now contains sorted numbers according to current digit
for ($i = 0; $i < $n; $i++) {
$arr[$i] = $output[$i];
}
}
// The main function to that sorts arr[] of size n using Radix Sort
function radixSort(&$arr, $n) {
// Find the maximum number to know number of digits
$m = max($arr);
// Do counting sort for every digit. Note that instead of passing digit number, exp is passed. exp is 10^i where i is current digit number
for ($exp = 1; $m / $exp > 0; $exp *= 10) {
countSort($arr, $n, $exp);
}
}
// A utility function to print an array
function PrintArray(&$arr, $n) {
for ($i = 0; $i < $n; $i++) {
echo $arr[$i] . " ";
}
}
// Driver Code
$arr = [170, 45, 75, 90, 802, 24, 2, 66];
$n = count($arr);
radixSort($arr, $n);
PrintArray($arr, $n);
- Визуализация:
Блочная сортировка (Bucket sort)
Блочная сортировка (Карманная сортировка, корзинная сортировка) - алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.
Элементы распределяются по корзинам:
Затем элементы в каждой корзине сортируются:
- Реализация на PHP:
function insertion_sort(&$elements, $fn = 'comparison_function') {
if (!is_array($elements) || !is_callable($fn)) return;
for ($i = 1; $i < sizeof($elements); $i++) {
$key = $elements[$i];
$j = $i - 1;
while ( $j >= 0 && $fn($key, $elements[$j]) ) {
$elements[$j + 1] = $elements[$j];
$j = $j - 1;
}
$elements[$j + 1] = $key;
}
}
function comparison_function(&$a, &$b) {
return $a < $b;
}
function bucket_sort(&$elements) {
$n = sizeof($elements);
$buckets = [];
for ($i = 0; $i < $n; $i++) {
$buckets[$i] = [];
}
foreach ($elements as $el) {
array_push($buckets[ceil($el/10)], $el);
}
$j = 0;
for ($i = 0; $i < $n; $i++) {
if (!empty($buckets[$i])) {
insertion_sort($buckets[$i]);
foreach ($buckets[$i] as $el) {
$elements[$j++] = $el;
}
}
}
}
$a = [-1, 0, 2, 3, -2];
echo "Original array: ";
insertion_sort($a);
echo "Sorted array: ";
var_dump($a);
Сортировка Шелла (Shell sort)
Алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами - это сортировка вставками с предварительными "грубыми" проходами.
- Реализация на PHP:
function shell_Sort($my_array) {
$x = round(count($my_array) / 2);
while($x > 0) {
for($i = $x; $i < count($my_array); $i++) {
$temp = $my_array[$i];
$j = $i;
while($j >= $x && $my_array[$j-$x] > $temp) {
$my_array[$j] = $my_array[$j - $x];
$j -= $x;
}
$my_array[$j] = $temp;
}
$x = round($x / 2.2);
}
return $my_array;
}
$test_array = [3, 0, 2, 5, -1, 4, 1];
echo "Original array: ";
echo implode(', ', $test_array);
echo "Sorted array: ";
echo implode(', ', shell_Sort($test_array));
- Визуализация:
