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

Сортировка — это перегруппировка множества элементов в некотором определённом порядке. Такими элементами могут быть числа (сортировка числового массива), символы, строки (рассортировать фамилии студентов), данные разных типов (информация об одном абоненте в телефонном справочнике, информация о книге в электронной библиотеке и т.п.). Цель сортировки — облегчить поиск элементов в таком упорядоченном множестве.

Интерес к сортировке объясняется несколькими причинами. При построении алгоритмов её реализации мы имеем дело с различными методами и приёмами программирования. С её помощью можно продемонстрировать многообразие алгоритмов для решения одной и той же задачи и анализ их эффективности. Основными критериями для выбора наилучшего метода сортировки ивляются время выполнения программы и дополнительный объём памяти.

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

Основным требованием к рассматриваемым алгоритмам является требование экономного расходования памяти. Перестановки, приводящие элементы в заданный порядок, должны выполняться на том же месте оперативной памяти. Другими словами, запрещается формировать новый дополнительный массив.

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

Методы сортировки массивов можно разбить на следующие основные группы, внутри которых существуют различные их модификации:

· сортировка обменом;

· сортировка выбором;

· сортировка включением (или вставками).

Пример 1. Рассмотрим алгоритм обменной сортировки. Массив просматривается в обратном направлении от конца к началу или в прямом направлении. При сортировке по возрастанию для первого варианта используют термин “пузырьковая” сортировка. Последовательно сравниваем каждую пару двух соседних элементов. Если они не удовлетворяют требуемому отношению порядка, то меняются местами, иначе остаются на своих местах.

Например, если массив 54, 43. 11. 77, 33, 90, 16 сортируем по возрастанию, то после первого прохода от начала к концу последовательно получим

43, 54. 11. 77, 33, 90, 16,

43, 11. 54. 77, 33, 90, 16

43, 11. 54, 77, 33, 90, 16

43, 11. 54, 33, 77, 90, 16

43, 11. 54. 33, 77, 90, 16

43, 11. 54. 33, 77, 16, 90

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

После второго прохода получим 11, 43, 33, 16, 54, 77, 90. Результаты сравнения и перестановок каждой пары здесь и дальше не показаны. Ещё два этапа дадут окончательный результат:

11, 33, 16, 43, 54, 77, 90

11, 16, 33, 43, 54, 77, 90

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

void RR(int &u, int &v) { int t=u; u=v; v=t; }; Заметим, что в этой функции формальными параметрами являются неиндексированные переменные, несмотря на то, что использовать её будем для перестановки двух элементов массива.

В первом, плохом, варианте и внутренний, и внешний циклы можно повторить не более size раз, где size — размерность одномерного массива x.

for ( int k=1; k<size; k++)

for(int j=0; j<size-1; j++)

if ( x[j]>x[j+1] ) RR(x[j], x[j+1]);

Улучшим внутренний цикл. Легко заметить, что после первого этапа наибольшее число массива 90 заняло своё последнее место. Это не зависит от того, где оно было до сортировки. После второго этапа второе наибольшее число 77 заняло предпоследнее место, и так далее. Поэтому если вначале надо анализировать все пары чисел, то на втором этапе последнее число можем не учитывать, так как оно уже на своём месте. Аналогично, на каждом последующем этапе количество сравниваемых пар можно на одну уменьшать. Тогда внутренний цикл будет таким: for(int j=0; j<size-k; j++) …

Оптимизация внешнего цикла. Всегда ли надо (size-1) просмотров массива? Для “хорошего” массива, который частично рассортирован, результат можем получить и раньше. Например, массив 33, 11, 16, 54, 77, 43, 90 будет рассортирован после второго прохода. Как c учётом этого организовать внешний цикл? Предлагается следующее. Просмотр и анализ массива будем продолжать, если на предыдущем этапе была хотя бы одна перестановка. Если окажется, что ни одну пару не переставляли, то это означает, что массив рассортировали и можно выйти из внешнего цикла. Это реализуется с помощью дополнительной переменной flag, которая в начале каждого прохода принимает нулевое значение.. Если на каком-то шаге была хотя бы одна перестановка, переменная flag изменит своё значение на единицу, и внешний цикл продолжаем. В противном случае, если не было ни одной перестановки, останется flag=0, и сортировка прекращается.

int flag=1, k; k=size;

while (flag) { k--; flag=0;

for(int j=0; j<k; j++)

if (x[j]>x[j+1]) { RR(x[j], x[j+1]); flag=1; }

}

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

Используемый при написании программы сортировки приём можно назвать методом последовательного (поэтапного) улучшения алгоритма (программы).Вначале составляем наиболее простой с точки зрения программирования, но не обязательно эффективный алгоритм. Его можем запрограммировать и отладить. При этом возможны, но не обязательны, некоторые упрощения постановки задачи. Здесь это не делали. Отладив такой плохой вариант, улучшаем алгоритм и (или) программу и снимаем, если вводили, ограничения на условие задачи.