Паскаль (Pascal) разрабатывался, как учебный язык выского уровня, структурного программирования. Относится к 3-му поколению языков программирования. На основе ALGOL.
Составные типы данных – типы данных базирующиеся на простых. Важна однотипность элементов и способ доступа, позволяющие выделить главные представители сложных типов.
Массив - набор однотип переменных, каждому эл-ту которого присвоен некот поряд номер, что обеспечивает простоту доступа к каждому эл-ту.
Массивы могут быть одномерными и многомерными
Описание при помощи слова array в разделе описания типов
Алгоритм сортировки - алгоритм упорядочения элементов в списке
Сортировка массива - процесс перестановки его элементов в опред порядке
Основ требов к методам сортировки - экономия использования памяти
Сортировка перемешиванием(Шейкерная) - устойчивая(слож-ть n^2)
(по возраст) 1.Обозначим каждый пройденный путь от начала до конца Wi, а обратный Wj
2. После Wi один из неустойч. эл-тов будет перемещен в поз справа как наиб, а после Wj наим из неотсорт. переместится в поз слева
3. И т.д. до отсортировки массива
procedure ShakerSort(Mas: Massiv; Start, m: integer);
var Left, Right, temp, i: integer;
begin
Left:=Start; Right:=m;
while Left<=Right do
begin
for i:=Right downto Left do
if (Mas[i-1]>Mas[i]) then
begin
temp:=Mas[i];
Mas[i]:=Mas[i-1];
Mas[i-1]:=temp;
end;
Left:=Left+1;
for i:=Left to Right do
if Mas[i-1]>Mas[i] then begin
temp:=Mas[i];
Mas[i]:=Mas[i-1];
Mas[i-1]:=temp;
end; Right:=Right-1;
end;
for i:=1 to M do write(' ', Mas[i]); end;
Сортировка вставками - устойчивая, сложность n^2
"+" Простота, эффект на частично упоряд. или состоящих из небольшого числа эл-тов
(По возраст) 1. Сравниваем 2 первых эл-та, если 2<1, то 1<->2, если 2>1, то ничего не меняется
2. Рассмотрим 3 эл-т. 2.1. 1<3,2<3, =>1-2-3
2.2. 1>3, 2>3, => 3-1-2
2.3. 1<3, 2>3 => 1-3-2
2.4. 1>3, 2<3 => 3-2-1
3. И т.д. до последнего эл-та
var i, j, temp, nom, n: integer;
procedure InsertSort(mas: arr; n: integer);
begin
for i:=1 to n-1 do begin
nom:=i+1;
temp:=mas[nom];
for j:=i+1 downto 2 do begin
if (temp
mas[j]:=mas[j-1];
nom:=j-1;
end; end;
mas[nom]:=temp; end;
write('Результирующий массив: ');
for i:=1 to n do write(mas[i], ' '); end;
Блочная сортировка - устойчивая, сложность n, требуется K доп памяти
1. Разделяем все элементы по конечному числу отдел блоков
2. Сортируем каждый блок отдельно
3. Помещаем элементы обратно в массив
var i,j,n,k:longint;
a:array[1..100000] of longint;
b:array[1..1000,1..1000] of longint;
razmer:array[1..1000] of integer;
{с помощью QSort мы будем сортировать карманы}
procedure QSort(first,last:integer);
var L,R,c,X:integer;
begin
if first < last then begin
X:= b[i,(first + last) div 2];
L:= first;R:= last;
while L <= R do begin
while b[i,L] < X do
L:= L + 1;
while b[i,R] > X do
R:= R - 1;
if L <= R then begin
c:=b[i,L]; b[i,L]:=b[i,R];
b[i,R]:=c;L:=L+1;
R:=R-1;end;end;
QSort(first, R);
QSort(L, last);
end;end;
{заполняем массив}
begin
read(n);
for i:=1 to n do
a[i]:=random(10000);
{разбиваем массив на карманы}
for i:=1 to n do begin
b[(a[i] div 10)+1,razmer[(a[i] div 10)+1]+1]:=a[i];
razmer[(a[i] div 10)+1]:=razmer[(a[i] div 10)+1]+1;
end;
{сортируем карманы}
for i:=1 to 1000 do
if razmer[i]<>0 then Qsort(1,razmer[i]);
{восстанавливаем массив}
k:=0;
for i:=1 to 1000 do
for j:=1 to razmer[i] do begin
k:=k+1; a[k]:=b[i,j];
end;
{выводим отсортированный массив}
writeln; writeln;
for i:=1 to n do
write(a[i],' ');
end.
11.
