Rambler's Top100

Улучшенные методы сортировки

Сортировка с помощью включений с уменьшающимися расстояниями.

Сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на расстоянии 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 компонент.  

Вверх

Белорусский рейтинг MyMinsk.com Сайты беларуси Регистр "ЗУБР" Каталог на TIGA.BY, а также  новости, работа, объявления, фото и многое другое Рейтинг@Mail.ru Rambler's Top100 Белорусский каталог программ Faststart - рейтинг сайтов, каталог интернет ресурсов, счетчик посещаемос­ти Яндекс.Метрика
Hosted by uCoz