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

UptoLike

ВУЗ: 

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

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

Рубрика: 

118
производится анализ факторов, влияющих на эффективность сортировки, после
чего выбранные или разработанные методы испытываются на тестовых приме-
рах с одновременным сравнительным расчетом их эффективности.
Основными факторами, которые следует учитывать при выборе и оцен-
ке того или иного метода сортировки, являются: размер сортируемого массива;
длина ключа; вид ключа; исходное распределение данных;
возможность дубли-
рования ключей; длина записей.
Размер сортируемого массива, прежде всего, позволяет ус-
тановить, требуется ли внешняя сортировка, т.е. достаточен ли свободный объ-
ем оперативной памяти для осуществления внутренней сортировки. При этом
выясняется также необходимость применения методов сортировки, в которых
используются минимальные объемы памяти.
Длина ключа и место его расположения
в пределах записи опреде-
ляют время, необходимое для выполнения операции сравнения. При этом сле-
дует выяснить, является ли ключ полем записи, к которому возможен доступ,
или необходимы дополнительные меры, позволяющие извлечь ключ из записи,
например «маскирование». В последнем случае необходимо оценить время,
требуемое на извлечение ключа из записи.
Важным является
также соответствие ключа структуре данных ЭВМ и
наличие возможной зависимости времени выполнения операции сравнения на
данной ЭВМ от числа символов в ключе. При наличии такой зависимости мо-
жет оказаться целесообразной предварительная обработка ключа для представ-
ления его в более удобной для выполнения операции сравнения форме.
Вид ключа. Время сравнения зависит от
внутреннего представле-
ния данных в ЭВМ и от доступности команд сравнения для различных типов
данных. Например, при отсутствии в конкретной ЭВМ команд сравнения деся-
тичных чисел может потребоваться предварительное преобразование ключа в
двоичный код. Время сортировки при этом увеличивается на время преобразо-
вания ключей.
Исходное распределение данных. В большинстве случаев
распределение ключей записей исходной последовательности является случай-
ным. Однако возможно, что процедура сбора данных уже обеспечивает частич-
ное их упорядочение. Если можно выявить устойчивые закономерности в ис-
ходном распределении записей, то это позволяет выбрать метод сортировки,
обеспечивающий минимальное число сравнений при данном конкретном по-
рядке распределения ключей в исходной последовательности.
Возможность
дублирования ключей. В некоторых при-
ложениях необходимо распознавание повторяющихся ключей. В таких случаях
алгоритм сортировки, кроме операций сравнения ключей по принципу «больше-
меньше», должен предусматривать проверку на их равенство. Когда повторения
распознавать не надо, важно предотвратить обмены при равенствах.
Длина записей совместно с их количеством позволяет оценить
необходимый для сортировки
объем оперативной памяти. При сортировке запи-

Страницы