Распределительная сортировка
Cтраница 1
Распределительные сортировки, в отличие от сравнительных сортировок, разделяются на блочные методы ( интервальные методы) и поразрядные методы. В блочных сортировках ключ рассматривается как единое целое и распределяется по интервалам, которые определяются так, чтобы обеспечить разумное разбиение списка на части. Поразрядные сортировки распределяют элементы по принимающим областям на основе значений конкретных разрядов ключа. [1]
Распределительные сортировки обычно требуют время, грубо оцениваемое как пропорциональное N X logp ( К) ( где р - основание применяемой системы счисления, К - максимальный размер ключа), потому что существует N проверяемых чисел и logp ( К) цифр в числе. Однако распределительные сортировки чувствительны к распределению величин элементов и плохо используют естественный порядок данных; кроме того, они часта требуют значительной дополнительной памяти. [2]
По своему характеру распределительные сортировки не являются минимальными по памяти. Поскольку они распределяют элементы по принимающим областям на основе некоторых характеристик ключей, то под эти принимающие области необходимо выделить память, отличную от той, которая используется под исходный список. [3]
 |
Пример сортировки Шелла. [4] |
Одна из простых схем распределительной сортировки называется сортировкой поразрядным группированием. Сортировка начинается с анализа самой младшей значащей цифры ключевого слова, а затем все величины с одинаковыми младшими цифрами объединяются в группы. После того как все величины распределены по такому правилу, содержимое групп располагается в порядке возрастания значения анализируемого разряда и процесс повторяется до тех пор, пока не остается цифр слева. Система счисления с основанием Р требует Р групп. [5]
Пример поразрядно-обменной сортировки показан на рис. 3.20. Это довольно сложный пример и может быть труден для понимания - отличительная черта большинства распределительных сортировок. [6]
Распределительные сортировки обычно требуют время, грубо оцениваемое как пропорциональное N X logp ( К) ( где р - основание применяемой системы счисления, К - максимальный размер ключа), потому что существует N проверяемых чисел и logp ( К) цифр в числе. Однако распределительные сортировки чувствительны к распределению величин элементов и плохо используют естественный порядок данных; кроме того, они часта требуют значительной дополнительной памяти. [7]
ПТС имеет ряд особенностей: она включает два магистральных конвейера, один из КОТОРЫХ 5 принимает грузы одновременно из нескольких точек и выполняет функции сортировочного и собирающего; выдача груза со склада производится в одной точке; прием грузов и сортировка магистральным конвейером 5 осуществляется на разных участках. Выполнение объединительной и распределительной сортировки на одном участке магистрального конвейера нецелесообразно, так как он должен в процессе работы постоянно реверсироваться. [8]
В главе 1 было оговорено различие между сравнительными и распределительными ( или классифицирующими) методами сортировки. В этой главе мы опишем ряд распределительных сортировок, а также связанные с ними проблемы и возможности. [9]
На самом деле желательно бы иметь более лучшие методы сортировки, которые бы требовали еще меньше времени. Все методы сортировки могут быть отнесены к одному из трех основных типов: ( 1) распределительные сортировки - сортируют путем анализа элементов по одной цифре за раз; ( 2) сравнительные сортировки - сортируют путем сравнения ключевых слов по два за раз и ( 3) сортировки вычислением адреса - преобразуют ключ в адрес, близкий к тому месту, где ожидается окончательное расположение символа. [10]
В сравнительном методе данные упорядочиваются по относительной величине ключей в списке. Большинство методов сортировки, которые мы будем рассматривать, являются сравнительными. Распределительный метод, наоборот, обследует каждый ключ либо целиком, либо символ за символом. Промежуточное размещение ключа зависит не от относительной величины ключа, а от характеристики, получаемой при сравнении этого ключа с некоторым стандартом. Распределительные сортировки полезны в тех случаях, когда о сортируемых данных известно многое, например, распределение ключей по некоторым интервалам, длина ключей и число записей. Когда предварительной информации меньше, предпочтительнее сравнительные сортировки, так как они менее чувствительны к распределению конкретного множества сортируемых величин. Они чувствительны к упорядоченности величин, обрабатываемых ими. [11]
Страницы: 1