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

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

Лекция 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). Определим операцию сравнения двух объектов r1=(x1,y1) и r2=(x2,y2) так: r1<r2 тогда и только тогда, когда x1<x2 или y1<y2. Удовлетворяет ли такое сравнение вышеприведенному условию? Возьмем 3 вектора: a=(3,9), b=(4,7), c=(1,8). По описанному способу сравнения получаем: a<b, b<c, но a не меньше c. Таким образом, при выборе этого отношения порядка не в каждом случае можно упорядочить заданную последовательность элементов.

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