Анализ эффективности алгоритмов сортировки и вcтроенных реализаций на примере языка программирования Java | Статья в журнале «Молодой ученый»

Автор:

Рубрика: Информатика

Опубликовано в Молодой учёный №21 (155) май 2017 г.

Дата публикации: 29.05.2017

Статья просмотрена: 356 раз

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

Рыжов С. С. Анализ эффективности алгоритмов сортировки и вcтроенных реализаций на примере языка программирования Java // Молодой ученый. — 2017. — №21. — С. 26-29. — URL https://moluch.ru/archive/155/43911/ (дата обращения: 18.02.2019).



В данной статье показана значительная роль проведения анализа работы алгоритмов сортировки на массивах данных различной размерности. Рассмотрены актуальные алгоритмы и стандартные реализации сортировки в языке программирования 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 с.

Основные термины (генерируются автоматически): массив данных, исходный код сортировки, сортировка выбором, сортировка вставками, программное обеспечение, алгоритм, время выполнения сортировки, алгоритм сортировки, элемент, левая сторона.


Похожие статьи

Сравнительный анализ алгоритмов сортировки данных...

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

Эволюция способов и алгоритмов сортировки данных в массивах

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

Параллельные методы сортировки | Статья в журнале...

Еще одним методом сортировки является сортировка Шелла. Данный алгоритм является очень эффективным и быстрым, и его время сортировки при использовании последовательного метода измеряется как

Эволюция способов и алгоритмов сортировки данных в массивах.

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

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

– наглядность представления исходных данных и основных результатов моделирования.

Использование алгоритмов нечеткого поиска при решении задачи...

Author described the algorithm of duplicate records elimination under condition of several data sources and errors of operator input.

Эволюция способов и алгоритмов сортировки данных в массивах.

Анализ поисковых алгоритмов при решении задач идентификации...

Сравнительный анализ алгоритмов сортировки данных в массивах.

Обеспечение защиты данных в базах данных. Влияние параметров поисковых алгоритмов компенсации движения на показатели качества современных видеокодеков.

MapReduce и метод доступа к хранилищу MRIJ on RCFile

MapReduce – это алгоритм, доступа к неструктурированным данным. Первым шагом этого алгоритма является выполнение функции Map ко всем элементам исходной коллекции.

На втором шаге происходит сортировка всех экземпляров и создание новых, где все значения...

Реализация алгоритма поиска ближайших объектов с помощью...

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

Используется разбиение исходного множества точек по широте/долготе.

Алгоритм можно усовершенствовать, если хранить в узле массив значений.

Сравнительный анализ алгоритмов сортировки данных...

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

Эволюция способов и алгоритмов сортировки данных в массивах

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

Параллельные методы сортировки | Статья в журнале...

Еще одним методом сортировки является сортировка Шелла. Данный алгоритм является очень эффективным и быстрым, и его время сортировки при использовании последовательного метода измеряется как

Эволюция способов и алгоритмов сортировки данных в массивах.

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

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

– наглядность представления исходных данных и основных результатов моделирования.

Использование алгоритмов нечеткого поиска при решении задачи...

Author described the algorithm of duplicate records elimination under condition of several data sources and errors of operator input.

Эволюция способов и алгоритмов сортировки данных в массивах.

Анализ поисковых алгоритмов при решении задач идентификации...

Сравнительный анализ алгоритмов сортировки данных в массивах.

Обеспечение защиты данных в базах данных. Влияние параметров поисковых алгоритмов компенсации движения на показатели качества современных видеокодеков.

MapReduce и метод доступа к хранилищу MRIJ on RCFile

MapReduce – это алгоритм, доступа к неструктурированным данным. Первым шагом этого алгоритма является выполнение функции Map ко всем элементам исходной коллекции.

На втором шаге происходит сортировка всех экземпляров и создание новых, где все значения...

Реализация алгоритма поиска ближайших объектов с помощью...

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

Используется разбиение исходного множества точек по широте/долготе.

Алгоритм можно усовершенствовать, если хранить в узле массив значений.

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Сравнительный анализ алгоритмов сортировки данных...

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

Эволюция способов и алгоритмов сортировки данных в массивах

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

Параллельные методы сортировки | Статья в журнале...

Еще одним методом сортировки является сортировка Шелла. Данный алгоритм является очень эффективным и быстрым, и его время сортировки при использовании последовательного метода измеряется как

Эволюция способов и алгоритмов сортировки данных в массивах.

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

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

– наглядность представления исходных данных и основных результатов моделирования.

Использование алгоритмов нечеткого поиска при решении задачи...

Author described the algorithm of duplicate records elimination under condition of several data sources and errors of operator input.

Эволюция способов и алгоритмов сортировки данных в массивах.

Анализ поисковых алгоритмов при решении задач идентификации...

Сравнительный анализ алгоритмов сортировки данных в массивах.

Обеспечение защиты данных в базах данных. Влияние параметров поисковых алгоритмов компенсации движения на показатели качества современных видеокодеков.

MapReduce и метод доступа к хранилищу MRIJ on RCFile

MapReduce – это алгоритм, доступа к неструктурированным данным. Первым шагом этого алгоритма является выполнение функции Map ко всем элементам исходной коллекции.

На втором шаге происходит сортировка всех экземпляров и создание новых, где все значения...

Реализация алгоритма поиска ближайших объектов с помощью...

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

Используется разбиение исходного множества точек по широте/долготе.

Алгоритм можно усовершенствовать, если хранить в узле массив значений.

Сравнительный анализ алгоритмов сортировки данных...

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

Эволюция способов и алгоритмов сортировки данных в массивах

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

Параллельные методы сортировки | Статья в журнале...

Еще одним методом сортировки является сортировка Шелла. Данный алгоритм является очень эффективным и быстрым, и его время сортировки при использовании последовательного метода измеряется как

Эволюция способов и алгоритмов сортировки данных в массивах.

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

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

– наглядность представления исходных данных и основных результатов моделирования.

Использование алгоритмов нечеткого поиска при решении задачи...

Author described the algorithm of duplicate records elimination under condition of several data sources and errors of operator input.

Эволюция способов и алгоритмов сортировки данных в массивах.

Анализ поисковых алгоритмов при решении задач идентификации...

Сравнительный анализ алгоритмов сортировки данных в массивах.

Обеспечение защиты данных в базах данных. Влияние параметров поисковых алгоритмов компенсации движения на показатели качества современных видеокодеков.

MapReduce и метод доступа к хранилищу MRIJ on RCFile

MapReduce – это алгоритм, доступа к неструктурированным данным. Первым шагом этого алгоритма является выполнение функции Map ко всем элементам исходной коллекции.

На втором шаге происходит сортировка всех экземпляров и создание новых, где все значения...

Реализация алгоритма поиска ближайших объектов с помощью...

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

Используется разбиение исходного множества точек по широте/долготе.

Алгоритм можно усовершенствовать, если хранить в узле массив значений.

Задать вопрос