Методы сортировки
Существует большое количество методов сортировки, которые обычно разбивают на 2 группы - внутренние и внешние.
Методы внешней сортировки требуются в случаях, когда массив данных настолько велик, что не помещается в оперативной памяти, а располагается в дисковых файлах (в старых книгах можно встретить специальные алгоритмы для сортировки массивов на магнитных лентах с их спецификой в виде последовательного доступа; эти методы сейчас более интересны в качестве упражнения для ума любителям математики).
Методы внутренней сортировки используются для упорядочивания данных, которые можно целиком разместить в оперативной памяти. Это позволяет выполнять произвольные перестановки элементов. Собственно различия алгоритмов заключаются в организации процесса перестановок, так как сложность алгоритма сортировки определяется в значительной степени именно числом выполненных перестановок (особенно если операции копирования элементов более трудоемки, чем копирование целых чисел).
Метод пузырька
Это самый очевидный, интуитивно понятный способ (многие другие методы с точки зрения житейской интуиции работают несмотря на очевидную неправильность). Применять его не следует (без крайней необходимости), так как его эффективность наихудшая, а по размеру программного кода он ничем не лучше многих других методов (к примеру, метода Шелла).
Метод Шелла - сортировка с помощью включений с уменьшающимися расстояниями
В 1959 г. Д.Шеллом было предложено усовершенствование сортировки с помощью прямого включения.
Сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на расстоянии 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 компонент.
Проблема заключается в том, что не известно, какие расстояния дают наилучшие результаты. Д.Кнут в работе "Искусство программирования для ЭВМ" показывает, что имеет смысл использовать такую последовательность (записана в обратном порядке):
1, 4, 13, 40, 121, ... или 1, 3, 7, 15, 31, ...
Математический анализ показывает, что в последнем случае для сортировки n элементов методом Шелла затраты пропорциональны n1.2.
Пример программной реализации
В программе показано, как сортировать массив с помощью стандартного алгоритма sort, а также приведена простая реализация алгоритма сортировки Шелла для вектора значений с весами (в виде шаблонной функции).
Проект для VisualStudio 2003 (2.8 Kb)
Ссылки
Для написания раздела использованы материалы сайта http://www.distedu.ru/mirror/_inform/bspu.secna.ru/Guide/book (составитель - Гусева Г.А.). Хороший материал по сортировкам можно найти по ссылке www.citforum.ru/programming/theory/sorting/sorting1.shtml. Последняя работа широко разошлась по рунету, но лучше читать авторский оригинал.
© Mental Computing 2010
