Сортировка простыми вставками в чем-то похожа на вышеизложенные методы.

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

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

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

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

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

1. Hайден элемент, меньший 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;
  }
}

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

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

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

Тогда при j=0 будет заведомо верно a[0] <= x. Цикл остановится на нулевом элементе, что и было целью условия j>=0.

Таким образом, сортировка будет происходить правильным образом, а во внутреннем цикле станет на одно сравнение меньше. С учетом того, что оно производилось Theta(n²) раз, это - реальное преимущество. Однако, отсортированный массив будет не полон, так как из него исчезло первое число. Для окончания сортировки это число следует вернуть назад, а затем вставить в отсортированную последовательность a[1]...a[n].

// сортировка вставками со сторожевым элементом
template<class T>
inline void insertSortGuarded(T a[], long size) {
  T x;
  long i, j;
  T backup = a[0];			// сохранить старый первый элемент

  setMin(a[0]);				// заменить на минимальный

  // отсортировать массив
  for ( i=1; i < size; i++) {  	
    x = a[i];
		 
    for ( j=i-1; a[j] > x; j--)
	  a[j+1] = a[j];

	a[j+1] = x;
  }

  // вставить backup на правильное место
  for ( j=1; j<size && a[j] < backup; j++)
    a[j-1] = a[j];

  // вставка элемента 
  a[j-1] = backup;
}

Функция setmin(T& x) должна быть создана пользователем. Она заменяет x на элемент, заведомо меньший(меньший или равный, если говорить точнее) всех элементов массива.

Copyright 2000-2002 © Ilia Kantor, при поддержке проекта MANUAL.RU