Билет 8

1. Обменная сортировка.

Название этой группы методов произошло от основного типа операций, используемого в алгоритмах - обмен двух элементов в файле своими значениями. Эта операция используется и в других группах, поэтому классификацию нельзя признать вполне строгой, но данное разделение, тем не менее, является традиционным. Файл, подлежащий сортировке, в общем случае состоит из элементов-записей, включающих информационную часть и ключи, по которым производится упорядочение по возрастанию. Поскольку информационная часть почти не влияет на процесс сортировки, будем предполагать, что файлы, используемые в примерах, состоит только из элементов-ключей, а информационная часть записи отсутствует.

Метод обмена ("пузырька") один из самых простых методов внутренней сортировки. Суть алгоритма состоит в последовательном просмотре массива от конца к началу или от начала к концу и сравнении каждой пары элементов между собой. При этом "неправильное" расположение элементов устраняется путем их перестановки. Процесс просмотра и сравнения элементов повторяется до просмотра всего массива. При сортировке по возрастанию "легкие" элементы с меньшим значением как бы "всплывают" к началу массива подобно тому, как это делают пузырьки воздуха в стакане с водой - отсюда и происходит популярное название алгоритма.

"Пузырьковая" сортировка имеет очень плохие временные характеристики. Она имеет только учебно-исторический интерес и не может быть рекомендована для практического использования.

Одна из возможных версий процедуры, реализующей алгоритм "пузырька", представлена на языке программирования Pascal. Массив для сортировки X[n] и его размер n считаются глобальными переменными. Тип элементов массива - целый. Сортировка осуществляется по возрастанию.

procedure Puzirek;

var i, j : integer;

y : integer;

begin

for i := 2 to n do

for j := n downto i do

if x[j-1] > x[j] then

begin

y:=x[j-1];

x[j-1]:=x[j];

x[j]:=y

end;

end;

2. Объекты

Объект – тип данных, аналогичный записи (record), с которым связан некоторый набор процедур и функций (называемых методами). Для каждого объекта мы можем создавать любое количество экземпляров объекта.

Конструкторы и деструкторы

Конструкторы (Constructors).

Конструктор – это специальный метод, который создает и инициализирует объект. Объявление конструктора выглядит как объявление процедуры, однако начинается со слова constructor. Примеры:

constructor Create;

constructor Create(AOwner: TComponent);

Деструкторы (Destructors).

Это специальные методы, которые разрушают объекты и освобождают занимаемую ими память. Объявление деструктора подобно объявлению процедуры, но вместо слова процедура указывается destructor, например

destructor Destroy;

destructor Destroy; override;

Виртуальный метод (виртуальная функция) — в объектно-ориентированном программировании метод (функция) класса, который может быть переопределён в классах-наследниках так, что конкретная реализация метода для вызова будет определяться во время исполнения. Таким образом, программисту необязательно знать точный тип объекта для работы с ним через виртуальные методы: достаточно лишь знать, что объект принадлежит классу или наследнику класса, в котором метод объявлен.

Виртуальные методы — один из важнейших приёмов реализации полиморфизма. Они позволяют создавать общий код, который может работать как с объектами базового класса, так и с объектами любого его класса-наследника. При этом базовый класс определяет способ работы с объектами и любые его наследники могут предоставлять конкретную реализацию этого способа.