Для каждого i от I до г-1 поменять местами элемент a[i] с минимальным элементом в последовательности a[i],…,a[r],. По мере продвижения индекса i слева направо, элементы слева от него зани-
мают свои окончательные позиции в массиве (дальнейшим перемещениям они не подлежат), таким образом, массив будет полностью отсортирован, когда i достигнет его правого конца.
template
void selection (Item a[], int 1, int r)
{ for (int i = 1; i r; i++)
{ int min = i ;
for (int j = i+1; j r; j++)
if (a[j] a [min]) min = j;
exch(a[i], a[min]);
}
}
Недостаток сортировки выбором заключается в том, что время ее выполнения лишь в малой степени зависит от того, насколько упорядочен исходный файл. Процесс нахождения минимального элемента за один проход файла дает очень мало сведений о том, где может находиться минимальный элемент на следующем проходе этого файла. Например, пользователь, применяющий этот метод, будет немало удивлен, когда узнает, что на сортировку почти отсортированного файла или файла, записи которого имеют одинаковые ключи, требуется столько же времени, сколько и на сортировку файла, упорядоченного случайным образом. Как мы убедимся позже, другие методы с большим успехом используют преимущества присутствия порядка в исходном файле.
Несмотря на всю ее простоту и очевидный примитивизм подхода, сортировка выбором превосходит более совершенные методы в одном из важных приложений: этому методу сортировки файлов отдается предпочтение в тех случаях, когда записи файла огромны, а ключи занимают незначительное пространство. В подобного рода приложениях затраты ресурсов на перемещения записей намного превосходят стоимость операций сравнения, а что касается перемещения данных, то никакой алгоритм не способен выполнить сортировку файла с меньшим числом перемещений данных, нежели метод выбора (см. лемму 2, раздел 5.5).
Рис.19. Пример сортировки выбором
Сортировка вставками
Метод сортировки, который часто применяют игроки в бридж по отношению к картам на руках, заключается в том, что отдельно анализируется каждый конкретный элемент, который затем помещается в надлежащее место среди других, уже отсортированных элементов. В условиях компьютерной реализации следует позаботиться о том, чтобы освободить место для вставляемого элемента путем смещения больших элементов на одну позицию вправо, после чего на освободившееся место помещается вставляемый элемент. Функция sort из программы 9 является программной реализацией этого метода, получившего название сортировки вставками (insertion sort)[3].
Как и в случае сортировки выбором, элементы, находящиеся слева от текущего индекса, отсортированы в соответствующем порядке, тем не менее, они еще не занимают свои окончательные позиции, ибо могут быть передвинуты с целью освобождения места под меньшие элементы, которые обнаруживаются позже. Массив будет полностью отсортирован, когда индекс достигнет правой границы массива. На рис.20 показано, как работает этот метод на примере учебного файла.
Реализация сортировки вставками, представлен- представленная в программе 9, проста, но не может считаться эффективной. Сейчас мы рассмотрим три способа его совершенствования, иллюстрирующих мотив, который прослеживается во многих разрабатываемых реализациях, а именно: требуется получить компактный, понятный и эффективный программный код, однако эти целевые установки время от времени вступают между собой в противоречие, поэтому часто приходится искать компромисс. Это достигается путем разработки естественной программной реализации с последующим ее улучшением за счет определенной последовательности преобразований с проверкой эффективности (и правильности) каждого такого преобразования.
Прежде всего, можно отказаться от выполнения операций compexch, если встречается ключ, который не больше ключа вставляемого элемента, поскольку подмассив, находящийся слева,
уже отсортирован. А именно, если справедливо условие a[j-l] 1 обычно оказывается излишней: и в самом деле, она достигает цели только в случае, когда вставляемый элемент является наименьшим из просмотренных к этому моменту, благодаря чему он достигает начала массива. Широко используемая альтернатива этому заключается в том, чтобы сохранять сортируемые ключи в элементах массива от а[1] до a[N], а сигнальный ключ {sentinel key) поместить в а[0], устанавли-
вая его значение, по меньшей мере, не превышающим наименьшего ключа в сортируемом массиве. Теперь проверка того факта, что обнаружен ключ меньше сигнального, одновременно становится проверкой обоих представляющих интерес условий, благодаря чему внутренний цикл становится меньше, а быстродействие программы
повышается.
Сигнальные ключи иногда не слишком удобны в применении: по-видимому, не очень-то просто определить значение минимально возможного ключа либо вызывающая программа не располагает местом под дополнительный ключ. В программе 11 предлагается один из способов обойти обе упомянутых проблемы в условиях сортировки вставками: сначала выполняется отдельный проход вдоль массива, в результате которого элемент с минимальным ключом помещается в первую позицию. Затем сортируется остальной массив, при этом первый элемент, он же наименьший, служит в качестве сигнального ключа. В общем случае следует избегать употребления в программах сигнальных ключей, поскольку зачастую легче воспринимаются программные коды с явными проверками, однако ситуации, когда сигнальные ключи могут оказаться полезными в плане упрощения программы и повышения ее эффективности, обязательно будут фиксироваться.
