Пример сортировки простыми вставками.

for todo

begin

; {вставить X на нужное место между mass[1] ,...,mass[i]}

end;

for todo

begin

;

;

while () and () do

begin

];

;

end;

;

end;

Улучшением может служить установление барьера.

for to do

begin

;

;

;

while do

begin

;

;

end;

;

end.

Также алгоритм сортировки простыми включениями можно улучшить, пользуясь тем, что готовая последовательность, в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее. Очевидно, что здесь можно применить бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения. Модифицированный алгоритм сортировки называется сортировкой бинарными включениями. Данное улучшение касается только числа сравнений.

Сортировка выбором

Суть сортировки прямым выбором: в сортируемой последовательности отыски­вается минимальный элемент. Найденный элемент меняется местами с первым элементом массива. Затем данный метод применяется ко всем элементам, кроме первого, т.е. к n-1-элементам, т.к. 1-ый элемент исходного набора уже будет находится на своем месте, после метод применяется к n-2-элементам и т.д. до тех пор, пока не останется один самый большой (минимальный)

Пример сортировки простым выбором.

Алгоритм:

ш.1) → ш.2)и ш.3)

ш.2) найти минимальный элемент в рассматриваемой последовательности и запомнить индекс найденного минимума

ш.3) Поменять местами первый с минимальным элементом, →ш.1)

Алгоритм Хоора (Hoare)

Суть: найти такой элемент множества, который разобьёт это множество на два подмножества, т.е. элементы, которые меньше делящего элемента, и элементы, что не меньше его. Данную идею можно реализовать различными способами. Например, в качестве делящего брать средний элемент массива.

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

Алгоритм Шелла (Shell)

Суть: сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на некотором расстоянии h методом простых вставок, затем шаг уменьшается и становится равным некоторому h₂ и после - снова выполняется сортировка методом простых вставок. Процесс продолжается до тех пор, пока шаг h_i не станет равным единице (h_i=1).

Записи

Запись - это структура данных, состоящая из фиксированного числа компонентов, называемых полями записи. В отличие от массива, компоненты (поля) записи могут быть различного типа. Чтобы можно было ссылаться на тот или иной ком­понент; записи, поля именуются. Идентификаторы компонент – идентификаторы полей.

Описание записи

Структура объявления типа записи такова:

<имя типа>: record <сп. полей> end;

<имя структуры>: record <сп. лолей> end;

Здесь <имя типа> — правильный идентификатор; record .. end — зарезервированные слова (запись, конец); <сп.полей> — список полей; представляет собой последовательность разделов записи, между которыми ставится точка с запятой.

Объявление полей аналогично объявлению переменных

<имя поля>: < тип поля >;

Пример:

var zapis : record

pole_1 : Byte;

pole_2 : String;

end;

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

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

Пример:

Type

TZapis_1 = record

pole_1_1: Byte;

pole_1_2: String;

end;

TZapis_2 = record pole_2_1: Char; pole_2_2: Real; pole_2_3: TZapis_1; pole_2_4: TZapis_2; end;

{ тип данных zapis_1 должен быть описан ранее} {ошибка, которая будет выявлена при компиляции}

Для того чтобы использовать данные описанного типа, необходимо описать сами данные.

var

z1: TZapis_1;

z2: TZapis_2;

Записи являются чрезвычайно удобным средством для представления программных моделей реальных объектов предметной области, потому что, как правило, каждый такой объект обладает; набором свойств, характеризуемых данными различных типов.

Пример записи — совокупность сведений о некотором студенте.

Объект «студент» обладает свойствами:

- «личный номер» — характеризуется целым положительным числом,

- «фамилия-имя-отчество» — характеризуется строкой символов и т.д.

Пример:

type

TDiscipline=record

math: real;

history: real;

…

end;

TStudent=record

num: byte;

name: string[20];

facult, group: string[7];

ocenki: TDiscipline;

end;

Один из вариантов использования отдельных записей — объединение их в массив, тогда описание массива будет выглядеть следующим образом

var

Students: array [1. .30] of TStudent;