Алгоритм - сортировка
Cтраница 4
К счастью, алгоритм жор-дановой сортировки в качестве побочного эффекта вычисляет достаточно много дополнительной информации, облегчающей выполнение шага 4 приведенного выше алгоритма. Шаг 2 является наиболее трудной частью алгоритма. В алгоритме имеются два узких места, непродуманная реализация каждого из которых приведет к тому, что алгоритм будет иметь квадратичную временную сложность. Во-первых, в ряде случаев алгоритм будет многократно порождать некоторые пары видимости. Действительно, для многоугольника, показанного на рис. 4, алгоритм может найти Q ( n2) повторяющихся пар видимости. [46]
Повышение эффективности некоторых алгоритмов сортировки достигается за счет использования специфических свойств ключей. [47]
Изложенный выше вариант алгоритма сортировки является сильным упрощением алгоритмов сортировки, реализованных на ЭВМ. Поскольку сортировка поглощает много машинного времени, авторы программ сортировки ищут разные, подчас довольно сложные пути для ускорения сортировки. Язык КОБОЛ дает программисту возможность довольно просто управлять процессом сортировки независимо от фактического алгоритма реализации сортировки на ЭВМ. [48]
Как и большинство алгоритмов сортировки, быстрая сортировка имеет много вариантов. Здесь можно лишь рассмотреть некоторые из них; в библиографической справке в конце главы указаны другие. [49]
 |
Сортировка посредством простого выбора. [50] |
В отличие от алгоритма сортировки простыми вставками, в этом алгоритме операция сравнения обязательно производится ( п - 1) я / 2 раз. При этом необходима операция вывода наименьших значений с каждого из рассматриваемых участков. Число операций вывода в наихудшем случае составляет п2 / 4, среднее число равно nlogn. Если сравнивать свойства этого алгоритма со свойствами алгоритма сортировки простыми вставками, то оказывается, что в случае сортировки простым выбором число сравнений больше, а число перемещений меньше. [51]
Иногда при применении алгоритма сортировки нас интересует, что происходит, если в сортируемом списке встречаются дубликаты ключей. Это важно в случае, когда происходит сортировка длинных записей по набору полей и хочется сохранить результаты уже выполненной сортировки. Пусть, например, фамилия и имя человека составляют два отдельных поля записи. [52]
Однако для многих алгоритмов сортировки число сравнений является хорошей мерой производимой работы, и вследствие этого представляет интерес минимальное число сравнений, требующееся для сортировки п имен. [53]
Оценим общую сложность алгоритма сортировки данных рассматриваемым методом. Процедура SURFACE всплытия Флойда выполняется п раз сначала для формирования исходного почти упорядоченного дерева ( процедура применяется для каждой вершины дерева) и затем п раз для всплытия каждого наибольшего ( наименьшего) элемента в почти упорядоченном дереве. [54]
Сортировка вставкой является алгоритмом сортировки, который из входного списка порождает отсортированный путем повторной вставки элементов исходного списка на правильные позиции в частично отсортированный список. [55]
Страницы: 1 2 3 4