Студопедия

КАТЕГОРИИ:

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


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




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

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

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

Как было замечено ранее, в некоторых программах сортировки лучше использовать простые алгоритмы. Программы сортировки часто используются только один раз (или несколько раз). Если количество элементов которые нужно отсортировать не велико (скажем меньше чем 500 элементов), то возможно, что использование простого алгоритма будет более эффективно, чем разработка и отладка сложного алгоритма. Элементарные методы всегда пригодны для маленьких файлов (скажем меньших чем 50 элементов); маловероятно, что сложный алгоритм было бы разумно использовать для таких файлов, если конечно не нужно сортировать большое количество таких файлов.

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

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

Под сортировкой понимают, процесс перестановки объектов множества в определенном порядке.

Целью алгоритма сортировки является переорганизация записей в файле так, чтобы они располагались в нем в каком-либо строго определенном порядке (обычно в алфавитном или числовом).

Пусть на дана последовательность элементов: a1, a2, ..., an сортировка означает - перестановку этих элементов в таком порядке: ak1,ak2, .. ,akn, что при заданной функции упорядочивания f(x), справедливо отношение :

f(ak1) <= f(ak2)<= .. <= f(akn) - функция упорядочивания не вычисляется, а содержится в каждом элементе в виде явной компоненты и ее значение называют ключом элемента. Следовательно, для представления i-ого элемента последовательности наилучшим образом подходит структура записи. Определим тип элемента, который будем использовать в алгоритмах сортировки следующим образом :

type elem = Record

key: integer;

описание др. компонентов

end;

Поле key - служит только для идентификации элемента.

Как здесь видно ключи являются только частью записи (часто очень маленькой их частью), используются для управления процессом сортировки.

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

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

Обычно, главное, что будет нас интересовать в алгоритме - это время его работы. Время работы алгоритма характеризуется числом необходимых сравнений обозначаемых через С и число м необходимых пересылок элемента - M.

Простые алгоритмы, которые мы рассмотрим, для сортировки N элементов имеют время работы пропорциональное N2, в то время как более сложные алгоритмы используют время пропорциональное NlogN. (Можно доказать, что никакой алгоритм сортировки не может использовать менее, чем N logN сравнений между ключами.)

Количество используемой дополнительной памяти алгоритма сортировки - это еще один важный фактор, который мы будем принимать во внимание. Вообще говоря, методы сортировки делятся на три типа(по времени):

- методы сортировки которые сортируют без использования дополнительной памяти, за исключением, возможно, небольшого стека и/или массива;

- методы которые используют для сортировки связанные списки и поэтому используют N дополнительных указателей хранящихся в памяти;

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

 

Сортировка- упорядочивание элементов массива (списка) по возрастанию либо убыванию по заданному ключевому полю.

Сортировка вставками сортирует список, вставляя очередной элемент в нужное место уже отсортированного списка. Пузырьковая сорти­ровка сравнивает элементы попарно, переставляя между собой элемен­ты тех пар, порядок в которых нарушен. Сортировка Шелла предста­вляет собой многопроходную сортировку, при которой список разби­вается на подсписки, каждый из которых сортируется отдельно, при­чем на каждом проходе число подсписков уменьшается, а их длина ра­стет. При корневой сортировке список разбивается на стопки, и при каждом проходе используется отдельная часть ключа. Пирамидаль­ная сортировка строит бинарное дерево, значение каждого узла в кото­ром превышает значение потомков. В результате наибольший элемент списка помещается в корень, и при его удалении и выборе очередной пирамиды в корне оказывается следующий по величине элемент. Этот процесс повторяется пока все элементы не окажутся в новом, уже от­сортированном, списке. Быстрая сортировка представляет собой рекурсивный алгоритм, кото­рый выбирает в списке осевой элемент, а затем разбивает список на две части, состоящие из элементов соответственно меньших или боль­ших выбранного.


Поделиться:

Дата добавления: 2015-04-18; просмотров: 85; Мы поможем в написании вашей работы!; Нарушение авторских прав





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