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

Внутреннюю сортировку иногда называют сортировкой массивов, поскольку сортируемая во внутренней памяти таблица, как правило, организуется как вектор записей. Основное требование к методам сортировки массивов - экономное использование памяти. Это означает, что переупорядочение элементов нужно выполнять на том же месте, где и расположен массив, и что методы, которые пересылают элементы из одного массива в другой, не представляют интереса. Такие методы называются сортировками «на том же месте» (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

Begin

x:=a[i];

<вставить x на подходящее место
в a[0]. . . a[i-1]>;

end;

Процесс сортировки прямыми включениями показан на примере восьми случайно взятых чисел:

На i-ом проходе i-ый ключ сравнивается с (i-1)-ым ключом, и если a[i-1].Кey > a[i].Кey, то элементы a[i-1] и a[i] обмениваются местами. Затем «новый» ключ a[i-1].Кey сравнивается с предыдущим ключом a[i-2].Кey и т. д. Таким образом, на каждом проходе часть элементов готовой последовательности сдвигается на одну позицию вправо, освобождая место для включаемого элемента. Этот процесс называется «просеиванием» элемента a[i].

Алгоритм сортировки прямыми включениями может иметь следующую реализацию:

Рrocedure DirInsSort;

Var i, j: Integer;

x: TElement;

Begin

For i:=1 To HighIndex Do Begin

For j:= i-1 Downto 0 Do

If a[j+1].Кey < a[j].Кey