Студопедия  
Главная страница | Контакты | Случайная страница

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

Алгоритмы внутренней сортировки

Читайте также:
  1. CТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ
  2. Алгоритмы замещения страниц
  3. Алгоритмы и их свойства. Представление алгоритмов
  4. Алгоритмы и их свойства. Представление алгоритмов
  5. Алгоритмы поиска и индексации
  6. Алгоритмы сортировки в Delphi
  7. Алгоритмы шифрования
  8. Альтернативные подходы к определению факторов внутренней среды
  9. Анализ внутренней среды на основе ключевых внутренних факторов

Под сортировкой понимают процесс перестановки объектов множества в определенном порядке (в частности, множества чисел – по возрастанию или убыванию). Упорядоченное расположение фамилий в телефонной книге, товаров на полках, числовых данных даёт человеку гармоничное представление о множестве объектов. При этом удобство восприятия сочетается с возможностью быстрого поиска и выбора нужного экземпляра. На отсортированных данных легче определить, имеются ли пропущенные элементы, и удостовериться, что все элементы были проверены. Легче найти общие элементы или отличия двух множеств, если они оба отсортированы.

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

Среди алгоритмов внутренней сортировки можно выделить три элементарных, называемых также прямыми: сортировка выбором; сортировка вставкой; сортировка обменом (пузырьковая).

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

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

Существуют более быстрые алгоритмы, имеющие сложность N log2 N. Однако на небольших файлах разница не заметна. К тому же быстрые алгоритмы не отличаются стабильностью. Метод сортировки называется стабильным если он сохраняет относительный порядок следования записей с одинаковыми ключами. Например, если алфавитный список группы сортируется по оценкам, то стабильный метод создает список, в котором фамилии студентов с одинаковыми оценками будут упорядочены по алфавиту, а нестабильный метод создаст список в котором, возможно, исходный порядок будет нарушен.




Дата добавления: 2014-12-20; просмотров: 122 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.012 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав