Введение в информационные системы. Брюхомицкий Ю.А. - 109 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

109
В процессе сортировки логический порядок следования значений клю-
чей не всегда может соответствовать физическому порядку их размещения в
памяти. В ряде случаев создают вспомогательную таблицу, обеспечивающую
доступ к записям в соответствии со значениями их ключей.
В ключевом поле могут храниться числовые или символьные данные. В
зависимости от характера ключей записи
сортируются либо численным, либо
алфавитно-цифровым способом. В первом случае записи упорядочиваются в
возрастающем или убывающем порядке числовых значений ключа. Во втором
случае при сортировке сравниваются строки символов, и устанавливается лек-
сико-графический порядок следования записей массива. При сравнении симво-
лов сопоставляются двоичные коды их машинного представления. Большим
считается символ, имеющий
больший код.
Сравнение строк символов осуществляется в соответствии с определен-
ными правилами. Пусть сравниваются две строки символов русского алфавита:
X
1
X
2
...X
m
и Y
1
Y
2
...Y
n
, где X
i
и Y
i
− символы, каждому из которых соот-
ветствует определенный двоичный код. Строка X
1
X
2
...X
m
будет считаться мень-
ше строки Y
1
Y
2
...Y
n
в следующих случаях:
1) если первая строка короче второй и все ее символы являются частью
второй, т.е. mn, а X
1
X
2
...X
m
= Y
1
Y
2
...Y
m
(например, СТОЛ <СТОЛЕШНИЦА;
МЕТОДМЕТОДИКА; НОТАНОТАРИУС);
2) если очередной символ первой строки меньше соответствующего
символа второй строки, т.е. для некоторого i ≤min (m, n) при X
1
= Y
1
, X
2
= Y
2
, . . .
, X
i-1
= Y
i-1
окажется X
i
Y
i
(например, УЧЕБНИКУЧЕНЫЙ; СТИПЕНДИЯ
СТУДЕНТ; СТАРТФИНАЛ).
В общем случае при сортировке строк символов вначале осуществляет-
ся сортировка по первому символу, затем по второму и т.д.
Иногда бывает удобно, чтобы информационный массив упорядочивался
не единственным способом. Подобная ситуация возникает, если различные при-
ложения используют в качестве ключа различные поля
записей массива. Сорти-
ровка основного массива по нужному для данного приложения ключу может
осуществляться каждый раз непосредственно перед началом обработки данных.
По окончании обработки отсортированный массив уничтожается. Время сорти-
ровки в этом случае входит в общее время обработки данных.
В ряде случаев копии массива или файла, упорядоченные по различным
ключам,
постоянно хранятся в памяти ЭВМ. Такие массивы называются инвер-
тированными. Дополнительный расход памяти при этом часто окупается уско-
рением процесса обработки.
В зависимости от состава технических средств, используемых в процес-
се сортировки, различают внутреннюю и внешнюю сортировки. Сортировка
внутренняя, если весь упорядоченный массив целиком размещается в опе-
ративной памяти и находится
там в течение всего процесса сортировки. Сорти-
ровка внешняя, если она производится в массивах данных, объем которых
превышает свободный объем оперативной памяти. В этом случае исходный и

Страницы