Последовательная сортировка одномерных массивов

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

Сортировка представляет собой процесс упорядочения элементов в массиве в порядке возрастания или убывания их значений.

Основная идея последовательной сортировки заключается в следующем. Вначале выбирается минимальный элемент из всего массива, найденный элемент перемещается в начало массива (в позицию с индексом, равным 1). Затем снова проводится поиск минимального элемента, но поиск начинается с позиции с индексом 2, так что элемент с индексом 1 при поиске не учитывается. Таким образом, будет найден второй по величине элемент массива. Затем это элемент перемещается в позицию с индексом 2. Теперь необработанная часть массива, в которой будет произведён поиск минимального значения, начинается с элемента с индексом 3. Эта последовательность операций выполняется до тех пор, пока в необработанной части массива не останется один элемент.

Рассмотрим алгоритм, представленный на рисунке 20.

Переменная k служит для указания вершины необработанной части массива, т.е. места, куда нужно поместить очередной минимальный элемент из этой необработанной части. В начале работы k = 1, следовательно, поиск минимального элемента будет проходить по всему массиву.

Тело основного цикла (блоки 5, 6, 7, 8) содержит алгоритм поиска минимального элемента. Его отличает от алгоритма, представленного на рисунке 19, следующее: осуществляется поиск не максимального, а минимального элемента (поскольку сортировка производится по возрастанию элементов), поиск осуществляется не по всему массиву, а только в его части (элементы с индексами от k+1 до n), помимо самого минимального значения выясняется и его положение в массиве (переменная Nmin). Далее в блоке 9 происходит перестановка элементов массива, так что найденный минимальный элемент оказывается на вершине необработанной части массива, под индексом k.

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

Так повторяется до тех пор, пока в необработанной части массива не остаётся один элемент.

Рисунок 20 – Блок-схема алгоритма
последовательной сортировки

Приведём трассировку части представленного алгоритма (таблица 11). Вложенный цикл (блоки 6, 7, 8) предназначен для нахождения минимального элемента массива, среди элементов с индексами от k+1 до n. Это алгоритм рассматривался ранее, поэтому в трассировке блоки 6, 7, 8 будут отображены одной строкой, элемент, находящийся на вершине необработанной части массива А, помечен серой заливкой ячейки.

Таблица 11 – Трассировка алгоритма последовательной сортировки
одномерного массива

№ блока	k	A[k]	Nmin	min	A[Nmin]	A
...
			-	-	-
6,7,8						22
			-	-	-
6,7,8							33
			-	-	-
6,7,8
			-	-	-
6,7,8									55
...

Реализация алгоритма в программу выглядит следующим образом: