a[0]:=x; j:=i-1;

while x<a[j] do begin

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

end;

a[j+1]:=x

end

end;

Быстрая сортировка

Быстрая сортировка основана на том факте, что для достижения наибольшей эффективности желательно производить обмен на больших расстояниях.

Рассмотрим следующий алгоритм:

1.Выберем средний элемент в массиве, назовем его x.

2.Просмотрим массив начиная с первого элемента, двигаясь слева направо, пока не найдем элемент a[i] > x.

3.Затем просмотрим массив начиная с последнего элемента, двигаясь справа налево, пока не найдем элемент a[i] < x.

4.Поменяем местами эти два элемента и продолжим процесс просмотра c обменом, пока два просмотра не встретятся где-то в середине массива. В результате массив разделится на две части: левая –

сключами, меньшими или равными x, и правая – с ключами, большими или равными x.

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

Алгоритм, сортирующий N элементов, включает обращение к самому себе (для меньшего числа элементов). Такой способ описания алгоритма называется рекурсией.

Рекурсивный вариант «процедуры быстрой сортировки»:

62

Procedure quicksort(мar a : vector; n : шnteger Procedure sort(l,r : Integer)

var x,w : real; i,j : integer;

begin i:=l; j:=r;

x:=a[(l+r)div(2)]; repeat

while a[i]<x do i:=i+1 while x<a[j] do j:=j-1; if i<=j then

begin w:=a[i];

a[i]:=a[j];

a[j]:=w;

i:=i+1; j:=j-1

end;

until i>j;

if l<j then sort(l,j); if i<r then sort(i,r); end;

begin { тело процедуры qiucksort } sort(1,n)

end;

Пример. Дана квадратная матрица N x N, состоящая их натуральных чисел. Повернуть ее на 90 градусов по часовой стрелке и вывести результат на экран.

Основная задача, которую нужно при этом решить, состоит в определении преобразования индексов элементов матрицы. Рассмотрим вначале матрицу 3х3 и посмотрим, что происходит с элементами при повороте.

63

Если считать, что после поворота у нас появилась новая матрица B, то соответствие между элементами устанавливается следующим

Для элементов матрицы		N x N справедлива следующая система
уравнений:		I = M
образом:
B11	<–> A31
B12	<–> A21
B21	<–> A32
B22	<–> A22 и т.д., т.е. B[I,J] <–> A[L,M].

J + L = N +1.

Отсюда правило преобразования элементов выглядит следующим образом:

B[I,J] = A[N+1-J,I].

Программа, решающая данную задачу, выглядит так:

Program PRG; const n1=100;

var a,b : array[1..n1,1..n1] of integer; k,n,i,j : integer;

begin

write(‘Введите размер матрицы N = ’); readln(n);

writeln(‘Исходная матрица’); k:=1;

for i:=1 to n do

for j:=1 to n do begin

a[i,j]:=k;

64

k:=k+1;

if j<n then write(a[i,j]:4) else writeln(a[i,j]:4)

end;

writeln(‘Матрица после поворота на 90 градусов’); for i:=1 to n do

for j:=1 to n do begin

b[i,j]:=a[n+1-j,i];

if j<n then write(b[i,j]:4) else writeln(b[i,j]:4)

end;

end.

Задание 7.

1.Задан массив A. Записать в массив B номера элементов массива A, удовлетворяющих условию 0≤A[i] ≤1.

2.Для каждой строки целочисленной матрицы найти число элементов, кратных пяти, и наибольший из таких элементов.

3.Две строки матрицы называются похожими, если совпадают множества чисел, встречающихся в этих строках. Определить количество похожих строк в заданной матрице.

4.Вычислить сумму и число положительных элементов матрицы, находящихся на главной диагонали.

5.Составить программу для транспонирования квадратной матрицы A[1..5,1..5] без использования дополнительных массивов.

6.Дан массив чисел. Расставить их по убыванию.

7.Отсортировать элементы массива, стоящие на четных местах, по убыванию с помощью простого выбора.

8.Отсортировать с помощью простого выбора элементы массива, стоящие на нечетных местах.

65

9.Дана матрица N x N, состоящая из натуральных чисел. Расставить строки таким образом, чтобы элементы в первом столбце были упорядочены по убыванию.

10.Дана квадратная матрица N x N, состоящая из натуральных чисел. Повернуть ее на 90 градусов против часовой стрелки и вывести результат на экран.

11.Дана квадратная матрица N x N, состоящая из натуральных чисел. Повернуть ее на 180 градусов и вывести результат на экран.

12.Дана квадратная матрица N x N, состоящая из натуральных чисел. Зеркально отразить ее элементы относительно горизонтальной оси симметрии. Вывести результат на экран.

13.Дана квадратная матрица N x N, состоящая из натуральных чисел. Зеркально отразить ее элементы относительно вертикальной оси симметрии. Вывести результат на экран.

14.Дана квадратная матрица N x N, состоящая из натуральных чисел. Зеркально отразить ее элементы относительно главной диагонали. Вывести результат на экран.

15.Дана квадратная матрица N x N, состоящая из натуральных чисел. Зеркально отразить ее элементы относительно побочной диагонали. Вывести результат на экран.

16.Написать программу, которая методом обмена («пузырька») сортирует по убыванию введенный с клавиатуры одномерный массив.

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

18.Написать программу, которая вводит с клавиатуры двумерный массив по строкам и вычисляет среднее арифметическое его элементов.

19.Написать программу, которая вводит по строкам с клавиатуры двумерный массив и вычисляет сумму его элементов по столбцам.

20.Дан неупорядоченный массив из n натуральных чисел от 1 до n. Вычислить минимальное число перестановок, необходимых для упорядочения массива по возрастанию.

66

21. Дана квадратная матрица A размерности N x N. Построить программу, вычисляющую определитель матрицы по формуле:

N

(− 1)α

A

=

∑

a

i j

a

i

j

...a

i

j

i

,i ,...,i

N

, j , j

2

,..., j

N

=1

1

2

1

1 1

2

2

N

N

i1

≠i2

≠i3...≠iN

j1≠ j2 ≠ j3...≠ jN

Здесь α – число инверсий в последовательности вторых индексов соответствующих произведений при условии, что первые расположены в порядке их возрастания.

22. Дана квадратная матрица A размерности N x N. Составить матрицу В путем удаления из матрицы A i-й строки и j-го столбца. i и j - произвольные целые числа от 1 до N.

			23. Дана	квадратная	матрица A размерности	N x N. Построить
программу, вычисляющую определитель матрицы						по формуле:
			N
	A		= ∑a1 j A1 j	, где A1 j –	алгебраическое дополнение элемента a1 j .
			j=1

67