Сортировка вставками

Прямые и быстрые методы внутренней сортировки

Все методы внутренней сортировки делятся на прямые и быстрые (или улучшенные) [7].

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

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

Методы внутренней сортировки можно разбить в соответствии с определяющими их принципами на три класса:

1. Сортировка вставками: элементы просматриваются по одному, и каждый новый элемент вставляется на подходящую позицию среди ране упорядоченных элементов.

2. Сортировка с помощью выбора: сначала выделяется наименьший (или наибольший) элемент и каким-либо образом отделяется от остальных, затем выбирается наименьший (наибольший) из оставшихся элементов и т.д.

3. Сортировка с помощью обмена: последовательно просматриваются пары соседних элементов; если элементы в паре образуют инверсию (т.е. неупорядочены), то они меняются местами.

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

Улучшенный метод обмена – Шейкерная сортировка, метод Хоара (самый быстрый из известных на сегодняшний день методов внутренней сортировки),

усовершенствование сортировки прямого включения – метод Шелла,

прямого выбора – сортировка с помощью бинарного дерева.

Рассмотрим процесс сортировки методом вставки (прямого включения) массива а[1], а[2], ..., a[n]. Вначале в исходном массиве выделяется уже отсортированная, например по неубыванию, часть а[1] ≤ а[2] ≤...≤ а[i-1] и не отсортированная a[i], a[i+l],..., a[n]. Затем с шагом 1, начиная с i = 2 чередуя сравнения и перемещения элемента a[i], в отсортированной части массива определяется такой индекс (ключ) j (1 ≤ j ≤ i -1), чтобы выполнялись неравенства a[j-l] ≤ a[i] ≤ a[j]. Если такой индекс найден, то элемент a[i] вставляется на соответствующее место. Для этого выполняется сдвиг на одну позицию вправо элементов отсортированной части: a[j], …, а[i-1]. После этого осуществляется переход к следующему значению i. В противном случае просто происходит переход к следующему значению i. С каждым шагомотсортированная часть массива увеличивается на один элемент. Очевидно, что для выполнения полной сортировки потребуется n -1 шаг, где n - число элементов исходного массива.

Покажем процесс сортировки вставками на примере целочисленного массива а[1..12], состоящего из чисел 22, -14, 13, 28, 6, 41, -5, 18, 0, 35, 6,-15 (значком * обозначены вставленные элементы, выделены элементы отсортированной части)

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

· найден первый слева элемент a[j] ≥ a[i], что говорит о необходимости вставки a[i] между a[j] и a[j-1], в частности, если j=1, то a[i] помещается в первую позицию, что влечет за собой необходимость увеличения диапазона индекса массива на единицу;

· достигнут правый конец отсортированной части массива (правый барьер), следовательно, элемент a[i] нужно оставить на прежнем месте.

Заметим, что сравнение и перемещение элемента a[i] в отсортированной части массива можно проводить и справа налево, начиная с (i-1)-го элемента.