Сортировка с помощью прямого включения.

Введение.

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

В общем случае сортировку следует понимать как процесс перегруппировки, заданного множества объектов в определенном порядке.

Сортировка применяется для облегчения поиска элементов в упорядоченном множестве. Задача сортировки одна из фундаментных в программировании. В большинстве случаев необходимо отсортировать многочлен, элементами которого являются целые числа.Различают два вида сортировки: внутреннюю и внешнюю.

Под внутренней сортировкой понимают сортировку массивов, так как массив можно поместить на хранение в оперативную (внутреннюю) память.

Под внешней сортировкой понимают сортировку файлов, т.к. файлы хранящиеся во внешней памяти, не всегда могут поместиться в оперативной памяти.

Мы будем рассматривать только внутреннюю сортировку.

Общая задача сортировки: пусть имеется множество элементов А={б₁, б₂,…, б_p}. Под сортировкой будем понимать перестановку этих элементов в множество A’={б_k1, б_k2,…, б_kp}, где при некоторой упорядочивающей функции f:A®A’ выполняется соотношение f(б₁)£f(б₂)£… £f(б_p), причем, б_ki=f(б_i).

Описание алгоритма: пусть имеется множество А={б₁, б₂,…, б_p}

1. Разделим множество А на две части.

A={б₁, б₂,…, б_i}È{б_i+1,…, б_p}, обозначим их AL и AR

Предполагается, что часть АL уже отсортирована.

2. Возьмем первый элемент части АR и поместим его в часть АL так, чтобы его порядок не нарушился.

3. Продолжаем, указанный процесс, до тех пор, пока не будет исчерпана часть АR.

На начальном этапе предполагается, что АL содержит только первый элемент множества А.

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

Если порядок не нарушается, т. е. x³б_i, то x станет последним элементом множества.

Если выполняется х<б_i, то сдвинем на позицию вправо б_i+1®б_i+1 и будем сравнивать x с б_i Продолжаем процесс до тех пор, пока не найдем такой элемент б_j, что х³б_j.

Реализация алгоритма: составим процедуру, производящую сортировку линейного массива с помощью прямого включения.

Procedure IncludeSort(var a:TintVec; p:integer);

Var i, j, x: integer;

Begin

For i:=2 to p do (1)

Begin

x:=a[i];

j:=i; (2)

While (j>=2) and (x<a[j-1]) do

Begin

a[j]:=a[j-1]; (3)

j:=j-1;

End;

a[j]:=x;

End;

End.

Описание программы: блок (1) реализует циклический проход всех элементов некоторой части, в блоке (2) переменной х присваивается текущий просеиваемый элемент, j – номер просеиваемого элемента. Блок (3) реализует механизм просеивания.

Далее по окончании выполнения блока (3) переменная j содержит номер позиции вставки просеиваемого элемента и j-ому элементу присваивается просеиваемый элемент.

Анализ алгоритма.

Оценим количество обменов элементов. Минимальное количество M_min=3*(p-1), среднее число обменов M_ср=(p*p+9*p-10)/4, максимальное число обменов M_max=(p*p+3*p-4)/2.