72 Глава 3. Алгоритмы сортировки
тировка вставками, сортирует список, вставляя очередной элемент в нужное место уже отсортированного списка. Пузырьковая сортировка сравнивает элементы попарно, переставляя между собой элементы тех пар, порядок в которых нарушен. Сортировка Шелла представляет собой многопроходную сортировку, при которой список разбивается на подсписки, каждый из которых сортируется отдельно, причем на каждом проходе число подсписков уменьшается, а их длина растет. При корневой сортировке список разбивается на стопки, и при каждом проходе используется отдельная часть ключа. Пирамидальная сортировка строит бинарное дерево, значение каждого узла в котором превышает значение потомков. В результате наибольший элемент списка помещается в корень, и при его удалении и выборе очередной пирамиды в корне оказывается следующий по величине элемент. Этот процесс повторяется пока все элементы не окажутся в новом, уже отсортированном, списке. Сортировка слиянием берет два уже отсортированных списка и создает, сливая их, новый отсортированный список. Быстрая сортировка представляет собой рекурсивный алгоритм, который выбирает в списке осевой элемент, а затем разбивает список на две части, состоящие из элементов соответственно меньших или больших выбранного.
Последняя сортировка предназначена для работы со списками, размер которых настолько велик, что они не помещаются целиком в памяти компьютера. Эта внешняя сортировка работает с группами записей в последовательных файлах; ее задача — минимизировать количество обращений к внешним устройствам (операция, требующая гораздо больше времени, чем сравнение). Читателю стоит принять во внимание, что даже расширенная память в современных компьютерах, в которую можно записать одновременно все записи базы данных, не решает проблемы: операции обмена в памяти все равно приводят к задержкам. Операционная система осуществляет такой обмен, переписывая сегменты виртуальной памяти на жесткие диски, хотя эти операции и не указаны в алгоритме явно.
3.1. Сортировка вставками
Основная идея сортировки вставками состоит в том, что при добавлении нового элемента в уже отсортированный список его стоит сразу вставлять в нужное место вместо того, чтобы вставлять его в произвольное место, а затем заново сортировать весь список. Сортировка
