Файл: Алгоритмы сортировки данных (Типы и структуры данных).pdf

Таблица 4.8.1 Сравнительные показатели производительности различных методов сортировки массивов

Из приведенных в таблице данных следует, в частности, для относительно небольшого массива в 512 элементов:

Худшая по производительности из простых сортировок (сортировка обменом) работает в 35 раз медленнее быстрой сортировки Хоара.

Самая быстрая из простых сортировок (простая сортировка вставками) работает медленнее в 4.2 раза чем худшая по производительности из сложных сортировок (сортировка Шелла).

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

4.9. Теоретическое сравнение сортировок методом простых вставок и методом пузырька

Сделаем теоретическое сравнение сортировок методом простых вставок и методом пузырька. Основным критерием сравнения сортировок является их эффективность, то есть число сравнений и число пересылок. Данные показатели также влияют на время сортировки. Укажем основные формулы, использующиеся для вычисления эффективности данных сортировок:

- число сравнений ключей элементов при i-ом просеивании;

- минимальное число сравнений ключей;

- максимальное число сравнений ключей;

- среднее число сравнений ключей;

- число пересылок (присваиваний) элементов при i-ом просеивании;

- минимальное число пересылок

- максимальное число пересылок

- среднее число пересылок

- размер массива;

Рассмотрим сортировку методом простых вставок

Рассмотрим сортировку методом пузырька

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

Таблица 4.9.1 Сравнительный анализ сортировок методом простых вставок и методом пузырька

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

Рисунок. 4.9.1

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

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

Рисунок. 4.9.2

Графики числа пересылок в сортировках: число пересылок П - для метода пузырька, число пересылок В - для метода простых вставок.

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

Ссылаясь на таблицу 1 можно также отметить, что сортировка методом пузырька требует больше времени, чем сортировка методом вставок.

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

Заключение

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

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

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

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

Список литературы

1. Д. Кнут. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М., "Мир", 1976 г., переиздание - М., Изд-во "Вильямс", 2000 - 720с.
2. Д. Кнут, Искусство программирования для ЭВМ. Т.3. Сортировка и поиск. - М., "Мир", 1978 г., переиздание - М., Изд-во "Вильямс", 2000. - 832с.
3. Н. Вирт, Алгоритмы и структуры данных. - М., Издат-во "Вильямс", 1998 - 360с.
4. Гагарина Л.Г., Колдаев В.Д., Алгоритмы и структуры данных. - М.: Финансы и статистика; ИНФРА-М, 2009. - 304с.
5. Алгоритмы сортировки - Википедия. http://ru.wikipedia.org/wiki/