Метод - вставка
Cтраница 4
Дать пример файла из 10 элементов ( использовать ключи от А до J), в процессе сортировки которого пузырьковая сортировка выполняет меньше операций сравнения, чем метод вставок, либо же доказать, что такой файл не существует. [46]
Основными операторами, используемыми в такой процедуре упорядочения, оказываются: на первом этапе - оператор обмена, выполняющий сравнения пар элементов с устранением выявленных при сравнении инверсий, а на последующих этапах - оператор упорядочения отдельных последовательностей методом вставки. [47]
В этой таблице представлена откос и тельная стоимость нескольких различный вариантов быстрой сортиро & ки на примере упорядочения первых N слов из книги Мооу Dick, Непосредственное использование метода астаеки для сортировки небольших поцфайлов или игнорирование небольших подфэйлов с последующей сортировкой того же файла методом вставки потом - - суть стратегии обеспечивающие один и тот же уровень эффекта внесли, но а то же spews экономия раскодаег достигаемая за счет реализации обои стратегий несколько ниже, чем для целочисленных ключей ( см. гзбл. Если во время разбиения фзйлйн присмотр не останавливается нэ дуб-линованных ключах, то время сортировки файла, у которого все ключи одинаковы, подчиняется квадратичной зависимости; ниэкзя эффектипнпсть прой & лнбтся в этом пример. По той же причине разделение на три части обеспечивает & ы-сокий урое & нь эффекти. [48]
Для случая, когда число разрядов у признака велико, а число элементов сравнительно мало, так что п Cj2z, разумно проводить разделение не для всех разрядов признака, а только для некоторой группы старших разрядов, устраняя оставшуюся неупорядоченность отдельных небольших групп элементов методом вставки практически за один просмотр массива. Оценим характеристики процедуры в этом случае. [49]
 |
Эмпирическое исследование вариантов быстрой сортировки. [50] |
В этой таблице представлена относительная стоимость нескольких различных вариантов быстрой сортировки на примере упорядочения первых N слов из книги Moby Dick. Непосредственное использование метода вставки для сортировки небольших подфайлов или игнорирование небольших подфайлов с последующей сортировкой того же файла методом вставки потом - суть стратегии, обеспечивающие один и тот же уровень эффективности, но в то же время экономия расходов, достигаемая за счет реализации обоих стратегий несколько ниже, чем для целочисленных ключей ( см. табл. 7.1), поскольку стоимость операции сравнения строк влечет большие издержки. Есяи во время разбиения файлов просмотр не останавливается на дублированных ключах, то время сортировки файла, у которого все ключи одинаковы, подчиняется квадратичной зависимости; низкая эффективность проявляется в этом примере в связи с тем, что существует множество слов, которые встречаются в данных довольно часто. По той же причине разделение на три части обеспечивает высокий уровень эффективности сортировки; она на 30 - 35 процентов быстрее системной сортировки. [51]
 |
Ножной гидравлический спредер. [52] |
Заделка места повреждения после вырезки, шерохования, промазки клеем и сушки заключается в заполнении его починочными материалами и усилении ослабленного вырезкой места в покрышке пластырем или манжетой. Повреждение заделывают методом наложения или методом вставок. Предварительно всю поверхность вырезки обкладывают более тонкой прослоечной резиной ( 0 7 - 0 9 мм) для обеспечения лучшей связи починочных материалов с покрышкой. С внутренней стороны покрышки накладывают пластырь или манжету с числом слоев корда, равным числу поврежденных слоев каркаса. [53]
В разделе 13.2 рассматривается расширенное дерево - вариант BST-дерева, которое можно использовать для обеспечения таких гарантий при реализации таблиц символов. Этот алгоритм - вполне очевидное расширение метода вставок в корень, рассмотренного в главе 12, но аналитическое обоснование предельных значений производительности является достаточно сложным. [54]
В этом разделе исследуются способы модификации метода вставки в корень, чтобы ротации также в определенном смысле балансировали дерево. [55]
Применение в управляющих ЦВМ односторонних долговременных запоминающих устройств с прошивкой сердечников или внешней электрической записью информации существенно затрудняет значительное изменение программ и делает не рентабельной их полную перетрансляцию. В этом случае основным методом корректировки программ становится метод вставок и только после накопления 10 - 20 ошибок ( на программу объемом в 500 - 1000 команд), исправляемых вставками, может оказаться целесообразной полная перетрансляция программы. Техническая сложность корректировки программ в управляющих ЦВМ с односторонней памятью является одной из причин, делающих целесообразным проведение этапа автономной отладки на универсальной ЦВМ с использованием интерпретирующих программ. [56]
Как обычно, основной характеристикой алгоритма сортировки, вызывающей наибольший интерес, является время, затрачиваемое на его выполнение. Для выполнения сортировки N элементов методом выбора, методом вставок и пузырьковым методом, которые будут рассматриваться в разделах 6.2 - 6.4, требуется время, пропорциональное N2, как показано в разделе 6.5. Более совершенные методы, которые исследуются в главах 7 - 10, могут выполнить сортировку vV элементов за время, пропорциональное jVlogvV, однако эти методы не всегда столь же эффективны, как рассматриваемые здесь методы применительно к небольшим значениям N, a также в некоторых особых случаях. [57]
Этот метод значительно менее эффективен по сравнению с сортировкой методом вставок ( S. [58]
Страницы: 1 2 3 4