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

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

Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале "вырастает" отсортированная последовательность.

Однако в сортировке «пузырьком» или «выбором» можно было четко заявить, что на i -м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее будут вставляться все новые элементы.

На i -м шаге работы алгоритма последовательность разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n].

На следующем, (i+1)- м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте (вставка завершена), либо они меняются местами и процесс повторяется (рис. 8).

0

1

3

4

Последовательность на текущий момент. Часть a[0]…a[2] уже упорядочена.

2 ↔ 4

2 ↔ 3

Вставка завершена

0

1

3

2

4

0

1

2

3

4

0

1

3

4

Вставка числа 2 в отсортированную подпоследовательность. Сравниваемые пары выделены

Рис. 8

Таким образом, в процессе вставки мы "просеиваем" элемент x к началу массива, останавливаясь в случае, когда:

1) найден элемент, меньший x, или

2) достигнуто начало последовательности.

Иногда этот метод называют сортировкой «просеиванием».

template<class T>void insertSort(T a[], long size) { T x; long i, j; for (i=0; i < size; i++) { // цикл проходов, i - номер прохода x = a[i]; // поиск места элемента в готовой последовательности for (j=i-1; j>=0 && a[j] > x; j--) a[j+1] = a[j]; // сдвигаем элемент направо, пока не дошли // место найдено, вставить элемент a[j+1] = x; }}

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

Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет «досортирован» очень быстро. Именно эти качества алгоритма делают его широко применимым на практике в соответствующих ситуациях.

Дата добавления: 2014-12-27