Методы программирования. Громов Ю.Ю - 60 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

60
в) поиска нужной информации в листинге (напечатанном машиной
документе). Поиск будет гораздо удобнее, если листинг будет отсортиро-
ван в алфавитном порядке.
Методы сортировки могут служить хорошей иллюстрацией идей
анализа алгоритмов, позволяющих оценивать рабочие характеристики
алгоритмов и разумно выбирать один среди, казалось бы, равноценных
алгоритмов.
Введём некоторые понятия и определим задачу сортировки.
Пусть необходимо упорядочить N элементов R
1
, R
2
, …, R
N
. Назовём
эти элементы записями, а совокупность N записей – файлом. Каждая за-
пись R
j
имеет, кроме всего прочего, ключ K
j
, который и управляет про-
цессом сортировки.
Задача сортировки заключается в том, чтобы найти такую переста-
новку p(1) p(2) … p(N) записей, в которой ключи расположились бы в
неубывающем порядке:
K
p(1)
≤ K
p(2)
≤ … ≤ K
p(N)
. (44)
Сортировка называется устойчивой, если она удовлетворяет допол-
нительному условию, что записи с одинаковыми ключами остаются в
прежнем порядке:
p(i) < p(j), если K
p(i)
=
K
p(j)
и i < j. (45)
В ряде случаев при сортировке может потребоваться физически пе-
ремещать записи в памяти; в других случаях достаточно создать вспомо-
гательную таблицу, которая некоторым образом описывает перестановку
и обеспечивает доступ к записям в соответствии с порядком их ключей.
Некоторые методы сортировки предполагают существование вели-
чин «∞» и «–
∞». Величина «∞» считается большей, а величина «–
∞»
меньшей любого ключа:
– ∞ < K
j
< ∞, j = 1, 2, …, N. (46)
Обычно сортировку подразделяют на два класса: внутреннюю, когда
все записи хранятся в оперативной памяти, и внешнюю, когда все они там
не помещаются. При внутренней сортировке имеются более гибкие воз-
можности для построения структур данных и доступа к ним. Внешняя
сортировка показывает, как поступать в условиях сильно ограниченного
доступа к данным.
Достаточно хороший общий алгоритм затрачивает на сортировку
N записей время порядка N logN, при этом требуется около logN «прохо-
дов» по данным.
Возможны следующие основные решения задачи внутренней сорти-
ровки:

Страницы