3. Алгоритмы сортировки

Из решения предыдущей зада­чи вытекает, что чрезвычайно важно иметь хорошие алго­ритмы упорядочения элементов последовательности. В программировании для задач упорядочения обычно используют термин сортировка. Описанный выше алгоритм сортировки (см. задачу 3) не является оптимальным. Известны алгорит­мы сортировки со сложностью в худшем случае порядка и n*log n. К ним относится обменная сортировка с разделени­ем, которая заключается в следующем:

1.         в исходном неотсортированном массиве выбрать некоторый элемент x = a[i];

2.         переставить элементы массива таким образом, чтобы слева от х оказались элементы массива, меньшие или равные х, а справа — элементы массива, большие х. Пусть при этом элемент х попадает в позицию с номером k, тогда массив будет иметь вид

( a[1], а[2],...,a[k-1], a[k], a[k+1],…,a[n] ).

Каждый из элементов а[1], а[2],..., a[k-1] меньше либо равен a[k], каждый из элементов а[k+1],..., а[n] больше a[k]. Отсюда можно сделать вывод, что элемент a[k] стоит на своем месте. А исходный массив при этом разделился на две неотсортированные части, барьером между которыми является элемент a[k],

3) далее необходимо применить шаги 1 и 2 для каждой из двух неотсортированных частей. И так до тех пор, пока не останутся подмассивы, состоящие из одного элемента, т. е. пока

не будет отсортирован весь массив.

Выбор алгоритма сортировки зависит от структуры обра­батываемых данных. Поэтому соответствующие методы бы­ли разбиты на два класса: сортировка массивов (таблиц) и сортировка файлов (последовательностей). Иногда эти мето­ды называют внутренней и внешней сортировкой, поскольку массивы • хранятся во внутренней, оперативной, памяти ма­шины, а файлы — в более медленной внешней памяти. Если данные «выстроены» в виде массива, то доступ имеется ко всем его элементам. Если же данные образуют файл, то дос­туп имеется только к одной величине из множества элемен­тов, записанных в файл.

Основное условие для сортировки массивов заключается в следующем: выбранный метод сортировки должен обеспе­чивать экономное расходование доступной памяти. Это оз­начает, что перестановки, приводящие элементы в порядок, должны выполняться «на том же месте», т. е. методы, в ко­торых элементы из массива А передаются в результирующий массив В, представляют существенно меньший интерес.

Сортировать элементы можно по неубыванию (a₁<=a₂<=...<=a_n) и по невозрастанию (a_t>=a₂>=a_n). Методы сортировки «на том же месте» можно разбить на три основные категории.

1.Сортировки с помощью выбора

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

2.Сортировки с помощью включения

Алгоритм метода со­стоит в следующем: последовательно просматривают элементы a_1,a_2,...,a_n и каждый новый элемент a_i вставляют на подходящее место в уже упорядоченную совокупность a_i-1. Это место определяется последовательным сравнением a_i с упорядоченными элементами a₁ …, a_i-1.

3.Сортировки с помощью обменов

Алгоритм метода та­ков: последовательным просмотром элементов a_1,a_2,...,a_n находят наименьшее i такое, что a_i>a_i+1. Затем меняют a_i и

a_i+1 местами и возобновляют просмотр с a_i+1 элемента и т.д.

Тем самым наибольшее число передвинется на последнее место. Следующие просмотры опять начинают с начала по­следовательности, уменьшая количество просматриваемых элементов на 1. Массив будет упорядочен после просмотра, в котором участвовали только первый и второй элементы.

Три перечисленных метода часто называют прямыми. В них требуется порядка n*n сравнений.

Задание для самостоятельной работы 

1.         Записать алгоритм поиска максимального элемента и его номера в таблице чисел A [1: n].

2.         Записать алгоритмы сортировки в таблице чисел A [1: n]: а) методом выбора;

б) методом включений;

в) методом обменов.

3.         Записать алгоритм подсчета в таблице чисел A[i: n] наибольшего количества расположенных последова­тельно положительных элементов.

4.         Записать алгоритм, проверяющий, является ли последовательность чисел A [1: n] перестановкой чисел 1, 2, ..., n.

5.         Дана упорядоченная таблица чисел A [1: n], которая может содержать элементы с одинаковыми значениями. Записать алгоритм, для выяснения того, имеется ли в таблице заданное число К. Если такое число имеется, то найти количество элементов таблицы, равных ему.

6.         Дана прямоугольная таблица чисел A[1: n, 1: m]. Со­ставить алгоритм, который определял бы номера строк таб­лицы, начинающихся с одинаковых чисел, и подсчитывал бы сумму элементов в этих строках.

7.         Дана прямоугольная таблица чисел A[1: n, 1: m]. Вы­яснить, есть ли в этой таблице строки, все элементы кото­рых совпадают.