Массивы

Размер через константу

Описание:

имя

начальный индекс

конечный индекс

тип
элементов
var A: array[1.. ] of integer;

const N=5;

N

var A : array[ 1 .. 5 ] of integer ;

Var
a,b: array [1..10] of real;
c: array [1..10] of char;
d:array [1..2, 1..5] of real;
Begin
a:=b;
a:=c; a:=d;

Все остальные действия выполняются с элементами массива и зависят от типа данных элементов.

Для работы с массивами используется цикл с параметром.

Псевдослучайные числа – обладают свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле.

Для обработки чаще всего используются вложенные циклы с параметром. Двумерные массивы часто называют матрицей.

Главная и побочная диагонали

сложность O(N2)

начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами
за 1 проход по массиву один элемент (самый маленький) становится на свое место

1-ый проход

2-ой проход

3-ий проход

Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов).

A[j] и A[j+1]

2-ой проход

for j:=N-1 downto 2 do
if A[j] > A[j+1] then begin
c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c;
end;

2

for j:=N-1 downto 1 do
if A[j] > A[j+1] then begin
c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c;
end;

1

i-ый проход

for j:=N-1 downto i do
...

i

for i:=1 to N-1 do begin
for j:=N-1 downto i do
if A[j] > A[j+1] then begin
с := A[j];
A[j] := A[j+1];
A[j+1] := с;
end;
end;

i

элементы выше A[i] уже поставлены

repeat
flag := False; { сбросить флаг }
for j:=N-1 downto 1 do
if A[j] > A[j+1] then begin
с := A[j];
A[j] := A[j+1];
A[j+1] := с;
flag := True; { поднять флаг }
end;
until not flag; { выход при flag=False }

flag := False;

flag := True;

not flag;

var flag: boolean;

i := 0;

i

i := i + 1;

N-1

N

нужно N-1 проходов

поиск минимального от A[i] до A[N]

если нужно, переставляем

i+1

i

N div 2

2 шаг: переставить элементы так:
при сортировке элементы не покидают « свою область»!

1 шаг: выбрать некоторый элемент массива X

3 шаг: так же отсортировать две получившиеся области

Разделяй и властвуй (англ. divide and conquer)

Разделение:
выбрать средний элемент массива (X=67)
установить L:=1, R:=N
увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа)
уменьшая R, найти первый элемент A[R], который <= X (должен стоять слева)
если L<=R, поменять местами A[L] и A[R] и перейти к п. 3

ограничение рекурсии

while L <= R do begin
while A[L] < X do L:= L + 1;
while A[R] > X do R:= R - 1;
if L <= R then begin
c:= A[L]; A[L]:= A[R]; A[R]:= c;
L:= L + 1; R:= R - 1;
end;
end;

разделение

обмен

двигаемся дальше

сортируем две части

procedure QSort ( first, last: integer);
...