3. Контрольные вопросы

1. Что такое массив?

2. Одномерные и двумерные массивы.

3. Статические и динамические массивы.

4. Описание статических массивов.

5. Описание динамических массивов.

6. Функция Rnd.

7. Что такое матрица?

8. Расскажите об основных видах матриц.

9. Блок-схема формирования единичной матрицы.

10. Блок-схема формирования симметричной матрицы

11. Блок-схема транспонирования матрицы.

12. Блок-схема умножения матрицы А(m  n) на матрицу В(n  l).

Лабораторная работа № 7 Сортировка массивов

1. ЦЕЛЬ РАБОТЫ

Целью работы является изучение методов сортировки и получение практических навыков сортировки массивов.

2. ТЕОРЕТИЧЕСКИЕ ПОЛОЖЕНИЯ

Основные положения

В общем случае сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке.

Цель сортировки – облегчить последующий поиск элементов в таком отсортированном множестве.

Мы встречаемся с отсортированными объектами в телефонных книгах, в оглавлениях книг, в библиотеках, в словарях, на складах – почти везде, где нужно искать хранимые объекты. Даже малышей учат держать свои вещи "в порядке", и они уже сталкиваются с некоторыми видами сортировки задолго до того, как ознакомятся с азами арифметики.

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

Введем некоторые обозначения и понятия.

Если у нас есть элементы A₁, A₂,…, A_N, то сортировка есть перестановка этих элементов так, чтобы при некоторой упорядочивающей функции F выполнялись отношения: F(A_K1) ≤ F(A_K2) … ≤ F(A_KN). Если сортировка происходит по убыванию, то знак отношения меняется на противоположный "≥". При решении практических задач упорядочивание массива, как правило, сопровождается некоторыми дополнительными действиями. Например, если A₁,Y₁; A₂,Y₂;…; A_N,Y_N – это значения аргумента A и некоторой функции Y = f(A), то перестановка этих аргументов должна сопровождаться одновременной перестановкой и значений функции.

Рассмотрим методы сортировки.

Сортировка методом прямого включения

Такой метод широко используется при игре в карты. Элементы (карты) мысленно делятся на уже "готовую" последовательность A₁, A₂,…, A_i-1, и "оставшуюся" (не сортированную) часть: A_i, A_i+1,…, A_N.

Суть метода заключается в том, что при каждом i-ом шаге (начиная с i = 2), из неотсортированной части извлекается i-ый элемент и помещается в "готовую" часть, при этом он вставляется на нужное место.

Текстовый алгоритм метода:

1. Начало.

2. Выполнить цикл, пока i имеет значения от 2 до N, шаг = 1:

а) i-ый элемент (A(i)) поместить в ячейку A(0);

б) присвоить j = -1, то есть j равно номеру элемента, находящегося слева от испытуемого (i-го) и таким образом стоящего в "готовой" последовательности;

в) если А(0) ≥ А(j), то элемент А(0) поместить в ячейку А(j+1), иначе элемент А(j) поместить в ячейку А(j+1), уменьшить значение j на единицу и вновь выполнить пункт в).

3. Конец.

На рис. 1 представлена блок-схема сортировки методом прямого включения.

Метод работает следующим образом: на i-ом шаге (начиная с i = 2) i-ый элемент помещается в свободную ячейку (например, А(0)). Этот элемент сравнивается со стоящим в "готовой" части слева от него элементом. Если элемент А(0) меньше, то происходит сдвиг вправо сравниваемого (j-го элемента) на одну позицию, после чего для сравнения берется следующий элемент. Если же элемент А(0) при сравнении оказывается не меньше, то он помещается на место, стоящее сразу за сравниваемым элементом.

Рис. 1. Блок-схема сортировки методом прямого включения

На рис. 2 приведен пример выполнения сортировки методом прямого включения.

Исходная последовательность		44	55	12	42	94	18	06	67
	А (0)
I = 2		44	55	12	42	94	18	06	67
I = 3		44	55	12	42	94	18	06	67
I = 4		12	44	55	42	94	18	06	67
I = 5		12	42	44	55	94	18	06	67
I = 6		12	42	44	55	94	18	06	67
I = 7		12	18	42	44	55	94	06	67
I = 8		06	12	18	42	44	55	94	67
Результат		06	12	18	42	44	55	67	94

Рис. 2. Пример сортировки методом прямого включения

Сортировка прямым включением больше подходит для случая, когда сортируемые данные поступают последовательно (одно за другим).