Структуры и алгоритмы обработки данных

Аналогично, для функции f (n) = 2n + 3n3 - 10 начиная с некоторого n первое слагаемое будет превосходить второе и поэтому данную функцию можно описать оценкой О(2n).

Важность О-оценивания состоит в том, что оно позволяет описывать характер поведения функции f(n) с ростом n: насколько быстро или медленно растет эта функция.

О-оценка позволяет разбить все основные функции на ряд групп в зависимости от скорости их роста:

1. постоянные функции типа О(1), которые с ростом n НЕ растут (в оценивании алгоритмов этот случай встречается крайне редко, но все-таки встречается!)

2. функции с логарифмической скоростью роста О(log 2 n)

3. функции с линейной скоростью роста О(n)

4. функции с линейно-логарифмической скоростью роста О(n*log 2 n)

5. функции с квадратичной скоростью роста О(n2 )

6. функции со степенной скоростью роста О(na) при а>2

7. функции с показательной или экспоненциальной скоростью роста О(2n)

8. функции с факториальной степенью роста О(n!)

В этом списке функции упорядочены именно по критерию скорости роста: сначала идут медленно растущие функции, потом - все более быстро растущие. Графики некоторых функций приведены на рисунке.



Отсюда можно сделать несколько выводов.

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

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

3. Алгоритмы класса О(2n) и О(n!) следует использовать с большой осторожностью, учитывая катастрофический рост их трудоемкости уже при n>100. Например, если число базовых операций определяется соотношением 2n, то при n=100 это число будет примерно равно 1030, и если одна базовая операция выполняется за 1 микросекунду, то это потребует около 1024 секунд, т.е. порядка 1016 лет. К сожалению, задачи с подобной трудоемкостью довольно часто встречаются на практике и их точное решение пока невозможно даже на сверхбыстрых суперкомпьютерах!

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

Есть два основных способа взаимодействия алгоритмов - последовательное и вложенное.

При последовательном выполнении алгоритмов с оценками O(f1), O(f2), …, O(fk) общая трудоемкость определяется трудоемкостью алгоритма с максимальным значением:

O (программы) = Max (O(f1), O(f2), . . ., O(fk))

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

O(программы) = O(f1)*O(f2)*O(f3)

1.2 Классификация задач сортировки и поиска

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

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

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

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

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

· Универсальные методы, не требующие никакой дополнительной информации об исходных данных и выполняющие сортировку "на месте", т.е. без использования больших объемов дополнительной памяти (например - для размещения копии исходного массива); такие методы в лучшем случае дают оценку трудоемкости порядка O(n*log 2 n)

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

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

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

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

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

Общая классификация методов сортировки приводится на схеме. Описание всех методов приводится далее в пособии.

Аналогично можно провести классификацию методов поиска. Прежде всего - внутренний поиск и внешний поиск. Внутренний поиск - универсальный и специальный. Универсальный - поиск в упорядоченном или неупорядоченном наборе данных. Неупорядоченный набор - метод простого перебора (массив, список, иногда - дерево), упорядоченный - метод двоичного поиска в массиве или дереве. Специальный метод поиска в массиве (хеш-поиск) предполагает особую его организацию и используется при определенных ограничениях (правда, при выполнении этих ограничений данный метод дает потрясающую производительность - одно сравнение для поиска ЛЮБОГО элемента, независимо от объема входных данных!). Внешний поиск реализуется для сверхбольших объемов данных, которые нельзя одновременно разместить в основной памяти и требует использования внешних файлов (один из самых известных методов основан на использовании так называемых B-деревьев). Универсальные методы поиска были рассмотрены ранее, а остальные рассматриваются ниже, после описания методов сортировки.

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

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

Пусть имеется 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.

	а1	а2	а3	а4	а5	а6	Выполняемые операции
шаг 1	15	33	42	07	12	19	сравнение 19 и 12, обмена нет
	15	33	42	07	12	19	сравнение 12 и 07, обмена нет
	15	33	07	42	12	19	сравнение 07 и 42, меняем их
	15	07	33	42	12	19	сравнение 07 и 33, меняем их
	07	15	33	42	12	19	сравнение 07 и 15, меняем их; 07 - наименьший
шаг 2	07	15	33	42	12	19	сравнение 19 и 12, обмена нет
	07	15	33	12	42	19	сравнение 12 и 42, меняем их
	07	15	12	33	42	19	сравнение 12 и 33, меняем их
	07	12	15	33	42	19	сравнение 12 и 15, меняем их, 12 -второй наим.
шаг 3	07	12	15	33	19	42	сравнение 19 и 42, меняем их
	07	12	15	19	33	42	сравнение 19 и 33, меняем их
	07	12	15	19	33	42	сравнение 19 и 15, обмена нет, 15 - третий наим.
шаг 4	07	12	15	19	33	42	сравнение 42 и 33, обмена нет
	07	12	15	19	33	42	сравнение 33 и 19, обмена нет, 19 - четвертый элем.
шаг 5	07	12	15	19	33	42	сравнение 42 и 33, обмена нет, сортировка закончена
	07	12	15	19	33	42

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

В общем случае, на каждом из n-1 шагов выполняется в среднем n/2 сравнений, поэтому оценка для числа сравнений выражается соотношением n(n-1)/2, т.е. данный метод относится к классу O(n2). Аналогично, число перестановок тоже пропорционально n2. Несмотря на то, что было предложено несколько улучшений данного метода (есть очень красивые названия - например, шейкер-сортировка), он остается самым неэффективным. Уже для 1000 элементов число сравнений выражается внушительной величиной порядка 500 тысяч.

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

for i := 2 to n do

begin

for j := n downto i do

if a[j-1] > a[j] then

begin temp := a[j-1]; a[j-1] := a[j]; a[j] := temp; end;

end;

1.4 Простейшие методы сортировки: метод вставок

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

Пусть имеется n элементов а1 а2, а3, . . ., аn, расположенных в ячейках массива. Сортировка выполняется за (n-1) шаг, причем шаги удобно нумеровать от 2 до n. На каждом i-ом шаге обрабатываемый набор разбивается на 2 части:

· левую часть образуют уже упорядоченные на предыдущих шагах элементы а1, а2, а3, . . ., аi-1

· правую часть образуют еще не обработанные элементы аi, аi+1, аi+2, . . ., аn

На шаге i для элемента аi находится подходящее место в уже отсортированной последовательности. Поиск подходящего места выполняется поэлементными сравнениями и перестановками по необходимости: сравниваем аi с аi-1, если аi < аi-1, то переставляем их, потом сравниваем аi-1 с аi-2 и т. д. Сравнения и, возможно, перестановки продолжаются до тех пор, пока не будет выполнено одно из 2-х следующих условий:

· в отсортированном наборе найден элемент, меньший аi (все остальные не просмотренные элементы будут еще меньше)

· достигнут первый элемент набора а1, что произойдет в том случае, если аi меньше всех элементов в отсортированном наборе и он должен занять первое место в массиве

Пример. Возьмем тот же исходный набор целых чисел: 15-33-42-07-12-19

	а1	а2	а3	а4	а5	а6	Выполняемые операции
шаг 2	15	33	42	07	12	19	сравнение 15 и 33, обмена нет, 15 - пока первый
шаг 3	15	33	42	07	12	19	сравнение 33 и 42, обмена нет, 15 и 33 пока первые
шаг 4	15	33	07	42	12	19	сравнение 07 и 42, меняем их
	15	07	33	42	12	19	сравнение 07 и 33, меняем их
	07	15	33	42	12	19	сравнение 07 и 15, меняем их; 07-15-33 пока первые
шаг 5	07	15	33	12	42	19	сравнение 12 и 42, меняем их
	07	15	12	33	42	19	сравнение 12 и 33, меняем их
	07	12	15	33	42	19	сравнение 12 и 15, меняем их
	07	12	15	33	42	19	сравнение 12 и 07, обмена нет, пока: 07-12-15-33
шаг 6	07	12	15	33	19	42	сравнение 19 и 42, меняем их
	07	12	15	19	33	42	сравнение 19 и 33, меняем их
	07	12	15	19	33	42	сравнение 19 и 15, обмена нет, все готово

Для данного примера было сделано 12 сравнений и 8 перестановок, что чуть лучше предыдущего метода. В среднем, число сравнений по данному методу примерно в 2 раза меньше, чем в методе пузырька, оставаясь тем не менее пропорциональным величине n2. Наилучший результат этот метод показывает для уже упорядоченного исходного массива - всего (n-1) сравнение.

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

for i := 2 to n do

begin

temp := a [i]; j := i - 1;

While (j > 0) and (temp < a [j] ) do

begin a [j+1] := a [j]; j := j - 1; end;

a [j+1] := temp;

end;

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

Данный метод из группы простейших имеет лучшие характеристики по числу перестановок, хотя он, как и оба ранее рассмотренных метода, в целом имеет трудоемкость O(n2). Его чуть более лучшие показатели связаны с тем, что в некоторых ситуациях выполняется перестановка не соседних элементов, а отстоящих на некотором расстоянии друг от друга.

Пусть имеется n элементов а1 а2, а3, . . ., аn, расположенных в ячейках массива. Сортировка выполняется за (n-1) шаг, пронумерованных от 1 до n-1. На каждом i-ом шаге обрабатываемый набор разбивается на 2 части:

· левую часть образуют уже упорядоченные на предыдущих шагах элементы а1, а2, а3, . . ., аi-1

· правую часть образуют еще не обработанные элементы аi, аi+1, аi+2, . . ., аn

Суть метода состоит в том, что в необработанном наборе отыскивается наименьший элемент, который меняется местами с элементом аi. На первом шаге (при i = 1), когда необработанным является весь исходный набор, это сводится к поиску наименьшего элемента в массиве и обмену его с первым элементом. Ясно, что поиск наименьшего элемента выполняется обычным попарным сравнением, но соседние элементы при этом не переставляются, что в целом уменьшает число пересылок.

Пример. Возьмем тот же исходный набор целых чисел: 15-33-42-07-12-19

	а1	а2	а3	а4	а5	а6	Выполняемые операции
шаг 1	15	33	42	07	12	19	сравнение 15 и 33, min = 15
	15	33	42	07	12	19	сравнение 15 и 42, min = 15
	15	33	42	07	12	19	сравнение 15 и 07, min = 07
	15	33	42	07	12	19	сравнение 07 и 12, min = 07
	15	33	42	07	12	19	сравнение 07 и 19, min = 07, обмен 15 и 07
шаг 2	07	33	42	15	12	19	сравнение 33 и 42, min = 33
	07	33	42	15	12	19	сравнение 33 и 15, min = 15
	07	33	42	15	12	19	сравнение 15 и 12, min = 12
	07	33	42	15	12	19	сравнение 12 и 19, min = 12, обмен 33 и 12
шаг 3	07	12	42	15	33	19	сравнение 42 и 15, min = 15
	07	12	42	15	33	19	сравнение 15 и 33, min = 15
	07	12	42	15	33	19	сравнение 15 и 19, min = 15, обмен 42 и 15
шаг 4	07	12	15	42	33	19	сравнение 42 и 33, min = 33
	07	12	15	42	33	19	сравнение 33 и 19, min = 19, обмен 42 и 19
шаг 5	07	12	15	19	33	42	сравнение 33 и 42, min = 33, обмена нет, все готово

В данном примере сделано 15 сравнений (как и в методе пузырька), но всего 4 перестановки. Эта особенность сохраняется и в целом: по числу сравнений метод выбора близок к методу пузырька, но по числу перестановок существенно превосходит оба рассмотренные выше методы (оценка числа перестановок n*log 2 n)

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

for i := 1 to n-1 do

begin

k := i; temp := a [i]; {устанавливаем начальный минимальный элемент}

for j := i+1 to n do

if a [j] < temp then

begin {изменяем текущий минимальный элемент}

k := j; temp := a [j];

end;

a [k] := a [i]; a [i] := temp;

end;

Общее заключение по простейшим методам сортировки.

Метод обмена (пузырька) имеет единственное преимущество - нулевое число пересылок в случае, если исходный набор уже отсортирован в нужном порядке.

В остальных случаях все его показатели пропорциональны n2.

Метод вставок также дает хорошие результаты для упорядоченных входных данных (число сравнений и пересылок пропорционально n).

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

Метод выбора, как это и следовало ожидать, имеет лучшие показатели по числу пересылок, особенно - для общего случая, где оценка О(n*log 2 n) заметно лучше оценки O(n2).

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

1.6 Практическое задание

Реализовать программу, объединяющую простейшие методы сортировки массивов:

· сортировку обменом (метод пузырька)

· сортировку выбором

· сортировку вставками

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

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

После завершения разработки программы необходимо выполнить всеми методами сортировку нескольких массивов с разным числом элементов (10, 100, 1.000, 10.000) и провести сравнительный анализ эффективности рассматриваемых методов.

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

Контрольные вопросы по теме

1. В чем состоит задача выбора алгоритмов решения однотипных задач?

2. Какие критерии используются при выборе алгоритмов?

3. Как оценивается трудоемкость алгоритма?

4. Что такое О-нотация и для чего она используется?

5. Какие группы функций можно выделить с помощью О-нотации?

6. Какие рекомендации следует использовать при выборе алгоритмов с помощью О-нотации?

7. Что можно сказать о применимости алгоритмов класса О(2n) и О(n!)?

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

9. Как классифицируются методы сортировки?

10. Что такое внутренняя и внешняя сортировка и в чем состоят особенности этих задач?

11. В чем состоят особенности универсальных и специальных методов внутренней сортировки?

12. Какие основные методы сортировки относятся к универсальным и какую они имеют трудоемкость?

13. В чем состоит практическое значение изучения простейших методов сортировки?

14. Как классифицируются методы поиска?

15. В чем состоит суть метода сортировки обменом?

16. Какие шаги выполняет алгоритм сортировки обменом?

17. Как программно реализуется сортировка обменом?

18. В чем достоинства и недостатки метода сортировки обменом?

19. Приведите практический пример сортировки массива методом обмена.

20. В чем состоит суть метода сортировки вставками?

21. Какие шаги выполняет алгоритм сортировки вставками?

22. Как программно реализуется сортировка вставками?

23. В чем достоинства и недостатки метода сортировки вставками?

24. Приведите практический пример сортировки массива методом вставок.

25. В чем состоит суть метода сортировки выбором?

26. Какие шаги выполняет алгоритм сортировки выбором?

27. Как программно реализуется сортировка выбором?

28. В чем достоинства и недостатки метода сортировки выбором?

29. Приведите практический пример сортировки массива методом выбора.

Тема 2. Улучшенные методы сортировки массивов

2.1 Метод Шелла

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

Алгоритм метода Шелла состоит в многократном повторении двух основных действий:

· объединение нескольких элементов исходного массива по некоторому правилу

· сортировка этих элементов обычным методом вставок

Более подробно, на первом этапе группируются элементы входного набора с достаточно большим шагом. Например, выбираются все 1000-е элементы, т.е. создаются группы:

группа 1: 1, 1001, 2001, 3001 и т.д.

группа 2: 2, 1002, 2002, 3002 и т.д.

группа 3: 3, 1003, 2003, 3003 и т.д.

. . . . . . . . . . . . . . . . . . . . .

группа 1000: 1000, 2000, 3000 и т.д.

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

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

На третьем этапе элементы группируются с еще меньшим шагом, например - все десятые элементы. Выполняется сортировка, группировка с еще меньшим шагом и т.д.

На последнем этапе сначала выполняется группировка с шагом 1, создающая единственный набор данных размерности n, а затем - сортировка практически отсортированного набора.

Пример. Исходный набор: 15 - 33 - 42 - 07 - 12 - 19

Выполняем группировку с шагом 3, создаем три группы по 2 элемента и сортируем каждую из них отдельно:

группа 1: 15 - 07 => 07 - 15 (1 сравнение, 1 пересылка)

группа 2: 33 - 12 => 12 - 33 (1 сравнение, 1 пересылка)

группа 3: 42 - 19 => 19 - 42 (1 сравнение, 1 пересылка)

Новый набор чисел: 07 - 15 - 12 - 33 - 19 - 42

Группировка с меньшим шагом 2 дает 2 группы по 3 элемента, которые сортируются отдельно:

группа 1: 07 - 12 - 19 => уже упорядочена (2 сравнения, 0 пересылок)

группа 2: 15 - 33 - 42 => уже упорядочена (2 сравнения, 0 пересылок)

Новый набор чисел: 07 - 12 - 19 - 15 - 33 - 42

Последняя группировка с шагом 1 дает сам набор чисел; к нему применяется сортировка вставками с 5-ю сравнениями и только одной пересылкой, после чего получаем искомый результат.

Итого - 12 сравнений и 4 пересылки, что, в общем-то, не лучше чем у простых методов. Однако здесь надо учесть два фактора.

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

Фактор 2 (специфический). Эффективность метода Шелла существенно зависит от выбора последовательности шагов группировки. Эта последовательность обязательно должна быть убывающей, а последний шаг обязательно равен 1. В настоящее время неизвестна наилучшая последовательность шагов, обеспечивающая наименьшую трудоемкость. На основе многочисленных экспериментов установлено, что число шагов группировки надо выбирать по формуле [(log 2 n)] - 1, где скобки [ ] используются для обозначения целой части числа, а в качестве самих последовательностей рекомендуется один из следующих наборов (обращаю внимание: для удобства восприятия шаги даются в обратном порядке):

1, 3, 5, 9, 17, 33, . . . (общая формула: tk = (2* tk-1) -1)

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767 . . . (общая формула: tk = (2* tk-1) +1, а еще проще - (2k - 1)).

В соответствии с этими рекомендациями, в предыдущем примере надо взять лишь 2 шага группировки со значениями 3 и 1. В этом случае потребуется лишь 8 сравнений и 5 пересылок.

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

for m := 1 to t do {t - число шагов группировки, m - номер шага}

begin

k := h [m]; {выбор величины шага группировки из заданного массива}

for i := k + 1 to n do {сортировка вставками внутри каждой группы}

begin

temp := a [i]; j := i - k;

while (j > 0) and (temp < a [j]) do

begin

a [j + k] := a [j]; j := j - k;

end;

a [j + k] := temp;

end;

end;

Оценка трудоемкости метода Шелла выражается соотношением O(n1,2), что лучше чем у простейших методов, особенно при больших n.

2.2 Метод быстрой сортировки

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

Более конкретно, алгоритм быстрой сортировки заключается в следующем.

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

· просматривается часть массива, расположенная левее опорного элемента и находится первый по порядку элемент ai > x

· после этого просматривается часть массива, расположенная правее опорного элемента, причем - в обратном порядке, и находится первый по порядку (с конца) элемент aj < x

· производится перестановка элементов ai и aj

· после этого в левой части, начиная с ai отыскивается еще один элемент, больший x, а в правой части, начиная с aj отыскивается элемент, меньший х

· эти два элемента меняются местами

· эти действия (поиск слева и справа с последующим обменом) продолжаются до тех пор, пока не будет достигнут опорный элемент x

· после этого слева от опорного элемента x будут находиться элементы, меньшие опорного, а справа - элементы, большие опорного. При этом обе половины скорее всего не будут отсортированными

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

Пример. Пусть исходный набор включает 11 чисел: 13-42-28-17-09-25-47-31-39-15-20. Основные шаги сортировки:

1. Выбор серединного элемента 25 (индекс 6): 13 42 28 17 09 25 47 31 39 15 20

2. поиск слева первого элемента, большего 25: 42 (2 сравнения)

3. поиск справа от конца первого элемента, меньшего 25: 20 (1 сравнение)

4. перестановка элементов 42 и 20: 13 20 28 17 09 25 47 31 39 15 42

5. поиск слева от 25 еще одного элемента, большего 25: 28 (1 сравнение)

6. поиск справа от 25 еще одного элемента, меньшего 25: 15 (1 сравнение)

7. перестановка элементов 28 и 15: 13 20 15 17 09 25 47 31 39 28 42

8. поиск слева от 25 еще одного элемента, большего 25: нет (2 сравнения)

9. поиск справа от 25 еще одного элемента, меньшего 25: нет (3 сравнения)

10. теперь слева от 25 все элементы меньше 25, а справа - больше

11. выделяем отдельно левую часть: 13 20 15 17 09

12. выбираем серединный элемент 15 (индекс 3): 13 20 15 17 09

13. поиск слева от 15 элемента, большего 15: 20 (2 сравнения)

14. поиск справа от 15 элемента, меньшего 15: 09 (1 сравнение)

15. перестановка 20 и 09: 13 09 15 17 20

16. поиск справа от 15 еще одного элемента, меньшего 15: нет (1 сравнение)

17. теперь слева от 15 все элементы меньше 15, а справа - больше

18. поскольку слева от 15 только 2 элемента, просто сравниваем их друг с другом и переставляем (09 и 13)

19. поскольку справа от 15 только 2 элемента, просто сравниваем их и не переставляем

20. получаем для левой части упорядоченный набор: 09 13 15 17 20

21. возвращаемся к правой части: 47 31 39 28 42

22. выделяем серединный элемент 39 (индекс в данном поднаборе - 3): 47 31 39 28 42

23. поиск слева от 39 элемента, большего 39: 47 (1 сравнение)

24. поиск справа от 39 элемента, меньшего 39: 28 (2 сравнения)

25. переставляем 47 и 28: 28 31 39 47 42

26. поиск слева от 39 еще одного элемента, большего 39: нет (1 сравнение)

27. теперь слева от 39 все элементы меньше 39, а справа - больше

28. поскольку слева от 39 только 2 элемента, просто сравниваем их и не переставляем

29. поскольку справа от 39 только 2 элемента, просто сравниваем их и переставляем (42 и 47)

30. получаем для правой части упорядоченный набор: 28 31 39 42 47

31. вместе с левой частью и серединным элементом 25 получаем окончательный результат

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

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

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

Наилучшее правило выбора опорного элемента - это так называемая медиана. Медиана - это средний элемент массива не по расположению, а по значению. В приведенном выше примере медианой является число 25, которое также было и серединным элементом (честно говоря, пример был подобран специально). К сожалению, поиск медианы в массиве является задачей, сопоставимой по трудоемкости с самой сортировкой, поэтому были предложены другие, более простые правила выбора опорного элемента.

На практике хорошо показал себя следующий способ: выбрать случайно в массиве три элемента и взять в качестве опорного средний из них. Этот способ очень прост в реализации, т.к. требует только двух сравнений, но, конечно, он может обеспечивать хорошие показатели только в среднем, и не гарантирует идеальное поведение алгоритма абсолютно для ЛЮБЫХ входных данных.

Есть и другие усовершенствования базового алгоритма быстрой сортировки. Среди них:

· Проверка каждого подмассива на возможную упорядоченность перед самой сортировкой

· Для малых подмассивов (n < 10) разумно проводить сортировку с помощью более простых методов, например - Шелла

Комбинация всех этих методов известна как метод Синглтона [7].

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

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

Procedure QuickSort (left, right : integer);

{формальные параметры для запоминания границ}

var i, j : integer;

sred, temp : <описание элемента исходного массива>;

begin

i := left; j := right; {установка начальных значений границ подмассива}

sred := mas [(left + right) div 2]; {определение серединного элемента}

repeat

while (mas [i] < sred) do i := i + 1;

{поиск слева элемента, большего опорного}

while (mas [j] > sred) do j := j - 1;

{поиск справа элемента, меньшего опорного}

if i <= j then

begin {обмениваем элементы и изменяем индексы}

temp := mas [i]; mas [i] := mas [j]; mas [j] := temp;

i := i + 1; j := j -1;

end;

until i > j;

if left < j then QuickSort (left , j);{обработка левой половины}

if i < right then QuickSort (i , right);{обработка правой половины}

end;

Первоначальный вызов этой процедуры производится в главной программе в виде QuickSort (1, n); здесь n - число элементов в массиве.

2.3 Пирамидальная сортировка

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

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



Подобное дерево называется пирамидой, если для всех элементов с индексами от 1 до n/2 выполняются следующие условия:

аi <= а2i и аi <= а2i+1

В частности, эти условия означают: а1 <= а2 и а1 <= а3; а2 <= а4 и а2 <= а5; а3 <= а6 и а3 <= а7; а4 <= а8 и а4 <= а9, и т.д.

Другими словами, в каждом элементарном поддереве значение в вершине этого поддерева меньше или равно значений в вершинах-потомках.

Пример двоичного дерева-пирамиды с 15-ю элементами:

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

Из примера видно, что пирамида НЕ является деревом поиска, т.к. строится по другим правилам.

Можно отметить следующие полезные свойства пирамиды:

· на вершине пирамиды всегда находится наименьший элемент во всем массиве (элемент а1), элемент а2 является наименьшим для левого поддерева, элемент а3 является наименьшим для правого поддерева и т.д.

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

Пирамидальная сортировка включает два больших этапа:

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

· последовательные удаления минимального элемента с вершины пирамиды с заменой его другим элементом

Реализация 1 этапа включает следующие шаги:

· условно разделяем исходный массив на две половины: левую с индексами от 1 до [n/2], и правую с индексами от [n/2]+1 до n (здесь [ ] обозначает целую часть); считаем пока, что левая половина образует верхнюю часть строящейся пирамиды, а правая - нижний слой терминальных вершин

· выбираем в левой половине последний элемент (его индекс m=[n/2]), а в правой половине - его непосредственных потомков (одного или двух, но хотя бы один будет обязательно) с индексом 2m и, возможно, 2m+1

· если потомков два, то выбираем из них наименьшего

· сравниваем элемент аm с наименьшим из потомков: если он больше, то меняем эти элементы в массиве местами для получения фрагмента пирамиды; в противном случае оставляем все без изменений, поскольку эти элементы уже образуют фрагмент пирамиды

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

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

Пример для 15 элементов приведен в таблице (символ ~ обозначает перестановку элементов)

В худшем случае каждый шаг в просеивании очередного элемента требует двух сравнений: сначала сравниваются два потомка текущего элемента, а потом наименьший из них сравнивается с самим элементом. В примере для построения пирамиды потребовалось 11*2=22 сравнения и 9 пересылок.

Реализация второго этапа состоит в (n-1)-кратном повторении следующих действий:

· с вершины пирамиды забирается минимальный элемент а1

· на его место в вершину пирамиды помещается последний элемент в массиве, причем индекс этого последнего элемента на каждом шаге будет уменьшаться от аn до а2

· помещенный в вершину элемент просеивается через пирамиду обычным образом, при этом он встает на свое место, а в вершину пирамиды выталкивается минимальный из оставшихся в массиве элементов

· на последнем шаге в пирамиде останется один элемент (самый большой) и сортировка будет закончена

При этом возникает вопрос - куда девать снимаемые с вершины пирамиды элементы? Можно просто помещать их в конец массива на место элемента, размещаемого в вершине. В результате на месте исходного массива создается упорядоченный ПО УБЫВАНИЮ набор данных.

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

В данном примере выполнено 51 сравнение и 40 пересылок, что вместе с этапом построения пирамиды дает 73 сравнения и 49 пересылок.

В целом, данный метод с точки зрения трудоемкости имеет типичное для улучшенных методов поведение: довольно высокая трудоемкость для небольших n, но с ростом n эффективность метода растет. При больших n метод в среднем немного уступает быстрой сортировке и имеет оценку порядка (n*log 2 n)/2. Единственное, в чем он превосходит быструю сортировку, так это поведение на аномальных входных данных, когда быстрая сортировка перестает быть "быстрой", а пирамидальная сохраняет свою трудоемкость порядка O(n*log 2 n). В [4] указывается, что пирамидальную сортировку выгодно использовать в том случае, когда требуется не провести полную сортировку большого набора данных, а лишь найти несколько (причем - немного) первых наименьших элементов.

Необходимо отметить, что понятие пирамидального дерева имеет и самостоятельное значение, и часто используется для решения других задач, не связанных с сортировкой массивов, например - для эффективной реализации приоритетных очередей [4].

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

Procedure Sito (al, ar : word);

var i, j : word;

x : <описание элемента массива>;

begin

i := al; j := 2*al; x := mas[al];

if (j < ar) and (mas[j + 1] < mas [j] ) then j := j + 1;

while (j <=ar) and (mas[j] < x) do

begin

mas [i] := mas [j]; i :=j; j :=2*j;

if (j < ar) and (mas[j + 1] < mas[j]) then j := j + 1;

end;

mas[i] := x;

end;

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

left := (n div 2) + 1; right := n;

{определение границ правой половины массива}

while left > 1 do

begin {цикл построения пирамиды}

left := left - 1; Sito (left, right);

end;

while right > 1 do (цикл сортировки}

begin

temp := mas[1]; mas[1] := mas[right]; mas[right] := temp;

right := right - 1; Sito (left, right);

end;

2.4 Практическое задание

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

Каждый метод реализуется своей подпрограммой, добавляемой в основную программу по мере разработки. Каждый исходный массив должен обрабатываться всеми программами сортировки с подсчетом и выводом фактического числа выполненных сравнений и пересылок. После завершения разработки программы необходимо выполнить всеми методами сортировку нескольких массивов с разным числом элементов (10, 100, 1.000, 10.000) и провести сравнительный анализ эффективности рассматриваемых методов.

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

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

Контрольные вопросы по теме

1. В чем состоит суть сортировки методом Шелла?

2. За счет чего метод Шелла дает лучшие показатели по сравнению с простейшими методами?

3. Приведите практический пример сортировки массива методом Шелла.

4. Какой фактор оказывает наибольшее влияние на эффективность сортировки методом Шелла?

5. Какие последовательности шагов группировки рекомендуются для практического использования в методе Шелла?

6. Как программно реализуется сортировка методом Шелла?

7. В чем состоит суть метода быстрой сортировки?

8. За счет чего метод быстрой сортировки дает лучшие показатели по сравнению с простейшими методами?

9. Что такое опорный элемент в методе быстрой сортировки и как он используется?

10. Приведите практический пример быстрой сортировки массива.

11. Что можно сказать о применимости метода быстрой сортировки с точки зрения его эффективности?

12. Какой фактор оказывает решающее влияние на эффективность метода быстрой сортировки?

13. Почему выбор серединного элемента в качестве опорного в методе быстрой сортировки может резко ухудшать эффективность метода?

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

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

16. Какие усовершенствования имеет базовый алгоритм метода быстрой сортировки?

17. Почему быстрая сортировка проще всего программно реализуется с помощью рекурсии?

18. Как программно реализуется рекурсивный вариант метода быстрой сортировки?

19. Какие особенности имеет не рекурсивная программная реализация метода быстрой сортировки?

20. В чем состоит суть метода пирамидальной сортировки?

21. Какой набор данных имеет пирамидальную организацию?

22. Чем отличаются друг от друга дерево поиска и пирамидальное дерево?

23. Приведите пример пирамидального дерева с целочисленными ключами.

24. Какие полезные свойства имеет пирамидальное дерево?

25. Какие шаги выполняются при построении пирамидального дерева?

26. Что такое просеивание элемента через пирамиду?

27. Приведите практический пример построения пирамидального дерева.

28. Какие шаги выполняются на втором этапе пирамидальной сортировки?

29. Приведите практический пример реализации второго этапа пирамидальной сортировки.

30. Что можно сказать о трудоемкости метода пирамидальной сортировки?

Тема 3. Специальные методы сортировки

3.1 Простейшая карманная сортировка

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

Самая простая разновидность специальных методов - так называемая карманная сортировка.

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

· ключи являются целыми числами, изменяющимися только от 1 до n

· все эти ключи различные

В этом случае ключи можно рассматривать как индексы элементов в массиве. Если в исходном массиве значение ключа может НЕ совпадать с индексом элемента, то после сортировки соответствие должно быть полным: ключ 1 - в ячейке 1, ключ 2 - в ячейке 2 и т.д., ключ n - в ячейке n.

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

Например, для массива из 10 элементов с неповторяющимися ключами от 1 до 10 получим:



Вся сортировка сводится лишь к 10 пересылкам и не требует ни одного сравнения! Реализация - одним единственным циклом (здесь Mas - исходный массив, RezMas - результирующий):

for i := 1 to n do

RezMas[Mas[i].key] := Mas[i];

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

· берем первый элемент в исходном массиве, пусть его ключ равен i

· перемещаем в массиве первый элемент в ячейку i, а i-ый элемент - в первую ячейку; после этой операции i-ый элемент окажется на своем месте

· если ключ первого элемента не равен 1 (например - j ), то обмениваем его с j-ым элементом, после чего и j-ый элемент оказывается на своем месте

· повторяем эти действия до тех пор, пока на первом месте не окажется элемент с ключом 1, причем каждое повторение обязательно размещает один элемент массива на своем "законном" месте

· при необходимости повторяем эти действия и для других элементов массива

Пример работы алгоритма

4	2	5	7	1	8	3	10	6	9	1.key = 4, меняем элементы 4 и 1
7	2	5	4	1	8	3	10	6	9	1.key = 7, меняем элементы 7 и 1
3	2	5	4	1	8	7	10	6	9	1.key = 3, меняем элементы 3 и 1
5	2	3	4	1	8	7	10	6	9	1.key = 5, меняем элементы 5 и 1
1	2	3	4	5	8	7	10	6	9	1.key = 1, также для 2, 3, 4, 5; 6.key = 8, обмен 6 и 8
1	2	3	4	5	10	7	8	6	9	6.key = 10, меняем 6 и 10
1	2	3	4	5	9	7	8	6	10	6.key = 9, меняем 6 и 9
1	2	3	4	5	6	7	8	9	10	6.key = 6, также для остальных; все готово

В этом примере потребовалось 17 сравнений и 7 пересылок. В общем случае, трудоемкость метода пропорциональна n.

Схема программной реализации:

for i := 1 to n do

while Mas[i]. key <> i do

"переставить Mas[i] и Mas[Mas[i].key]";

3.2 Карманная сортировка для случая повторяющихся ключей

Рассмотренный метод можно обобщить следующим образом. Пусть по-прежнему ключи могут иметь значения только от 1 до n, но во входном наборе каждое значение может повторяться любое число раз, в том числе и ноль. Пусть исходный массив содержит m элементов, причем m>n. В этом случае с одним и тем же ключом может быть связано несколько элементов, и их нельзя поместить в одну ячейку результирующего массива.

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

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

Пример. Пусть задан следующий входной набор из 15 элементов с диапазоном изменения ключей от 1 до 5 (в скобках указан ключ элемента):

а1(4), а2(2), а3(5), а4(1), а5(4), а6(3), а7(4), а8(3), а9(5), а10(1), а11(3), а12(2), а13(2), а14(5), а15(3)

Тогда эти элементы будут распределены следующим образом:

После объединения списков получим:

а4, а10, а2, а12, а13, а6, а8, а11, а15, а1, а5, а7, а3, а9, а14

Для программной реализации необходимо объявить массив указателей и ссылочный тип для поддержки списков. Дополнительные затраты памяти связаны в первую очередь с реализацией дополнительных списков, т.к. общее число элементов в этих списках равно m, а кроме того для каждого элемента надо 4 байта для адресных полей. Трудоемкость данного метода оценивается соотношением O(m+n), а при m>>n становится пропорциональной числу элементов m.

3.3 Поразрядная сортировка

Данный метод является обобщением карманной сортировки. Пусть известно, что каждый ключ является k-разрядным целым числом. Например, если k = 4, то все ключи находятся в диапазоне 0000 - 9999. Смысл поразрядной сортировки заключается в том, что k раз повторяется карманная сортировка. На первом шаге все ключи группируются по младшей цифре (разряд единиц). Для этого в каждом ключе выделяется младшая цифра и элемент помещается в соответствующий список-карман для данной цифры. Потом все списки объединяются и создается новый массив, в котором элементы упорядочены по младшей цифре ключа. К этому массиву опять применяется карманная сортировка, но уже по более старшей цифре (разряд десятков): в каждом ключе выделяется вторая справа цифра и элементы распределяются по соответствующим спискам. Потом списки объединяются в массив, где элементы будут упорядочены уже по двум младшим цифрам. Процесс распределения по все более старшим цифрам с последующим объединением повторяется до старшей цифры (разряд k).

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

Пример. Пусть имеется исходный набор из 15-ти двухразрядных ключей (k=2):

56, 17, 83, 09, 11, 27, 33, 02, 16, 45, 08, 37, 66, 99, 90

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

ключ 56 в список для цифры 6, ключ 17 в список для цифры 7, ….., ключ 16 опять в список для цифры 6 и т.д.

0	1	2	3	4	5	6	7	8	9

90 11 02 83 45 56 17 08 09

33 16 27 99

66 37

Объединяем списки:

90, 11, 02, 83, 33, 45, 56, 16, 66, 17, 27, 37, 08, 09, 99

В этом наборе ключи упорядочены по младшей цифре