1.1. Бинарные вставки
Этот метод упоминается Джоном Мочли в 1946г. в первой публикации по машинной сортировке.
Метод является улучшенной версией предыдущего метода простых вставок. Он основывается на том факте, что мы вначале ищем место в уже упорядоченной части массива, куда нужно вставить элемент, используя бинарный поиск, а затем уже вставляем. Это дает существенный выигрыш по числу сравнений, но число перестановок по прежнему остается большим.
Сначала Х сравнивается с элементом k[j/2], затем, в зависимости от результата сравнения, с элементом, лежащим посередине между 1 и j/2 или посередине между j/2+1 и j и т.д.
Например, если вставляется 64-я запись, то можно сравнить ее с 32-й, и если 64-я запись окажется меньше, то сравнить ее уже с 16-й, а если окажется больше, то сравнить с 48-й и т.д. Таким образом, место 64-й записи будет определено в худшем случае за шесть сравнений.
При этом число сравнений для каждого j равно примерно lg(j).Число пересылок элементов при этом не изменяется и остается примерно равным N/4.
Время работы алгоритма t примерно оценивается формулой:
t=a*N2 + b*N + c*N*lgN,
где a,b,c - неизвестные константы, зависящие от программной реализации алгоритма.
1.2. Двухпутевые вставки
Главный недостаток метода простых вставок заключается в том, что приходится сдвигать большое количество элементов. Метод бинарных вставок позволяет ускорить процесс поиска места для вставки очередного элемента. Однако для освобождения этого места по-прежнему необходимо подвинуть примерно 1/2j ранее рассортированных записей. В начале 50-х годов был предложен один из первых приемов, позволяющий сократить число необходимых переписей в памяти, - метод двухпутевых вставок.
Число пересылок можно сократить примерно в 2 раза (до N2/8), если допустить сдвиги элементов не только вправо, но и влево. Для выходного файла резервируется место в памяти, равное 2N-1,где N – число элементов в исходном файле. Первый элемент пересылается в середину выходного файла. В дальнейшем элементы выходного файла сдвигаются вправо или влево в зависимости от того, в какую сторону нужно сдвигать меньше элементов. Файл из предыдущего примера будет сортироваться следующим образом.
исходный файл
|
|
503
|
|
87
|
|
512
|
|
61
|
|
908
|
|
170
|
|
897
|
|
275
|
|
выходной файл
|
комментарий
|
|
|
|
|
|
|
|
|
503
|
|
|
|
|
|
|
X = 87
|
|
|
|
|
|
|
|
^
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
87
|
|
503
|
|
|
|
|
|
|
X = 512
|
|
|
|
|
|
|
|
|
|
^
|
|
|
|
|
|
|
|
|
|
|
|
|
87
|
|
503
|
|
512
|
|
|
|
|
X = 61
|
|
|
|
|
|
^
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
61
|
|
87
|
|
503
|
|
512
|
|
|
|
|
X = 908
|
|
|
|
|
|
|
|
|
|
|
|
^
|
|
|
|
|
|
|
|
|
61
|
|
87
|
|
503
|
|
512
|
|
908
|
|
|
X = 170
|
|
|
|
|
|
|
|
^
|
|
|
|
|
|
|
|
|
|
|
61
|
|
87
|
|
170
|
|
503
|
|
512
|
|
908
|
|
|
X = 897
|
|
|
|
|
|
|
|
|
|
|
|
^
|
|
|
|
|
|
|
61
|
|
87
|
|
170
|
|
503
|
|
512
|
|
897
|
|
908
|
X = 275
|
|
|
|
|
|
|
|
^
|
|
|
|
|
|
|
|
|
61
|
|
87
|
|
170
|
|
275
|
|
503
|
|
512
|
|
897
|
|
908
|
конеч. сост.
|
Из таблицы видно, что присоединение новых элементов к выходному файлу происходит как справа, так и слева от центрального элемента 503 с возможным сдвигом вправо или влево.
Необходимость отвести для выходного отсортированного массива место под 2N-1 элементов объясняется тем, что изначально неизвестно, куда относительно первой записи будут добавляться элементы. Например, если первый элемент окажется минимальным, то все последующие будут расположены справа от него, а слева останется N-1 пустых записей. Аналогично для случая, когда первый элемент наибольший, заполненными будут только N левых элементов. При реализации алгоритма необходимо следить за правой и левой границей и освобождать неиспользованные области памяти.
Время работы алгоритма t примерно оценивается формулой:
t = a*N2 + b*N
где a, b - неизвестные константы, зависящие от программной реализации алгоритма.
|
