Материал: Глава 14. Алгоритмы сортировки

§14.1 Внутренняя сортировка данных

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

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

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

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

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

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

1

элементов. Подсчет именно этих операций лежит в основе методов оценивания трудоемкости алгоритмов сортировки.

Методы сортировки массивов можно разделить на две большие группы:

• Универсальные методы, не требующие никакой дополнительной информации об исходных данных и выполняющие сортировку «на месте», т.е.

без использования больших объемов дополнительной памяти (например – для размещения копии исходного массива); такие методы в лучшем случае дают оценку трудоемкости порядка ( 2 )

• Специальные методы, которые либо за счет некоторой дополнительной информации об исходных данных, либо за счет использования большой дополнительной памяти позволяют получить более высокую производительность сортировки порядка O(n) (примеры – карманная

ипоразрядная сортировка)

Всвою очередь, универсальные методы сортировки делятся на две подгруппы:

• Простейшие методы с трудоемкостью порядка (2): сортировка обменом, сортировка выбором и сортировка вставками

• Улучшенные методы с трудоемкостью ( 2 ): метод Шелла, пирамидальная сортировка, быстрая сортировка

Возникает справедливый вопрос: зачем нужны простейшие методы,

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

Подобные ситуации уже были упомянуты выше: если надо очень много (сотни тысяч или миллионы) раз повторить сортировку весьма небольших массивов

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

простейшие методы сортировки имеют исключительно простую и понятную

2

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

методах.

§14.2 Простейшие методы сортировки: метод обмена

Данный метод относится к классу простейших, занимая в нем последнее место по производительности. Тем не менее, он очень широко известен,

видимо, благодаря своему одному легко запоминающемуся названию – метод

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

Пусть имеется n элементов а1 а2, а3, . . ., аn, расположенных в ячейках массива. Для простоты будем считать, что сам элемент совпадает с его ключом. Алгоритм состоит в повторении n-1 шага, на каждом из которых в оставшемся необработанном наборе за счет попарного сравнения соседних элементов отыскивается минимальный элемент.

Шаг 1. Сравниваем аn с аn-1 и если аn < аn-1 то меняем их местами, потом сравниваем аn-1 с аn-2 и, возможно, переставляем их, сравниваем аn-2 и аn-3 и

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

Шаг 2. Аналогично сравниваем аn с аn-1, аn-1 с аn-2 и т.д., а3 с а2, в результате чего на месте а2 оказывается второй наименьший элемент, который вместе с а1

образует начальную часть упорядоченного массива Шаг 3. Аналогичными сравнениями и перестановками среди элементов а3,

а4, …, аn находится наименьший, который занимает место а3

. . . . .

Шаг n-1. К этому моменту первые n-2 элемента в массиве уже упорядочены и остается “навести порядок” только между двумя последними элементами аn-1 и аn. На этом сортировка заканчивается.

Пример. Дано 6 элементов – целые числа 15, 33, 42, 07, 12, 19. 3

Итого, для шести элементов сделано 5+4+3+2+1 = 15 сравнений и 8

перестановок.

В общем случае, на каждом из − 1 шагов выполняется в среднем /2

сравнений, поэтому оценка для числа сравнений выражается соотношением

( − 1)/2, т.е. данный метод относится к классу ( 2). Аналогично, число перестановок тоже пропорционально n2. Несмотря на то, что было предложено несколько улучшений данного метода (есть очень красивые названия –

4

например, шейкер-сортировка), он остается самым неэффективным. Уже для

1000 элементов число сравнений выражается внушительной величиной порядка 500 тысяч.

Программная реализация включает двойной цикл: внешний реализует основные шаги алгоритма, внутренний сравнивает и переставляет элементы,

начиная с конца массива.

Пример программной реализации сортировки методом обмена представлен в листинге 14.1.

Мы создаём функцию BubbleSort. В неё будет передан массив mas,

который мы заполним числами для сортировки.

Здесь мы сравниваем, так сказать, предыдущий элемент (i) с

последующим (j).

Если элемент массива под номером i будет больше, чем элемент

массива под номером j, то меняем элементы местами и продолжаем сравнение дальше, как в алгоритме.

Для изменения «направления» сортировки, где меньший элемент будет

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

5