Внутренняя сортировка

Внутреннюю сортировку иногда называют сортировкой массивов, поскольку сортируемая во внутренней памяти таблица, как правило, организуется как вектор записей. Основное требование к методам сортировки массивов - экономное использование памяти. Это означает, что переупорядочение элементов нужно выполнять на том же месте, где и расположен массив, и что методы, которые пересылают элементы из одного массива в другой, не представляют интереса. Такие методы называются сортировками «на том же месте» (in sity).

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

- простые методы особенно хорошо подходят для разъяснения свойств большинства принципов сортировки;

- программы, основанные на этих методах, легки для понимания и коротки;

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

Более сложные по сравнению с прямыми сортировками методы (Шелла, пирамидальная сортировка и т. д.) называются усовершенствованными сортировками; они применяются для упорядочения больших (по количеству элементов) таблиц.

Методы, сортирующие элементы «на том же месте», можно разбить на три основных класса в зависимости от лежащего в их основе приема:

1) сортировка включениями (вставками),

2) сортировка выбором (выделением),

3) сортировка обменом.

11.2.1 Сортировка прямыми включениями

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

a[0].Кey £ a[1].Кey £ ... £ a[i-1].Кey

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

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

В общем виде алгоритм сортировки прямыми включениями выглядит следующим образом:

 

For i:=1 To HighIndex Do