§ 18. Сортировка одномерного массива

18.4. Сортировка простыми вставками

Будем просматривать элементы массива a, начиная со второго. Каждый новый элемент a[i] будем вставлять на подходящее место в уже упорядоченную часть массива a[1], ..., a[i–1]. Место вставки определяется путем сравнения элемента a[i] с упорядоченными элементами a[1], ..., a[i–1].

Такой метод сортировки называется сортировкой простыми вставками. Он также требует порядка n2 операций сравнения и столько же перестановок элементов в массиве.

Рассмотрим ее работу на массиве а = {9, 6 0, 2, 7, 3, 1, 5} (примеры 18.11). Цветом выделены элементы уже отсортированной части.

Формальное описание алгоритма. На i-м шаге (i = 1, …, n – 1) выполняем:

1. Берем первый элемент в неотсортированной части массива.
2. Последовательно сравниваем его с элементами в отсортированной части, до тех пор, пока не определим место для вставки.
3. Сдвигаем элементы вправо на один, освобождая место для вставки.

Фрагмент программы, содержащий алгоритм сортировки простыми вставками, приведен в примере 18.12.

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

Пример 18.11. Сортировка массива методом простых вставок:

Пример 18.12. Фрагмент программы сортировки простыми вставками.

for (int k = 1; k < n; k++) {

  int i = k;

  while (i > 0 && a[i - 1] > a[i]){

    swap(a[i - 1], a[i]);

    i--;

  }

}

В 2000 г. в научном издании Newsletter университета Глазго был опубликован алгоритм под названием «Глупая сортировка»1. Автор — Хамид Сарбази-Асад (Hamid Sarbazi-Azad). Чуть позже голландский ученый Дик Грун (Dick Grune) исследовал метод подробнее и переименовал его в «Гномью сортировку». Под этим именем алгоритм сейчас и известен. «Гномья сортировка» основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу, он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперед, иначе меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперед; если нет следующего горшка, он закончил.

Пример 18.13. Фрагмент программы «гномьей сортировки».

while (i < n) {

  if (i == 0 || a[i - 1] <= a[i])

    i++;

  else {

    swap (a[i], a[i-1]);

    i--;

  }

}

[1] Глупой сортировкой обычно называют другой алгоритм: http://algolab.valemak.com/stupid.