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

ЛАБОРАТОРНАЯ РАБОТА № 7

СОСТАВЛЕНИЕ ПРОГРАММ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ СОРТИРОВКИ.

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

Требования к выполнению работы: Для всех заданий вначале составить блок-схему алгоритма, а затем программу. Элементы массивов получать с помощью генератора случайных чисел. Вывести на печать массивы до, и после преобразования.

Теоретические положения

Рассмотрим массив целых или действительных чисел a₁,…,a_n. Пусть требуется переставить элементы этого массива так, чтобы после перестановки они были упорядочены по убыванию или возрастанию. Эта задача называется задачей сортировки. Для решения этой задачи можно воспользоваться следующими алгоритмами.

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

Найти элемент массива, имеющий наименьшее значение, переставить его с первым элементом, затем проделать то же самое, начав со второго элемента и т.д.

Сортировка обменами.

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

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

Просматривать последовательность а₁,…,а_n и каждый новый элемент а_i вставлять на свое место в уже упорядоченную совокупность а_1,…,а_i_-₁. Это место определяется последовательным сравнением а_i с упорядоченными элементами а₁,…,а_i_-1.

Сортировка бинарными вставками.

Алгоритм упорядочения простыми вставками можно изменить следующим образом. Место, на которое надо вставить а_i в уже упорядоченную совокупность а₁,…,а_i_-1 определяется алгоритмом деления отрезка пополам. Новый алгоритм сортировки называется алгоритмом сортировки бинарными вставками (слова “бинарная вставка” следует понимать как “вставка делением пополам”).

12 3 4 5 Следующая ⇒