1) Циклический сдвиг на 1 позицию влево

1) Циклический сдвиг на 1 позицию влево

t: =a[1]

for j: =1 to N-1 do

a[j]: = a[j+1];

a[N]: =t;

2) Циклический сдвиг на 1 позицию вправо

t: =a[N]

for j: =N downto 2 do

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

a[1]: =t;

3) Переворот массива

for j: =1 to (N div 2) do

begin

t: =a[j];

a[j]: =a[N-j+1];

a[N-j+1]: =t;

end;

только для массивов, описанных

var a: =array[1.. N] of integer

4) Разбрасывание элементов массива на 2 непересекающиеся части

Цель:

good

Not good

Порядок элементов внутри множества не важен

Пример: Четные/Нечётные числа

Заведём 2 счётчика: b(begin), e(end)

b идёт вправо

good – идёт дальше, not good – останавливается

e идёт влево

not good – идёт дальше, good – останавливается

Если мы не в конечной позиции, то swap(a[b] и a[e]);

inc – увеличение на 1, dec - уменьшение на 1

b e

1 4675283 4 9

b e

446 7 52 8 319

4468 52 7319

4468 25 7319

b: =1; e: =N;

while(b < =e) do

if a[b] mod 2 = 0 then inc(b)

else if a[e] mod 2 < > 0 then dec(e)

else begin

t: =a[b];

a[b]: =a[e];

a[e]: =t;

end;

Замечание:

Алгорим работает, даже если одно из множеств пустое

222446 8

3 795111

5) Сортировка методом выбора максимального

В несортированной части массива брать максимальный элемент и менять его местами с посл элементом в неотсортированной части

for i: =N downto 2 do begin

max: =1;

for j: =2 to 1 do

if a[j]> a[max] then max: =j;

t: =a[i];

a[i]: = a[max];

a[max]: =t;

end;

Алгоритм сортировки называется устойчивым, если он не меняет в массиве порядок равных элементов относительно друг друга. Данный алгоритм не является устойчивым.

6) Сортировка методом пузырька

for i: =N downto 2 do begin

k: =0;

for j: =1 to i-1 do

if a[j] > a[j+1] then begin

t: =a[j];

a[j]: =a[j+1];

a[j+1]: =t;

inc(k);

end;

if k=0 then break

end;

Пузырёк является устойчивым алгоритмом.

7) Алгоритм бинарного поиска

Есть ли в массиве элемент Х?

Применяется только к отсортированному массиву

В бинарном поиске тыкаем в середину области поиска

Простая реализация:

L: =1; R: =N;

while(L< =R) do begin

m: =(L+R) div 2

if a[m] = x then break

else if a[m] > x then

R: =m-1

else L: =m+1

end;

if L< =R then writeln(m)

else writeln(‘NO’)

Недостаток: из нескольких равных x элементов находит случайный

Профессиональная реализация:

Найти границу между 2 множествами

Правый бин-поиск ищет границу между множествами < =x и > x

Левый бин-поиск ищет границу между множествами < x и => x

Правый бин-поиск

Найти границу – поставить указатели L и R в соседние элементы, чтоб граница была между ними

L: =

R: =

while (R-L> 1) do begin

m: =(L+R) div 2;

if a[m]> x

then R: =m

else L: =m

end;

Если в задаче надо найти элемент:

if (a[L]=x)

Барьеры:

1) правый (R=N+1)

2) левый (R=0)