Алгоритмы сортировки одномерных массивов

Под сортировкой понимают процесс перестановки объектов данного массива в определенном порядке. Целью сортировки является упорядочение массивов для облегчения последующего поиска элементов в данном массиве. Рассмотрим основные алгоритмы сортировки по возрастанию числовых значений элементов массивов. Существует много методов сортировки массивов. В этой работе будут рассмотрены алгоритмы двух методов: модифицированного метода простого выбора и метода парных перестановок.

Сортировка модифицированным методом простого выбора

Этот метод основывается на алгоритме поиска минимального элемента. В массиве А(1..n) отыскивается минимальный элемент, который ставится на первое место. Для того, чтобы не потерять элемент, стоящий на первом месте, этот элемент устанавливается на место минимального. Затем в усеченной последовательности, исключая первый элемент, отыскивается минимальный элемент и ставится на второе место и так далее n–1 раз, пока не встанет на свое место предпоследний

n–1 элемент массива А, сдвинув максимальный элемент в самый конец.

Рассмотрим алгоритмическое решение задачи на примере сортировки некоторого массива значений по возрастанию. В соответствии с вышеописанным методом необходимо несколько раз выполнить операции поиска минимального элемента и его перестановку с другим элементом, то есть потребуется несколько раз просматривать элементы массива с этой целью. Количество просмотров элементов массива, согласно описанию модифицированного метода простого выбора, равно n–1, где n – количество элементов массива. Таким образом, можно сделать вывод, что проектируемый алгоритм сортировки будет содержать цикл, в

котором будет выполняться поиск минимального элемента и его перестановка с другим элементом.

Обозначим через i счетчик (номер) просмотров элементов массива и изобразим обобщенный алгоритм сортировки на рис. 19. Отметим, что для перестановки элементов местами необходимо знать их порядковые номера. Алгоритмы ввода исходного массива изображен на рис. 16. Алгоритм поиска в массиве минималь-ного элемента и его номера будет аналогичен алгоритму примера 10, который

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

сортировки данным методом с акцентом на поиск минимального элемента на конкретном примере. Пусть исходный массив содержит 5 элементов (2, 8, 1, 3, 7). Количество просмотров, согласно модифицированному методу простого выбора, будет равно 4. Покажем в таблице 4, как будет изменяться исходный массив на каждом просмотре.

Из данных, приведенных в таблице 4, следует, что поиск минимального значения в массиве на каждом просмотре осуществляется в сокращенном массиве, который сначала начинается с первого элемента, а на последнем просмотре массив, в котором ищется минимальный элемент, начинается уже с четвертого (или n–1) элемента. При этом можно заметить, что номер первого элемента массива для каждого поиска и перестановки совпадает с номером просмотра i.

Введем следующие обозначения:

К – номер минимального элемента,

J – номер элемента массива,

М и А(К) – одно и тоже значение минимального элемента массива,

i – номер переставляемого с минимальным элемента,

А(i) – значение переставляемого элемента.

Тогда циклический алгоритм сортировки модифицированным методом простого выбора будет выглядеть, как показано на рис. 20.

Сортировка методом парных перестановок

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

Процесс перестановок пар повторяется просмотром массива с начала до тех пор, пока не будут отсортированы все элементы, т. е. во время очередного просмотра не произойдет ни одной перестановки. Для подсчета количества перестановок целесообразно использовать счетчик – специальную переменную В. Если при просмотре элементов массива значение счетчика перестановок осталось равным нулю, то это означает, что все элементы отсортированы (см. рис. 21).