Алгоритмы сортировки

Алгоритмы сортировки

Лекция 7

Обращение к элементам записи

Тип запись

 Синтаксис

RECORD

<Список имен 1>:<Тип 1>;

<Список имен 2>:<Тип 2>;

∙ ∙ ∙

<Список имен N>:<Тип N>;

END

При описании переменной типа «запись» в памяти создается последовательность переменных различного типа (сравните с типом массив, который описывает последовательность переменных одного типа).

 Пример

TYPE

Date=RECORD

Day:1..31;

Month:(Jan,Feb,Mar,…,Nov,Dec);

Year:Integer;

END;

Student=RECORD { К примеру со списком студентов}

Fam,Name,Pat:STRING;

Fakultet:(MM,RT,MT,FT, …);

Group:Integer;

END;

VAR

D:Date;

S:ARRAY [1..100] OF Student;

Осуществляется с помощью оператора «.» (точка).

 Пример

D.Day:=23;

D.Month:=Oct;

D.Year:=2002;

S[5].Fam:='Иванов';

S[5].Fakultet:=MM;

Переменные одного и того же типа «запись» можно присваивать друг другу:

 Пример

S[4]:=S[5];

Таким образом, тип «запись» позволяет группировать данные различного типа в одной переменной (или, например, в одном элементе
массива).

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

Все алгоритмы сортировки можно поделить на две группы: сортировка сравнениями и лексикографическая сортировка. Эти два вида алгоритмов отличаются тем, что при сортировке сравнениями неизвестна внутренняя структура объектов. При этом они вообще могут иметь различную структуру, необходимо только уметь сравнивать объекты друг с другом (например, числа). На самом деле только одного сравнения объектов недостаточно, оно должно обладать еще некоторыми дополнительными свойствами, например транзитивностью, т.е. если a < b и b < c, то должно быть a < c. Предположим, что мы должны сравнивать вектора фактически являющиеся парами чисел вида r =(x, y). Определим операцию сравнения двух объектов r₁ =(x₁, y₁) и r₂ =(x₂, y₂) так: r₁ < r₂ тогда и только тогда, когда x₁ < x₂ или y₁ < y₂. Удовлетворяет ли такое сравнение вышеприведенному условию? Возьмем 3 вектора: a =(3,9), b =(4,7), c =(1,8). По описанному способу сравнения получаем: a < b, b < c, но a не меньше c. Таким образом, при выборе этого отношения порядка не в каждом случае можно упорядочить заданную последовательность элементов.

Лексикографическая сортировка обычно применяется при сортировке объектов с известной внутренней структурой. Например, упорядочивание текстовых строк по алфавиту. Внутренняя структура строк известна: строка состоит из символов; количество символов алфавита ограничено.