В данной статье показана значительная роль проведения анализа работы алгоритмов сортировки на массивах данных различной размерности. Рассмотрены актуальные алгоритмы и стандартные реализации сортировки в языке программирования Java.
Ключевые слова: алгоритмы, сортировка, анализ алгоритмов, программирование, java, сортировка вставками, сортировка выбором, сортировка Шелла
Использование правильно подобранных алгоритмов в современной разработке программного обеспечения жизненно важно для проекта, так как ошибочный выбор алгоритма для тривиальной, на первый взгляд, задачи может прямо сказаться на скорости выполнения реализованной функциональности. На текущей момент разработано множество библиотек, включающих в себя множество реализованных эффективных алгоритмов, которые могут быть использованы любым разработчиком программного обеспечения для достижения сравнительно высоких показателей скорости выполнения программы. Практика показывает, что зачастую разработчик полностью доверяется встроенным средствам и не анализирует в достаточной степени ситуацию, в которой будет применен выбранный алгоритм. К примеру, в языке программирования Java реализован встроенный класс java.util.Arrays, содержащий в себе множество методов, которые могут быть применены к массивам данных, включая метод sort(). В большинстве случаев использование стандартной реализации сортировки массивов данных будет достаточно для достижения высокой скорости исполнения программы. Как показано далее в этом исследовании, есть ряд исключений, при которых решения, использующие другие реализаций алгоритма сортировки, демонстрируют большую эффективность.
В теории алгоритмов существует множество вариантов реализации сортировки. Самые известные из них: пузырьковая (bubble sort), сортировка вставками (insertion sort), сортировка выбором (selection sort), сортировка Шелла (Shell sort).
Сортировка выбором — простой и очевидный способ упорядочить массив данных. Алгоритм, используемый в данной сортировке, содержит в себе следующий набор инструкций: осуществляется проход по всему массиву с первого элемента, на каждом проходе находится минимальный элемент в правой части массива от текущего элемента, далее текущий элемент меняется местами с минимальным. В результате, алгоритм формирует окончательный вариант массива в отсортированном по возрастанию виде. Анализ алгоритма показывает, что его сложность равна O(n^2), где n — количество элементов массива. Следовательно, при увеличении массива данных в два раза, время работы алгоритма возрастет в четыре раза. На рисунке 1 изображен исходный код сортировки выбором.
Рис. 1. Исходный код сортировки выбором
В таблице 1 приведен расчет времени, необходимый для успешного выполнения сортировки массивов данных различного объема, при использовании сортировки выбором.
Таблица 1
Время выполнения сортировки выбором (мс.)
|
|
Количество элементов |
|||||
|
10 |
100 |
1000 |
10000 |
100000 |
1000000 |
|
|
Время |
4250 |
46043 |
429651 |
29521459 |
2987591756 |
361000964856 |
Алгоритм работы сортировки вставками реализован несколько иным способом. Элементы, оставшиеся с левой стороны от текущего, всегда находятся в отсортированном виде, так как каждый следующий элемент исходного массива данных переходит в левую сторону массива до тех пор, пока на его пути не окажется меньший элемент. Среднестатистический случай использования данного алгоритма сортировки выполняется примерно в два раза быстрее по сравнению с сортировкой выбором. Оценка сложности алгоритмов обычно проводится исходя из наихудшего случая. Учитывая это, сложность алгоритма сортировки вставками определена как O(n^2), где n — количество элементов массива. [1] Таким образом, сложность данного алгоритма равна сложности алгоритма сортировки выбором. На рисунке 2 изображен исходный код сортировки вставками.
Рис. 2. Исходный код сортировки вставками
В таблице 2 приведен расчет времени, необходимый для успешного выполнения сортировки массивов данных различного объема, при использовании сортировки вставками.
Таблица 2
Время выполнения сортировки вставками (мс.)
|
|
Количество элементов |
|||||
|
10 |
100 |
1000 |
10000 |
100000 |
1000000 |
|
|
Время |
1506 |
35684 |
356987 |
33721654 |
4787521651 |
459054914459 |
Как показано в таблице 2 сортировка вставками выполняется в течение большего периода времени по сравнению с алгоритмом сортировки выбором на массивах данных, состоящих из более чем 10000 объектов и составленных из случайно подобранных значений. Однако, на массивах данных, состоящих из менее чем 10000 объектов, сортировка вставками демонстрирует более высокую скорость выполнения.
В 1959 году Дональд Шелл отметил, что в алгоритме вставками самым неэффективным этапом является перенос текущего объекта в левую сторону через множество других объектов. [3] Шелл предложил эффективный способ решения данной проблемы — последовательное применение так называемых частичных сортировок (h-sort). Используя указанный механизм, алгоритм формирует массив, который будет h-отсортирован, где h — значение, на которое каждый элемент может быть отклонен от своей целевой позиции в полностью отсортированном массиве данных. Таким образом, последовательно применяя частичную сортировку с уменьшающимся значением h, возможно отсортирвоать большой массив данных быстрее по сравнению с классическими алгоритмами сортировки. Однако, слабой стороной данного метода, является сложность выбора последовательности частичных сортировок. От правильности данного выбора, зависит конечная эффективность алгоритма. Распространенной практикой является последовательность, предложенная математиком и специалистом в области информатики Дональдом Кнутом: h = h * 3 + 1. [2] На рисунке 2 изображен исходный код сортировки Шелла.
Рис. 3. Исходный код сортировки Шелла
Как показано в таблице 3, разработанная Кнутом последовательность обеспечивает высокую эффективность и сравнительно проста в реализации на практике.
Таблица 3
Время выполнения сортировки Шелла (мс.)
|
|
Количество элементов |
|||||
|
10 |
100 |
1000 |
10000 |
100000 |
1000000 |
|
|
Время |
2315 |
31374 |
36987 |
1229052 |
14567826 |
242967519 |
Анализируя результаты исследования классических алгоритмов сортировки массивов данных, можно заметить, что при возрастании количества элементов в массиве, который необходимо отсортировать, с наилучшей стороны показывает себя алгоритм сортировки методом Шелла.
При разработке программного обеспечения важную роль играет правильность выбора алгоритмов решения поставленных задач. Разработчик высокого класса должен уметь анализировать данные, с которыми ему предстоит работать, и выберать не только самый распространенный алгоритм, реализованный в качестве стандартного втроенного инструмента в платформу, но и уметь оценивать уместность применения такого алгоритма.
Литература:
1. Дональд Эрвин Кнут, Искусство программирования. Том 1. Основные алгоритмы. — СПб.: Вильямс, 2015. — 720 с.
2. Роберт Седжвик, Кевин Уэйн, Алгоритмы на Java. — СПб.: Вильямс, 2016. — 848 с.
3. Томас Х. Кормен, Чарльз И. Лейзерсон, Алгоритмы. Построение и анализ. — СПб.: Вильямс, 2016. — 1328 с.
