Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования (Методы сортировки массивов).pdf

Заключение

Основное требование к методам сортировки массивов – экономное использование памяти. Это означает, что переупорядочение элементов нужно выполнять in situ (на том же месте) и что методы, которые пересылают элементы из массива a в массив b, не представляет для нас интереса. Таким образом, выбирая метод сортировки, руководствуясь критерием экономии памяти, классификацию алгоритмов мы проводим в соответствии с их эффективностью, т. е. экономией времени или быстродействием.

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

Можно показать, что среднее расстояние, на которое должен переместиться каждый из n элементов во время сортировки, - это n/3 мест. Это число дает ключ к поиску усовершенствованных, т. е. более эффективных, методов сортировки. Все простые методы в принципе перемещают каждый элемент на одну позицию на каждом элементарном шаге. Поэтому они требуют порядка таких шагов. Любое улучшение должно основываться на принципе пересылки элементов за один цикл на большее расстояние.

Рассмотрев усовершенствованные методы сортировки срав­ним их эффективность. Как и раньше, n — число сортируемых элементов, а С и М — соответственно число необходимых сравне­ний ключей и число обменов. Для всех прямых методов сорти­ровки можно дать точные аналитические формулы. Для усовершенствованных методов нет сколько-либо осмыслен­ных, простых и точных формул. Существенно, однако, что в слу­чае сортировки Шелла вычислительные затраты составляют с×n^1.2, а для пирамидальной сортировки и метода быстрой сортировки — с×n×logn, где с — соответствую­щие коэффициенты.

Эти формулы просто вводят грубую меру для производитель­ности как функции n и позволяют разбить методы сортиров­ки на примитивные, прямые методы (n²) и на усложненные или "логарифмические" методы (n×log(n)).

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

Итак, сделаем вывод: алгоритмы устойчивой сортировки - самые медленные алгоритмы сортировки, принадлежащие к классу О(n²), применяются при небольшом n. Алгоритмы неустойчивой сортировки – наиболее быстрые, принадлежащие к классу О(n×log(n)), применяются при большом n. Выбор определенного метода сортировки зависит от структуры обрабатываемых данных, а также от количества элементов. При решении определенной задачи, выбранный метод сортировки должен быть наиболее эффективным.

Список использованной литературы

1. Бакнелл Джулиан М. Книга: Фундаментальные алгоритмы и структуры данных в Delphi. [Текст] / Д.М. Бакнелл. Перевод с английского. - ООО "ДиаСофтЮП", 2003.- 560 с.
2. Вирт Н. Книга: Алгоритмы и структуры данных. [Текст] / Н.Вирт. Перевод с английского – М. Издательство «Мир», 1989. -358 с.
3. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. [Текст] = Алгоритмы: построение и анализ, 2-издание. / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Перевод с английского – М. Издательский дом «Вильямс», 2005. – 1296 с.
4. Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с.

1. Бакнелл Джулиан М. Книга: Фундаментальные алгоритмы и структуры данных в Delphi. [Текст] / Д.М. Бакнелл. Перевод с английского. - ООО "ДиаСофтЮП", 2003.- 560 с. ↑

2. Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с. ↑

3. ? Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с. ↑

4. Бакнелл Джулиан М. Книга: Фундаментальные алгоритмы и структуры данных в Delphi. [Текст] / Д.М. Бакнелл. Перевод с английского. - ООО "ДиаСофтЮП", 2003.- 560 с. ↑

5. ? Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с. ↑

6. ? Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с. ↑

7. ? Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с. ↑

8. Бакнелл Джулиан М. Книга: Фундаментальные алгоритмы и структуры данных в Delphi. [Текст] / Д.М. Бакнелл. Перевод с английского. - ООО "ДиаСофтЮП", 2003.- 560 с. ↑

9. Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. [Текст] : учебное пособие для студентов вузов / Л.Г. Гагарина, В.Д. Колдаев. - Издательство "Финансы и статистика"; Издательский дом ИНФРА-М, 2009. - 304 с. ↑