Оценка сложности алгоритмов сортировки

УДК 681.3.(07)

Оценка сложности алгоритмов сортировки

1, 2

Национальный исследовательский Иркутский государственный технический университет,

664074, г. Иркутск, Лермонтова, 83.

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

Ил. 2. Табл. 3. Библиогр. 3 назв.

Ключевые слова: алгоритм; оценка сложности алгоритма; методы сортировки; асимптотические классы оценки.

EVALUATION OF SORTING ALGORITHMS COMPLEXITY

O. Tomskikh, A. Gorokhov

National Research Irkutsk State Technical University,

83 Lermontov St., Irkutsk, 664074

The authors investigate theoretical and practical evaluation of methods to sort arrays. The article demonstrates the results of sorting program by several methods and concludes about their effectiveness according to input data level.

Illustrations: 2 figs. Sources: 3 refs.

Key words: algorithm, estimation of the algorithm complexity, sorting methods, asymptotic evaluation classes

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

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

метод пузырька (существуют разные модификации); метод вставки; метод слияния; метод вычерпывания; метод Шелла; бинарные методы.

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

Алгоритмы сортировки можно сравнивать по числу сравнений значений ключа и количеству перестановок элементов.

В табл. 1 [1] приведены значения меры эффективности алгоритмов внутренней сортировки С (от английского Compare) и М (от английского Move).

Использованы оценки для методов:

Сортировка пузырьком (Bubble sort); сложность алгоритма: O(n2); для каждой пары индексов производится обмен, если элементы расположены не по порядку. Сортировка вставками (Insertion sort); сложность алгоритма: O(n2); определяем, где текущий элемент должен находиться в упорядоченном списке, и вставляем его туда. Сортировка выбором (Selection sort); сложность алгоритма: O(n2); поиск наименьшего или наибольшего элемента и помещения его в начало или конец упорядоченного списка.

Таблица 1

Теоретические характеристики методов сортировки

Массив	Показатель/ метод	Insert	Select	Bubble
Упорядоченный	C	N–1	(N2 – N)/2	(N2 – N)/2
M	2(N–1)	3(N–1)	0
Обратно упорядоченный	C	(N2 + N – 2)/4	(N2 – N)/2	(N2 – N)/2
M	(N2 – 9N – 10)/4	N(Ln(N) + 0,57)	0,75(N2 – N)
Случайный	C	(N2 –N)/2 – 1	(N2 – N)/2	(N2 – N)/2
M	(N2 –3N – 4)/2	N2/4 + 3(N–1)	1,5(N2 – N)

Для получения реальных значений была разработана программа с использованием языка С++ в системе программирования NeatBeancs.  В табл. 2 приведены данные на примере массива из 50 элементов.

Таблица 2

Практические характеристики методов сортировки

Массив	Показатель/ метод+(t)	Insert	Select	Bubble
Упорядоченный	C	49	1225	1225
M	0 (0,180ms)	0 (0,284ms)	0 (0,282 ms)
Обратно упорядоченный	C	1225	1225	1225
M	1225(0,257ms)	50 (0,317ms)	1225(0,388ms)
Случайный	C	583	1225	1225
M	533(0,249ms)	50(0,260ms)	536(0,331ms)

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

Таблица 3

Временные характеристики методов сортировки, ms (миллисекунды)

N	Bubble	Insert	Select
200	2	1	1
500	4	4	3
700	4	6	4
1000	6	4	4
5000	65	32	53
10000	243	122	223
15000	549	236	442
20000	964	465	851
25000	1538	717	1219
50000	5996	2901	5367

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

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

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

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

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

По результатам работы программы на масивах различного объема построены графики (рис. 1, рис. 2).

Алгоритм Bubble sort эффективен лишь на небольших массивах. По общим результатам, он оказался самым худшим. Но, тем не менее, этот способ лежит в основе некоторых более совершенных алгоритмов, таких как сортировка Шелла (Shell sort) и быстрая сортировка (Quick sort).

Рис. 1. Функция временной сложности на малых объемах массивов (N)

Рис. 2. Функция временной сложности на больших объемах массивов (N)

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

Алгоритм сортировки вставками (Insertion sort) – это устойчивый алгоритм, эффективен на небольших наборах данных. Оказывается быстрым именно для небольших наборов. Также, для него важно, насколько упорядочен массив первоначально – эффективен на наборах данных, которые уже частично отсортированы, можно применять, например, на статичном массиве, в который изредка вставляются элементы; В отличие от других методов, сортировка вставками не использует обмены.

Мы сравнивали алгоритмы сортировки, испытав их на массивах, упорядоченных, обратно упорядоченных и случайных. Среди всех алгоритмов порядка O(n2) время сортировки вставками отражает тот факт, что на i-м проходе требуется лишь i/2 сравнений. Этот алгоритм явно превосходит все прочие сортировки порядка O(n2). Самую худшую общую производительность демонстрирует сортировка методом пузырька.

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

Библиографический список

лгоритмы и структуры данных. – М.: Мир,1989. ейтел П. Как программировать на С++. – М.: .Мир, 2000. Методы внутренней сортировки массивов: учеб. пособие к лабораторным работам. – Челябинск: Изд-во ЮУрГУ, 2006.

1 ,  студентка факультета кибернетики, , e-mail: *****@***edu

Tomskikh Olga, a student of Cybernetics Faculty, tel.: 40-51-63, e-mail: *****@***edu

2 , кандидат экономических наук, доцент кафедры вычислительной техники, e-mail: *****@***ru

Gorokhov Anatoliy, Candidate of Economics, Associate Professor of Computer Science Department, e-mail: *****@***ru