Улучшенные методы сортировкиСортировка с помощью включений с уменьшающимися расстояниями.Сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на расстоянии 4. Такой процесс называется четверной сортировкой. После первого прохода элементы перегруппировываются - теперь каждый элемент группы отстоит от другого на две позиции - и вновь сортируются. Это называется двойной сортировкой. И наконец, на третьем проходе идет обычная или одинарная сортировка. Например: Дан массив, состоящий из элементов: 44 55 12 42 94 18 06 67 После четверной сортировки получаем: 44 18 06 42 94 55 12 67 Т.е. элементы, отстоящие на 4 позиции друг от друга сравниваются и меняются местами в случае необходимости (44<94, 55>18 значит меняем местами, 12>06 тоже меняем местами, 42<67). После двойной сортировки получаем: 06 18 12 42 44 55 94 67 Теперь сравниваем элементы, отстоящие на 2 позиции (44>06 - меняем, 94>12 - меняем, 44>12 - меняем и т.д.) После одинарной сортировки получаем: 06 12 18 42 44 55 67 94 На первый взгляд можно засомневаться: если необходимо несколько процессов сортировки, причем в каждый включаются все элементы, то не добавят ли они больше работы, чем сэкономят? Однако на каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуется сравнительно немного перестановок. Ясно, что такой метод в результате дает упорядоченный массив, и, конечно же, сразу видно, что каждый проход от предыдущих только выигрывает (так как каждая i-сортировка объединяет две группы, уже отсортированные 2i-сортировкой). Так же очевидно, что расстояния в группах можно уменьшать по-разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу. Все t расстояния обозначаются соответственно h1,h2,...,ht, для них выполняются условия ht=1, hi+1<hi Каждая h-сортировка программируется как сортировка с помощью прямого включения. Причем простота условия окончания поиска места для включения обеспечивается методом барьеров. Ясно, что каждая из сортировок нуждается в постановке своего собственного барьера и программу для определения его местоположения необходимо делать насколько возможно простой. Поэтому приходится расширять массив не только на одну-единственную компоненту a0, а на h1 компонент. |