Краткие теоретические сведения

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

Обменная поразрядная сортировка (сортировка “пузырьком”).

Для вектора из n элементов делается (n-1) просмотр, в каждом просмотре сравниваются попарно элементы, начиная с первого, если предыдущий элемент больше последующего, их меняют местами. После каждого просмотра очередной наибольший элемент встает на свое место (сортировка по возрастанию).

Последовательно просматриваем числа a₁,...,a_n находим наименьшее i такое, что a _i > a_i+1. Поменять a_i и a_i+1 местами, возобновить просмотр с элемента a_i+1 и т.д. Тем самым наибольшее число передвинется на последнее место. Следующие просмотры начинать опять сначала, уменьшая на единицу количество просматриваемых элементов. Массив будет упорядочен после просмотра в котором участвовали только первый и второй элементы.

Сортировка посредством выбора.

Находится минимальный элемент массива и меняется местами с первым. Среди оставшихся элементов ( то есть начиная со второго) опять находится минимальный и меняется местами со вторым и процесс повторяется.

Допустим, что элементы a₁,...,a_i-1 уже упорядочены, тогда среди оставшихся (a_i,...,a_n) находим минимальный элемент и меняем его местами с i-тым элементом. И т.д. пока массив не будет полностью упорядочен.

Метод простых вставок

Последовательно просматриваем a₂,...,a_n и каждый новый элемент a_i вставляем на подходящее место в уже упорядоченную совокупность a₁,...,a_i-1. Это место определяется последовательным сравнением a_i с упорядоченными элементами a₁,...,a_i-1.

Метод бинарных вставок

Этот алгоритм представляет из себя оптимизированную версию предыдущего, отличие заключается в том, что при поиске место, на которое надо вставить элемент a_i в уже упорядоченную совокупность a₁,...,a_i-1, определяется алгоритмом деления пополам (отсюда и название алгоритма "бинарные вставки" здесь понимаем как "вставка делением пополам").

Метод шелла, метод Уильяма Флойда, бинарных деревьев,…

Схема сортировки согласно алгоритму 1 (блок-схема)

MAS(исходный)

4	5	8	9	3	2	4	1	6	7
MAS[1]	MAS[2]	MAS[3]	MAS[4]	MAS[5]	MAS[6]	MAS[7]	MAS[8]	MAS[9]	MAS[10]

Через нахождение минимального среди первых n элементов….

1 итерация

Просматриваем элементы с первого по десятый, находим минимальный элемент и его порядковый номер в массиве, заменяем найденным элементом первый

4	5	8	9	3	2	4	1	6	7
MAS[1]	MAS[2]	MAS[3]	MAS[4]	MAS[5]	MAS[6]	MAS[7]	MAS[8]	MAS[9]	MAS[10]

Меняются местами первый элемент с восьмым

4	5	8	9	3	2	4	1	6	7
MAS[1]	MAS[2]	MAS[3]	MAS[4]	MAS[5]	MAS[6]	MAS[7]	MAS[8]	MAS[9]	MAS[10]

Массив после 1 итерации

1	5	8	9	3	2	4	4	6	7
MAS[1]	MAS[2]	MAS[3]	MAS[4]	MAS[5]	MAS[6]	MAS[7]	MAS[8]	MAS[9]	MAS[10]

2 итерация

Во 2 итерации рассматриваются элементы со второго по десятый, находим минимальный элемент и его порядковый номер в массиве, заменяем найденным элементом второй

1	5	8	9	3	2	4	4	6	7
MAS[1]	MAS[2]	MAS[3]	MAS[4]	MAS[5]	MAS[6]	MAS[7]	MAS[8]	MAS[9]	MAS[10]

Меняются местами второй элемент с шестым

1	5	8	9	3	2	4	4	6	7
MAS[1]	MAS[2]	MAS[3]	MAS[4]	MAS[5]	MAS[6]	MAS[7]	MAS[8]	MAS[9]	MAS[10]

Массив после 2 итерации

1	2	8	9	3	5	4	4	6	7
MAS[1]	MAS[2]	MAS[3]	MAS[4]	MAS[5]	MAS[6]	MAS[7]	MAS[8]	MAS[9]	MAS[10]

……………………………………………………………

Массив после 9 итерации

1	2	3	4	4	5	6	7	8	9
MAS[1]	MAS[2]	MAS[3]	MAS[4]	MAS[5]	MAS[6]	MAS[7]	MAS[8]	MAS[9]	MAS[10]

Далее представлены образцы блок-схем сортировки первой строки двумерного массива.

Л абораторная работа №3(2 часа)

Тема: Составление и запись алгоритмов для вычисление суммы элементов одномерного массива, нахождение минимального элемента в виде программы. Компиляция и тестирование программы.

Цель: Приобрести навыки составления и анализа алгоритмов заполнения и обработки элементов массивов, нахождение минимального элемента в виде программы, представления их в программы, проведение компиляции и тестирования программы.

Задание: Разработать алгоритм решения задачи представить его в виде программы на языке программирования Turbo Pascal. Провести компиляцию и тестирование программы.

Массив целых чисел размерностью 1×20 заполнить случайным образом. Вывести на экран максимальный и минимальный элементы, места их расположения, разность их значений, подсчитать количество и сумму элементов, больших 10 и меньших 40, а также среднее значение этих элементов, вывести полученные результаты.