Cтраница 2
В чем превосходит и в чем уступает сортировка всего файла методом вставок двум методами, представленными в упражнении 8.1. ( Ответьте на этот вопрос, полагая, что малый файл имеет произвольную организацию, так что каждая вставка проходит примерно полпути в большом файле, а время выполнения сортировки определяется выражением с3 MN / 2, при этом константа с3 - того же порядка, что и другие константы. [16]
Предположим, что используется сортировка вставками для упорядочения случайно распределенного файла, элементы которого принимают одно из трех возможных значений. Какой зависимости подчиняется время выполнения сортировки: линейной, квадратичной или некоторой промежуточной зависимости. [17]
При получении оценки времени выполнения сортировки целочисленных файлов rekt н ш иным истодом, часто предполагается, чтп стоимости опсраиий сравнении и оСмена приблизительно одно-то [ [ Орядка. [18]
Этот результат обобщается путем его применения к поразрядной сортировке MSD. Тем не менее, поскольку основной интерес для нас представляет время выполнения сортировки, а не символы просматриваемых ключей, мы должны проявлять осторожность, поскольку время выполнения поразрядной сортировки пропорционально величине основания системы счисления Л и не имеет ничего общего с ключами. [19]
Доказательство наличия этого свойства практически тривиально, в то же время оно играет весьма важную роль в нашем понимании поразрядной сортировки MSD. В частности, оно говорит нам, что мы не можем утверждать, что время выполнения сортировки будет меньше в силу того, что N мало, поскольку R может быть намного больше, чем N. Короче говоря, для сортировки файлов небольших размеров следует использовать другие методы. Этот вывод может служить решением проблемы пустых корзин, которую мы обсуждали в конце раздела 10.3. Например, если R равно 256, а N равно 2, то поразрядная сортировка MSD будет в 128 раз медленнее, чем более простой метод, предусматривающий только сравнение элементов. Рекурсивная структура поразрядной сортировки MSD приводит к тому, что соответствующая рекурсивная программа будет многократно вызывать себя для большого числа файлов небольших размеров. Поэтому в условиях рассматриваемого примера игнорирование проблемы пустых корзин может привести к тому, что вся поразрядная сортировка замедлится в 128 раз по сравнению с тем, какой она может быть. Что касается промежуточных ситуаций ( например, предположим, что R равно 256, а N равно 64), то стоимость не будет настолько катастрофичной, тем не менее весьма существенной. Использование сортировки вставками - не слишком удачный выбор, ибо стоимость N2 / 4 сравнений все еще недопустимо высока; не следует игнорировать проблему пустых корзин в силу того факта, что их очень много. Простейший путь решения этой проблемы состоит в использовании основания системы счисления, которая меньше размера сортируемого файла. [20]
Время выполнения каждого прохода зависит от того, насколько упорядочен файл к моменту начала прохода. После выполнения нескольких проходов все эти файлы будут упорядоченными одинаково; таким образом, время выполнения сортировки не очень чувствительно к виду входных данных. [21]
Каждый элемент перемещается дважды, один раз в процессе распределения и один раз при возвращении в исходный файл; ссылки на ключи также производятся дважды, один раз при подсчете, другой раз при выполнении распределения. Два других цикла for в алгоритме используются при накоплении показаний счетчиков и фактически мало влияют на время выполнения сортировки до тех пор, пока количество подсчетов существенно не превосходит размер файла. [22]
При дистрибутивной сортировке признак анализируется по частям и сортировка выполняется в несколько этапов, на каждом из которых анализируется одинаковая часть всех признаков. Объем части определяется резервом основной памяти, необходимым для дистрибутивной сортировки. Время выполнения дистрибутивной сортировки в отличие от компаративной более существенно зависит от суммарной длины признака. При небольшой длине признака дистрибутивные методы обладают более высокой производительностью по сравнению с компаративными. [23]
Но гарантированное время выполнения, пропорциональное NlogN, может обернуться недостатком. Например, в главе 6 мы видели, что существуют методы, которые могут быть адаптированы таким образом, что в некоторых особых ситуациях, например, когда уровень упорядоченности файла достаточно высок либо когда имеется всего лишь несколько различных ключей, время их выполнения линейно. В противоположность этому, время выполнения сортировки слиянием зависит главным образом от числа ключей входного файла и оно практически не чувствительно к их порядку. [24]
Другая причина, побуждающая манипулировать индексами, заключается в том, что таким путем можно избежать расходов на перемещения записей целиком. Достигается значительная экономия, если записи большие ( а ключи маленькие), поскольку для выполнения операции сравнения требуется доступ только к небольшой части записи, а большая часть записи в процессе выполнения сортировки не затрагивается. В самом деле, если ключи длинные, то операции обмена могут быть даже не такими дорогостоящими, как операции сравнения. При получении оценки времени выполнения сортировки целочисленных файлов тем или иным методом, часто предполагается, что стоимости операций сравнения и обмена приблизительно одного порядка. Выводы, полученные на основе такого предположения, можно, по-видимому, отнести к широкому классу приложений в тех случаях, когда применяется сортировка по указателям или индексная сортировка. [25]
Положенный в основу этого кода алгоритм в интерфейсе не определен, хотя быстрая сортировка ( см. главу 7) находит широкое применение. В главе 7 мы рассмотрим многие причины, почему это так. Благодаря материалу данной главы, а также глав с 7 по 11, станет понятно, почему в условиях некоторых специальных приложений целесообразно применение ряда других методов сортировки. Кроме того будут исследоваться подходы к ускорению вычислений в тех случаях, когда время выполнения сортировки является критическим фактором для приложения. [26]
Можно легко проверить это свойство на примере данных, приведенных на рис. 6.2, представляющих собой таблицу размерностью N на N, на которой незаштрихованные буквы соответствуют сравнениям. Примерно половина элементов этой таблицы не заштрихована, эти элементы расположены над диагональю. Каждому из TV - 1 элементов ( за исключением завершающего элемента) на диагонали соответствует операции обмена. Эти свойства сохраняются независимо от природы входных данных; единственный показатель сортировки выбором, зависящий от характера входных данных - это число операций присваивания переменной min новых значений. В наихудшем случае эта величина также становится квадратично зависимой, однако в среднем она характеризуется значением O ( N ogN) ( см. раздел ссылок), так что мы вправе рассчитывать на то, что время выполнения сортировки выбором не чувствительно к природе входных данных. [27]