Сортировка вставкой на PHP

Не давно мы рассматривали сортировку выбором, а сейчас рассмотрим сортировку вставкой, оценим ее плюсы и минусы в работе, а так же сравним с сортировкой выбором.

Сортировка вставкой очень похоже на естественное поведение человека, когда он, что то сортирует по порядку. Например вы хотите отсортировать купюры в бумажнике по порядку, и скажем у вас есть следующие купюры в данном порядке:

  • 1) 50
  • 2) 100
  • 3) 1000
  • 4) 500

Что бы минимизировать количество "вытаскивания и вставки" купюр с места на место, вы явно возьмете купюру номиналом 500 и поместите (вставите) ее между 100 и 1000, так как 500 меньше 1000, но больше 100.

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

Давайте рассмотрим код на PHP, что бы было более наглядно:

function insertionSort($mas, $masCount)
{
    for($i = 1; $i < $masCount; $i++)
    {
        $rightValue = $mas[$i];
        $leftValue = $i - 1;
        
        while($leftValue >= 0 && $mas[$leftValue] > $rightValue)
        {
            $mas[$leftValue+1] = $mas[$leftValue];
            $leftValue--;
        }
        
        $mas[++$leftValue] = $rightValue;
    }
    
    return $mas;
}

На вход функция принимает сортируемый массив mas и количество элементов в массиве masCount.

Сама функция построена из внешнего и внутреннего цикла, внешний цикл проходит по всему массиву со смещением в единицу i=1, а не 0, а внутренний цикл работает до тех пор, пока правый элемент не упрется в начало цикла или не найдет элемент меньше или равный себе по значению.

Внешний цикл идет от i до masCount, так как нам нужно пройтись по всему массиву, рассмотреть каждое значение. При входе во внешний цикл мы фиксируем две переменные rightValue = текущее значение под индексом i (то есть значение из внешнего цикла), и leftValue, которое равно i-1, то есть индекс (и следовательно значение) слева от i.

Если рассмотреть более предметно, то получается, что сначала сортировки (При первом входе во внешний цикл) мы берем пару под индексами 0-leftValue и 1-rightValue.
Причем в rightValue находится само значение элемента под индексом i, а в leftValue хранится индекс элемента, который будет сравниваться с rightValue.

Далее мы открываем внутренний цикл с условием выхода из цикла при
1) leftValue меньше нуля (то есть когда мы достигли крайнего левого индекса в массиве, то есть его начала)
2) Если leftValue будет меньше rightValue.

Заметьте, что важна именно такая последовательность условий, так как у нас используется логический оператор И, то при ложном положении первого условия, дальнейшие условия не выполняются.
Если бы первым было условие $mas[$leftValue] > $rightValue, то мог бы произойти выход за пределы массива, то есть обращение к индексу -1, которого у нас нет.

Во внутреннем цикле мы приравниваем значение под индексом leftValue к значению под индексом leftValue+1, то есть больший элемент смещаем на одну позицию вправо (при первом вхождении это будет индекс i).

После чего мы уменьшаем на единицу значение leftValue, то есть смещаемся на одну позицию левее по массиву, что бы при повторной итерации внутреннего цикла сравнить следующую пару.

После выхода из внутреннего цикла мы приравниваем значение, которое хранится в rightValue (изначально под индексом i), индексу под номером leftValue+1 (потому что мы минусовали на единицу в конце внутреннего цикла), то есть тому элементу на котором мы остановили внутренний цикл.

Теперь рассмотрим плюсы и минусы сортировки вставкой.
Наихудшее время выполнения данного алгоритма O(n^2), это может быть если входящий массив отсортирован по убыванию, чего на практике быть не должно, если вам надо перевернуть массив, лучше использовать другие алгоритмы.

Плюсы данного алгоритма в том, что внутренний цикл чаще всего на практике будет стремится к masCount/2, если массив равномерно заполнен рандомизированными значениями.

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

Но наихудший и наилучший вариант на практике не встречаются, истинна, где то посередине, поэтому среднее время работы данного алгоритма на практике будет, где то n^2/2, лично в моих тестах оно было еще меньше, где то n^2/4.

Минусы разумеется очевидны, чем больше массив, и чем больше разброс значений в нем, тем больше время работы будет стремится к n^2.

Сравнение с сортировкой выбором.
В моих тестах был массив в n (100, 1000, 10000) элементов, заполненный случайными значениями от 1 до 1000000. В случае размерности массива в 100 элементов сортировка вставками обгоняла на 100% сортировку выбором (в два раза быстрее). При массиве в 1000 элементов 80%, а вот при массиве в 10000 элементов всего лишь на 20%.

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


comments powered by Disqus