§ 18. Сортировка одномерного массива

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

В отсортированном виде хранятся данные в списке контактов в смартфоне (в алфавитном порядке) или письма в электронном почтовом ящике (в порядке получения), данные в различных справочниках и энциклопедиях.

Задача сортировки состоит в такой  перестановке элементов последовательности, чтобы для двух соседних элементов выполнялось условие того, что они находятся в порядке. Порядок элементов определяет функция сравнения, которая на любых двух элементах последовательности принимает одно из трех значений: меньше, больше или равно. Таким образом, сортировка множества элементов возможна тогда, когда для этого множества введено понятие порядка.

Часто среди элементов сортируемой последовательности могут оказаться равные по значению элементы. В этом случае принято говорить о порядке неубывания (невозрастания). В общем случае элементы могут быть не равны по значению, но считаться равными относительно функции сравнения (пример 18.2).

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

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

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

Давайте представим, что перед нами поставлена задача расставить N  чисел по возрастанию. Как бы мы ее решали?

Наверное, пришлось бы сначала найти минимальное из всех чисел и поставить его на первое место в последовательности. Затем из еще неотсортированных элементов надо было бы опять выбрать минимальный элемент и поставить его после уже отсортированной части и т. д. (пример 18.3)

Рассмотрим работу данного метода на массиве a = {9, 6, 0, 2, 7, 3, 1, 5}. Минимальный элемент на каждом шаге подчеркнут (пример 18.4). Цветом выделен тот элемент, который на текущем шаге меняется местами с минимальным.

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

Формальное описание алгоритма. На i-м шаге (i = 0, …, n - 1) выполняем:

1. Выбираем из элементов с индексами от i до n–1 минимальный.
2. Меняем местами найденный минимальный элемент и элемент a[i]. На i-м месте оказывается минимальный элемент из еще неотсортированной части массива.
3. После выполнения последнего шага в позиции a[n–1] будет находиться самый большой элемент массива.

Посчитаем количество сравнений, которые пришлось сделать для упорядочения массива. На первом шаге для нахождения максимального элемента необходимо (n – 1) сравнений, на втором — (n – 2), на третьем (n – 3), ..., на последнем шаге — одно сравнение. Найдем сумму: n – 1 + n – 2 + n – 3  ... + 1 =  Или, другими словами порядка n² операций[1].

Рассмотрим еще один метод сортировки, который называется сортировка обменом. Название метода определяется тем, что алгоритм основывается на обмене местами двух элементов массива. Меняются местами те два соседних элемента в массиве, которые стоят «не в порядке».

Рассмотрим его на примере того же массива a = {9, 6, 0, 2, 7, 3, 1, 5} (пример 18.6). Цветом выделен тот элемент, правее которого просматривать массив нет необходимости, поскольку элементы, стоящие там, уже отсортированы.

Формальное описание алгоритма. На i-м шаге (i = 1, …, n – 1) выполняем:

1. Сравниваем первые два элемента. Если первый больше второго, то меняем их местами.

2. Затем сравниваем второй и третий, третий и четвертый, ..., i и i + 1, при необходимости меняя их местами.

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

Фрагмент программы, содержащий алгоритм сортировки обменом, приведен в примере 18.7.

Число сравнений в данном алгоритме, как и в алгоритме сортировки выбором, равно 

При каждом сравнении возможна перестановка двух элементов в массиве. Поэтому количество перестановок (в худшем случае) будет равно количеству сравнений, т. е. порядка n² операций.

На последних двух проходах в примере 18.6 массив не менялся. Заметим, что если на каком-то шаге алгоритма элементы массива уже упорядочены, то при последующих проходах по массиву перестановки больше выполняться не будут. Следовательно, как только количество выполненных на последнем проходе перестановок станет равным 0, то алгоритм можно заканчивать (пример 18.8).

Если проанализировать сортировку обменом, то можно заметить, что самое маленькое число занимает свое место за один проход по массиву, а самое большое перемещается по направлению к своему месту на одну позицию при каждом проходе. Это наводит на мысль чередовать направление проходов. Такая сортировка называется шейкер-сортировкой (шейкерная сортировка, сортировка перемешиванием, коктейльная сортировка). Рассмотрим ее работу на том же массиве а = {9, 6 0, 2, 7, 3, 1, 5} (примеры 18.9, 18.10).

Будем просматривать элементы массива a, начиная со второго. Каждый новый элемент a[i] будем вставлять на подходящее место в уже упорядоченную часть массива a[1], ..., a[i–1]. Место вставки определяется путем сравнения элемента a[i] с упорядоченными элементами a[1], ..., a[i–1].

Такой метод сортировки называется сортировкой простыми вставками. Он также требует порядка n² операций сравнения и столько же перестановок элементов в массиве.

Рассмотрим ее работу на массиве а = {9, 6 0, 2, 7, 3, 1, 5} (примеры 18.11). Цветом выделены элементы уже отсортированной части.

Формальное описание алгоритма. На i-м шаге (i = 1, …, n – 1) выполняем:

1. Берем первый элемент в неотсортированной части массива.
2. Последовательно сравниваем его с элементами в отсортированной части, до тех пор, пока не определим место для вставки.
3. Сдвигаем элементы вправо на один, освобождая место для вставки.

Фрагмент программы, содержащий алгоритм сортировки простыми вставками, приведен в примере 18.12.

Рассмотрим еще один алгоритм сортировки, который является существенным улучшением алгоритма сортировки обменом. Сортировка обменом является одним из самых неэффективных алгоритмов сортировки. Однако усовершенствованный алгоритм позволяет получить результат намного быстрее, поэтому, его изобретатель Чарльз Хоар назвал этот алгоритм быстрой сортировкой (quicksort). Высокая производительность достигается за счет того, что происходит обмен элементов на больших расстояниях.

В массиве выбирается некоторый элемент, называемый опорным. Для остальных элементов производятся перестановки таким образом, чтобы слева от опорного находились элементы не больше его, а справа — не меньше. Тем самым массив разбивается на две части:

• не отсортированные элементы слева от опорного элемента;
• не отсортированные элементы справа от опорного элемента.

В дальнейшем для каждой части действия повторяются. Следует заметить, что конечная позиция опорного элемента необязательно совпадает с его позицией до перестановок элементов.

Рассмотрим ее работу на том же массиве а = {9, 6, 0, 2, 7, 3, 1, 5} (пример 18.14).

Формальное описание алгоритма:

1. Заведем два указателя: левый и правый, которые позволят перемещаться по элементам массива с начала и с конца.

2. В качестве опорного элемента выберем элемент, стоящий на среднем месте.

3. Слева от опорного элемента найдем не меньший, а справа — не больший, чем опорный, и поменяем их местами.

4. Обмен элементов производим, пока указатель из левой части не станет больше указателя из правой части.

5. Рекурсивно обрабатываем 2 части массива: от начала до значения правого указателя и от значения левого указателя до конца.

Рекурсивная функция быстрой сортировки приведена в примере 18.15.

В худшем случае алгоритм требует порядка n² операций сравнения и столько же перестановок элементов в массиве. Однако такие случаи встречаются нечасто (пример 18.16). В среднем, если при каждом рекурсивном вызове массив делится на две почти равные части, то количество требуемых операций будет порядка nk, где значение k определяется из равенства 2^k = n. Значение k также определяет размер дополнительной памяти для хранения стека рекурсивных вызовов.

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

Функцию для сравнения двух объектов называют компаратором (от англ. compare — сравнить).

Функция-компаратор зависит от двух параметров и возвращает логическое значение. Тип параметров функции должен совпадать с типом элементов в массиве. Функция должна возвращать знание true, для двух значений, которые находятся «в порядке» и false в противном случае.

Пример 18.17. Дан линейный массив из целых чисел. Написать программу сортировки массива так, чтобы все четные числа стояли в начале массива, а нечетные — в конце. Данные сгенерировать случайным образом.

Этапы выполнения задания

I. Исходные данные: переменные n — количество чисел в массиве, a — массив.

II.  Результат: отсортированный массив а.

III. Алгоритм решения задачи.

1. Ввод исходных данных. Элементы массива сгенерированы случайным образом.
2. Для решения задачи будем использовать алгоритм сортировки обменом.
3. Создадим компаратор (функцию сравнения), которая будет сравнивать числа по остаткам от деления на 2.
4. Будем менять элементы местами, если они расположены «не в порядке».
5. Вывод результата.

IV. Описание переменных: n – int, a –  vector<int>.

Для решения этой задачи выбор алгоритма сортировки обменом не является оптимальным, поскольку он потребует порядка n² операций сравнения и обмена. Пример необходим для того, чтобы показать использование функции-компаратора.

Для получения оптимального решения можно исходить из того факта, что все числа относительно остатка при делении на 2 бывают всего двух категорий (четные и нечетные), и для их сортировки достаточно всего одного прохода по массиву. Это можно сделать по аналогии с алгоритмом быстрой сортировки с помощью двух указателей: слева ищем первый нечетный, а справа — последний четный и меняем их местами (пример 18.18).

Пример 18.19. Дан линейный массив из слов. Написать программу сортировки массива так, чтобы слова располагались в порядке убывания количества букв «а» в слове. Данные прочитать из файла.

Этапы выполнения задания

I. Исходные данные: переменные n — количество слов в массиве, a — массив.

II. Результат: отсортированный массив а.

III. Алгоритм решения задачи.

1. Ввод исходных данных..
2. Для решения задачи будем использовать алгоритм сортировки выбором.
3. Создадим компаратор (функцию сравнения), которая будет сравнивать слова по количеству букв «а» в слове.
4. Также создадим функцию, которая будет определять количество букв «а» в слове.
5. Вывод результата.

IV. Описание переменных: n – int, a –  vector<string>.

Пример 18.20. В текстовом файле input.txt хранится информация о студентах. Для каждого студента указана его фамилия, город, из которого он приехал, и три числа — баллы за ЦТ, с которыми он поступил в вуз. Отсортировать список студентов в порядке убывания суммарного балла за ЦТ. Вывести фамилию, город и суммарный балл.

Этапы выполнения задания

 I. Исходные данные: переменные n — количество записей о студентах, a — массив структур.

 II. Результат: отсортированный массив а.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. В описании структуры, кроме полей, указанных в условии задачи, добавим поле сумма, в которой запишем суммарный балл (описание структуры было разобрано в примере 17.8).
3. Для решения задачи будем использовать алгоритм сортировки простыми вставками.
4. Создадим компаратор (функцию сравнения), которая будет сравнивать две структуры по полю суммы баллов.
5. Вывод результата.

1. На каких принципах основана сортировка выбором?

2. На каких принципах основана сортировка обменом?

3. В чем суть сортировки простыми вставками?

4. За какое количество операций сравнения будет отсортирован массив, если применять сортировку обменом?

5. Сколько перестановок будет сделано для упорядочения массива, если применять сортировку выбором?

6. В чем преимущество алгоритма быстрой сортировки?

7. Какие недостатки есть у алгоритма быстрой сортировки?