Задача 37. Сортировка массива методом попарно-обменных перестановок

Условие задачи. Отсортировать заданный массив по возрастанию методом попарно-обменных перестановок.

Сортировка - это классическая задача программирования. 25% времени работы компьютеров приходится на реализацию этого процесса. Сортировка – это перестановка заданного множества элементов в некотором определённом порядке. Порядок расположения элементов может быть следующим:

§ По возрастанию, если каждый следующий объект больше предыдущего.

§ По неубыванию, если каждый следующий объект больше либо равен предыдущему.

§ По убыванию, если каждый следующий объект меньше предыдущего.

§ По невозрастанию, если каждый следующий объект меньше либо равен предыдущему.

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

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

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

Поэтому после однократного прохода по массиву для полной сортировки массива необходимо выполнить еще один аналогичный просмотр. В этот раз должна быть пройдена часть массива, предшествующая последнему элементу (от первого элемента до предпоследнего), для нахождения второго по величине значения и его перемещения на место, предшествующее последнему элементу, и так далее, пока оставшаяся для очередного просмотра часть массива не станет состоять всего из одного элемента — первого элемента сортируемого массива, значение которого к этому моменту уже будет точно наименьшим при сортировке по возрастанию (или наибольшим при сортировке по убыванию). Таким образом, сначала выполняется просмотр части массива длиной N, затем N –1, затем N –2, и так далее. Последним выполняется просмотр части массива из 2 элементов. Массив из одного элемента не проверяется — в нем нет пары для сравнения. Всего последовательный просмотр со сравнением и перестановками выполняется N –1 раз.

Для реализации такого поведения используем алгоритмическую конструкцию «цикл с предопределенным числом повторений» для повторения N –1 раз действия «просмотр массива с попарным сравнением значений элементов и перестановкой при необходимости». Причем, на каждой его i -й итерации будут попрано сравниваться с соседними только элементы исходного массива с 1-го по N – i +1 (то есть сравниваются пары элементов, где ближайший к началу элемент имеет индекс с 1-го по N – i). Просмотр элементов также реализуется с помощью вложенной алгоритмической конструкции «цикл с предопределенным числом повторений», причем для каждой i -й итерации внешнего цикла, тело вложенного цикла будет выполняться N – i раз. Если переменная i — счетчик внешнего цикла, а переменная j — счетчик внутреннего цикла, то i последовательно принимает значения от 1 до N –1, а для каждого значения i переменная j последовательно принимает значения от 1 до N – i, где N — количество элементов массива.

Предположим, что у нас существуют следующие переменные: некоторый массив Marr, натуральное число Lma, соответствующее числу элементов массива Marr, переменная для временного хранения элемента массива TmEl. Тогда алгоритм попарно-обменной сортировки по возрастанию массива Marr длины Lma, введенного пользователем, с последующим выводом отсортированного массива, можно записать следующим образом: