Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Классификация методов сортировки.






Пусть задано некоторое множество элементов а1, а2, а3,..., аn и требуется выстроить эти элементы по порядку в соответствии с заданной функцией предпочтения (например, по алфавиту). Очень часто значения функции предпочтения явно хранятся в исходных элементах в виде специального ключевого поля целого или строкового типа.

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

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

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

Методы сортировки массивов можно разделить на две большие группы:

· Универсальные методы, не требующие никакой дополнительной информации об исходных данных и выполняющие сортировку “на месте”, т.е. без использования больших объемов дополнительной памяти (например – для размещения копии исходного массива); такие методы в лучшем случае дают оценку трудоемкости порядка O(n*log 2 n);

· Специальные методы, которые либо за счет некоторой дополнительной информации об исходных данных, либо за счет использования большой дополнительной памяти позволяют получить более высокую производительность сортировки порядка O(n) (примеры – карманная и поразрядная сортировка);

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

· Простейшие методы с трудоемкостью порядка O(n2): сортировка обменом, сортировка выбором и сортировка вставками;

· Улучшенные методы с трудоемкостью O(n*log 2 n): метод Шелла, пирамидальная сортировка, быстрая сортировка;

Общая классификация методов сортировки приведена на рисунке 1.1.


 


 

 

Рис.1.1. Общая классификация методов сортировки.

 

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


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал