Паскаль (Pascal) разрабатывался, как учебный язык выского уровня, структурного программирования. Относится к 3-му поколению языков программирования. На основе ALGOL.
Составные типы данных – типы данных базирующиеся на простых. Важна однотипность элементов и способ доступа, позволяющие выделить главные представители сложных типов.
Массив - набор однотип переменных, каждому эл-ту которого присвоен некот поряд номер, что обеспечивает простоту доступа к каждому эл-ту.
Массивы могут быть одномерными и многомерными
Описание при помощи слова array в разделе описания типов
Алгоритм сортировки - алгоритм упорядочения элементов в списке
Сортировка массива - процесс перестановки его элементов в опред порядке
Основ требов к методам сортировки - экономия использования памяти
Сортировка двоичным деревом: левый преемник всегда <, а правый всегда > или = предшественнику (сложность O(n log n)), требуется О(n) доп памяти)
При добавлении элемента сравниваем его последовательно с нижестоящими узлами
type
TType = integer;
arrType = array[1 .. n] of TType;
const a: arrType = (44, 55, 12, 42, 94, 18, 6, 67);
type PTTree = ^TTree;
TTree = record
a: TType;
left, right: PTTree; end;
procedure SortTree(var a: arrType; n: integer);
var root: PTTree; i: integer;
begin
root := nil;
for i := 1 to n do
root := AddToTree(root, a[i]); // добавление в дерево
TreeToArray(root, a) // заполнение массива
end;
procedure TreeToArray(root: PTTree; var a: arrType);
const maxTwo: integer = 1;
begin
if root = nil then exit;
TreeToArray(root^.left, a); (* Левое поддерево *)
a[maxTwo] := root^.a; Inc(maxTwo);
TreeToArray(root^.right, a); (* Правое поддерево *)
Dispose(root); end;
function AddToTree(root: PTTree; nValue: TType): PTTree;
begin
if root = nil then begin (* При отсутствии преемника создать новый элемент *)
root := new(PTTree);
root^.a := nValue;
root^.left := nil;
root^.right := nil;
AddToTree := root; exit; end;
if root^.a < nValue then
root^.right := AddToTree(root^.right, nValue) else
root^.left := AddToTree(root^.left, nValue);
AddToTree := root; end;
Пирамидальная сортировка (слож-ть О(n log n)) превращаем список в кучу, берем наиб и добавляем в конец
Прога:Type arrType = Array[1 .. n] Of Integer;
Procedure HeapSort(Var ar: arrType; n: Integer);
Var i, Left, Right: integer;
x: Integer;
Procedure sift;
Var i, j: Integer;
Begin
i := Left; j := 2*i; x := ar[i];
While j <= Right Do Begin
If j < Right Then
If ar[j] < ar[Succ(j)] Then Inc(j);//succ- возврат след. за x значение
If x >= ar[j] Then Break;
ar[i] := ar[j];
i := j; j := 2 * i;
End; ar[i] := x; end;
Var T: Integer;
Begin
Left := Succ(n div 2); Right := n;
While Left > 1 Do Begin
Dec(Left); sift;End;
While Right > 1 Do Begin
T := ar[ Left ]; ar[ Left ] := ar[ Right ]; ar[ Right ] := T;
Dec(Right); sift; End; End.//dec - уменьшить на 1
12.
