Объявление и инициализация матрицы

Объявление и инициализация матрицы аналогичны описанным выше способам работы с векторами. То есть в разделе VAR переменным отводится место, а начальное значение этих величин специально не устанавливается. Поэтому после объявления массива необходимо его элементам задать необходимые значения. Используется три способа инициализации двумерного массива.

• Если значения элементов массива определены до начала работы программы, то есть известны на этапе формулировки задания на программирование, то можно использовать следующий способ:

CONST
A: ARRAY [1..5, 1..2] OF REAL = ((0.1, -15.3), (7, 0), (-11.89,4), (-78,11.2), (1,0.01));
При таком объявлении массива в разделе констант, вы заносите в двумерный массив А по порядку А[1,1] = 0.1, А[1,2] = -15.3, А[2, 1] = 7, А[2, 2] = 0,... А[5, 2] - 0.01 вещественные числа, перечисленные в круглых скобках. При этом массив является массивом переменных, то есть в процессе работы программы можно менять содержимое любого элемента матрицы.

• Второй способ применяется в том случае, если исходные данные необходимо внести с клавиатуры в процессе выполнения программы. Так как матрица представляет собой конечный набор однотипных элементов, пронумерованных с помощью двух индексов I и J, то удобно использовать вложенный арифметический цикл (операторы FOR) для ввода значений непосредственно с клавиатуры. При этом можно предложить два приема. Предположим, в вашей программе сделаны объявления:

CONST
M = 3;
N = 4;
VAR
A: ARRAY[ 1.. М, 1.. N] OF REAL;
где M — количество строк, а N — количество столбцов в матрице. Первый способ ввода будет иметь инструкцию:
WRITELN('Введите массив А, из 12 вещественных чисел');
FOR I := 1 ТО М
DO FOR J:= 1 TO N
DO READ(A[I,J]);
При таком способе оператор может ввести все 12 чисел в форме матрицы.
Через пробел в одну строку вводится четыре числа первой строки и затем нажимается на клавишу Enter. Вторая и третья строки матрицы А вводятся аналогично. На экране монитора остается изображение матрицы в удобочитаемом виде, близком к оригиналу.
Второй способ ввода имеет вид:
FOR I := 1 ТО М
DO FOR J:=l TO N
DO BEGIN
WRITE('A[', I:1, J:1 ']= ');
READLN(A[I, J])
END;
Этот фрагмент программы позволяет вам вводить число непосредственно за подсказкой компьютера, курсор для ввода стоит через пробел за знаком равенства.

• Третий способ заполнения заключается в прямом присвоении в теле программы значений элементам массива. Например, следующие операторы вложенного арифметического цикла в совокупности с оператором присваивания обеспечивают обнуление всех 12 компонентов массива:

FOR I := 1 ТО М
DO FOR J:=l TO N
DO A[I,J]:=0;

Понятие сортировки. Алгоритмы сортировки.

Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

каждый алгоритм сортировки состоит из трех основных частей:

• Функция сравнения пары элементов сортируемого массива
• Процедура перестановки, меняющая местами пару элементов
• Сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены.

#define less(x,y) (x < y) // функция сравнения элементов#define swap(x,y) {int t=x; x=y; y=t;} // процедура перестановки элементов

Пузырьковая сортировка

Операция сравнения/перестановки выполняется для каждых двух стоящих рядом элементов. После первого прохода по массиву "вверху" оказывается самый "легкий" элемент. Следующий цикл сортировки выполняется начиная со второго элемента, в результате чего вторым в массиве оказывается второй наименьший по величине элемент, и так далее.
Алгоритм прост и крайне неэффективен.

void sort_bubble(int a[], int max) // пузырьковая сортировка { for (int i=0; i<max; i++) for (int j=max-1; j>i; j--) if (less(a[j], a[j-1])) swap(a[j], a[j-1]); }

Сортировка выбором

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

void sort_choose(int a[], int max) // сортировка выбором { for (int i=0; i<max; i++) { int k=i; for (int j=i+1; j<max; j++) if (less(a[j], a[k])) k=j; if (i!=k) swap(a[i], a[k]); } }

Сортировка Шелла

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

void sort_shell(int a[], int max) // сортировка Шелла { for (int gap = max/2; gap>0; gap/=2) // выбор интервала for (int i=gap; i<max; i++) // проход массива// сравнение пар, отстоящих на gap друг от друга for (int j=i-gap; j>=0 && less(a[j+gap],a[j]); j-=gap) swap(a[j], a[j+gap]); }

Сортировка Хоора

Суть метода заключается в том, чтобы найти такой элемент множества, подлежащего сортировке, который разобьет его на два подмножества: те элементы, что меньше делящего элемента, и те, что не меньше его.

Для массива из 10 чисел установим два индекса: на первый (i) и на последний (j) элементы.

10 7 28 49 31 25 17 3 14 43 i <--j step==-1

На каждом шаге будем изменять значение индекса j на значение step (вначале оно равно -1, индекс уменьшается), т.е. двигать j влево. Мы будем делать так в том случае, если j-й элемент больше, чем i-й элемент. Если это условие не выполнено - поменяем местами i-й и j-й элементы массива и сами индексы i и j, а также изменим знак у значения step -- оно станет равным +1:

3 7 28 49 31 25 17 10 14 43 j--> i step==+1

Продолжим процесс: теперь j движется вправо, и изменится условие - сейчас для продолжения процесса необходимо, чтобы j-й элемент был меньше i-го.

Будем продолжать вышеописанный процесс до тех пор, пока индексы i и j не станут одинаковыми.

В этот момент можно утверждать, что i-й (он же и j-й) элемент разделил исходное множество на два подмножества: все элементы, находящиеся слева от делящего элемента, меньше его, и все элементы, находящиеся справа, не меньше делящего (i-го) элемента. Получилось, что i-й элемент стоит на своем месте:

3 7 10 49 31 25 17 28 14 43 ij

Таким образом, мы описали процедуру нахождения расположения одного элемента. Иными словами, мы "отсортировали" один элемент множества. Такая же процедура применима к элементам "левого" и "правого" подмножеств, которые на данный момент еще не отсортированы.

Условие завершения нашей рекурсивной процедуры - совпадение границ, которое эквивалентно тому, что в множестве остался один элемент.

void sort_hoor(int a[], int l, int r) // сортировка Хоора { int i=l, j=r, step=-1, condition=1; if (l>=r) return; // сортировать нечего do { // сортируем с левой границы до правой if (condition == less(a[j],a[i])) { swap(a[i], a[j]); // перестановка чисел swap(i, j); // обмен местами индексов step = -step; // теперь - в другую сторону condition = !condition; // обмен условия на противоположное } j += step; // передвинем индекс } while (j!=i); // пока индексы не сойдутся sort_hoor(a, l, i-1); // левое подмножество sort_hoor(a, i+1, r); // правое }

QuickSort

По существу является разновидностью сортировки Хоора, но программная реализация немного красивее и быстрее.

Основное отличие - за делящий элемент всегда выбирается середина массива.

void sort_quick(int a[], int l, int r) // QuickSort { int i=l, j=r, x=a[(l+r)/2]; do { while (less(a[i],x)) i++; while (less(x,a[j])) j--; if (i<=j) { swap(a[i], a[j]); i++; j--; }; } while (i<j); if (l<j) sort_quick(a,l,j); if (i<r) sort_quick(a,i,r); }