Массивы

Что это?
Массив – упорядоченная последовательность данных одного типа, объединённых одним именем.
Размер через константу
Описание:
имя
начальный индекс
конечный индекс
тип
элементов
var A: array[1.. ] of integer;
const N=5;
N
var A : array[ 1 .. 5 ] of integer ;

Как устроен?
A
массив
3
15
НОМЕР
элемента массива
(ИНДЕКС)
A[1]
A[2]
A[3]
A[4]
A[5]
ЗНАЧЕНИЕ элемента массива
A[2]
НОМЕР (ИНДЕКС)
элемента массива: 2
ЗНАЧЕНИЕ
элемента массива: 10

Действия с массивами
Единственная операция, возможная с массивом – присваивание, но только в случае, когда размерность массивов и тип элементов совпадают.
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;
Все остальные действия выполняются с элементами массива и зависят от типа данных элементов.

Заполнение и обработка массивов
Задание:
… Begin
for i:=1 to N do {ввод данных}
begin
writeln(‘Введите элемент');
readln(a[i]);
end;
for i:=1 to N do {вывод данных}
write(a[i]:4);
Для работы с массивами используется цикл с параметром.

Генерация случайных величин
Ф random; - генерирует вещественное число в диапазоне от 0 до 1.
Ф random(x); - генерирует целое число в диапазоне от 0 до х (х – целое число).
Пример:
Begin
y:=random(1000);
Псевдослучайные числа – обладают свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле.

Многомерные массивы
Многомерные массивы – массивы, размерность которых больше либо равна двум.
Var
mas: array [1..5,1..10] of integer;
Begin
for i:=1 to 5 do {ввод данных}
for j:=1 to 10 do
mas[i,j]:=random(100);
Для обработки чаще всего используются вложенные циклы с параметром. Двумерные массивы часто называют матрицей.
Главная и побочная диагонали

Сортировка элементов массива

Сортировка
Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, сумме делителей, …).
Задача: переставить элементы массива в порядке возрастания.
Алгоритмы:
простые и понятные, но неэффективные для больших массивов
метод пузырька
метод выбора
сложные, но эффективные
«быстрая сортировка» (Quick Sort)
сортировка «кучей» (Heap Sort)
сортировка слиянием
пирамидальная сортировка
сложность O(N2)

Метод пузырька
Идея – пузырек воздуха в стакане воды поднимается со дна вверх.
Для массивов – самый маленький («легкий» элемент перемещается вверх («всплывает»).
начиная снизу, сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами
за 1 проход по массиву один элемент (самый маленький) становится на свое место
1-ый проход
2-ой проход
3-ий проход
Для сортировки массива из N элементов нужен
N-1 проход (достаточно поставить на свои места N-1 элементов).

Программа
1-ый проход:
сравниваются пары
A[N-1] и A[N], A[N-2] и A[N-1]
…
A[1] и A[2]
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

Программа
program qq;
const N = 10;
var A: array[1..N] of integer;
i, j, c: integer;
begin
{ заполнить массив }
{ вывести исходный массив }
{ вывести полученный массив }
end.
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] уже поставлены

Метод пузырька с флажком
Идея – если при выполнении метода пузырька не было обменов, массив уже отсортирован и остальные проходы не нужны.
Реализация: переменная-флаг, показывающая, был ли обмен; если она равна False, то выход.
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;
repeat
i := i + 1;
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 }
i := 0;
i
i := i + 1;

Метод выбора
Идея:
найти минимальный элемент и поставить на первое место (поменять местами с A[1])
из оставшихся найти минимальный элемент и поставить на второе место (поменять местами с A[2]), и т.д.

Метод выбора
for i := 1 to N-1 do begin
nMin:= i ; for j:= i+1 to N do
if A[j] < A[nMin] then nMin:=j;
if nMin <> i then begin
c:=A[i];
A[i]:=A[nMin];
A[nMin]:=c;
end;
end;
N-1
N
нужно N-1 проходов
поиск минимального от A[i] до A[N]
если нужно, переставляем
i+1
i

Эффективные методы
сортировки

«Быстрая сортировка» (Quick Sort)
Идея – более эффективно переставлять элементы, расположенные дальше друг от друга.
N div 2
2 шаг: переставить элементы так:
при сортировке элементы не покидают « свою область»!
1 шаг: выбрать некоторый элемент массива X
3 шаг: так же отсортировать две получившиеся области
Разделяй и властвуй (англ. divide and conquer)

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

«Быстрая сортировка» (Quick Sort)

«Быстрая сортировка» (Quick Sort)
procedure QSort ( first, last: integer);
var L, R, c, X: integer;
begin
if first < last then begin
X:= A[(first + last) div 2];
L:= first; R:= last;
QSort(first, R); QSort(L, last);
end;
end.
ограничение рекурсии
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;
разделение
обмен
двигаемся дальше
сортируем две части

«Быстрая сортировка» (Quick Sort)
program qq;
const N = 10;
var A: array[1..N] of integer;
begin { заполнить массив }
{ вывести исходный массив на экран }
Qsort ( 1, N ); { сортировка }
{ вывести результат }
end.
procedure QSort ( first, last: integer);
...