Сортировка пузырьком (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)

Быстрая сортировка - это еще один алгоритм типа "разделяй и властвуй". Он работает, рекурсивно повторяя следующие шаги:

  1. Выбрать ключевой индекс и разделить по нему массив на две части. Это можно делать разными способами, но в данной статье мы используем случайное число.
  2. Переместить все элементы больше ключевого в правую часть массива, а все элементы меньше ключевого - в левую. Теперь ключевой элемент находится в правильной позиции - он больше любого элемента слева и меньше любого элемента справа.
  3. Повторяем первые два шага, пока массив не будет полностью отсортирован.

Давайте посмотрим на работу алгоритма на следующем массиве:

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));

test