Этот программа представляет собой усовершенствованный вариант функции sort из программы 9, поскольку (i) он помещает наименьший элемент массива в первую позицию; в этом качестве наименьший элемент может быть использован как сигнальный ключ; (ii) во внутреннем цикле он выполняет лишь одну операцию
присваивания; операция обмена исключается; и (iii) он прекращает выполнение внутреннего цикла, когда вставляемый элемент уже находится в требуемой позиции. Для каждого i он сортирует элементы a[l],…,a[i], перемещая на одну позицию вправо элементы а[l],…,a[i-1] из отсортированного списка, которые по значению больше a[i], после чего а[i] попадает в соответствующее место.
template
void insertion (Item a[], int 1, int r)
{ int i;
for (i = r; i 1; i—) compexch (a [i-1] , a[i]);
for (i = 1+2; i
{ int j = i; Item v = a[i];
while (v a[j-l])
{ a[j] = a[j-l]; j —; }
a[j] = v;
}
}
Третье улучшение, которое сейчас будет рассматриваться, также касается удаления лишних команд из внутреннего цикла. Оно следует из того факта, что последовательные обмены значениями с одним и тем же элементом не эффективны. Если производятся два или большее число обменов значениями, то мы имеем
t = a[j]; a[j] = a[j-l] ; a[j-l] = t;
t = a[j-l]; a[j-l] = a[j-2] ; a[j-2] = t
и т.д. Значение t в этих двух последовательностях не изменяется, но при этом происходит бесполезная трата времени на его запоминание и последующее чтение с целью следующего обмена значениями. Программа 11 передвигает большие элементы на одну позицию вправо вместо того, чтобы воспользоваться операцией обмена, тем самым избегая напрасной траты времени.
Рис.20. Пример выполнения сортировки вставками
Программа 11 является реализацией сортировки методом вставки, обладающей большей эффективностью, нежели программная реализация этого же метода сортировки, включенная в программу 9 (в разделе 5.5 мы убедимся в том, что ее быстродействие примерно в два раза выше). В рамках данной книги нас интересуют не только элегантные и одновременно эффективные алгоритмы, но и элегантные и одновременно эффективные реализации этих алгоритмов. В подобных случаях положенные в их основу алгоритмы несколько отличаются друг от друга — было бы правильно назвать функцию sort из программы 9 неадаптивной сортировкой вставками (nonadaptive insertion sort). Правильное понимание свойств алгоритма — лучшее руководство при разработке его программной реализации, которая может эффективно использоваться в различных приложениях.
В отличие от сортировки выбором, время выполнения сортировки вставками зависит главным образом от исходного порядка ключей при вводе. Например, если файл большой, а ключи записей уже упорядочены (или почти упорядочены), то сортировка вставками выполняется быстро, а сортировка выбором протекает медленно. Более полное сравнение различных алгоритмов сортировки приводится в разделе 5.5.
Пузырьковая сортировка
Метод сортировки, который многие обычно осваивают раньше других из-за его исключительной простоты, называется пузырьковой сортировкой (bubble sort), в рамках которой выполняются следующие действия: проход по файлу с обменом местами соседних элементов, нарушающих заданный порядок, до тех пор, пока файл не будет окончательно отсортирован. Основное достоинство пузырьковой сортировки заключается в том, что его легко реализовать в виде программы, однако вопрос о том, какой из методов сортировки реализуется легче других — пузырьковый, метод вставок или метод выбора — остается открытым. В общем случае пузырьковый метод обладает несколько меньшим быстродействием, однако его все же стоит рассмотреть для полноты картины[3].
Предположим, что мы всегда передвигаемся по файлу справа налево. Если удается обнаружить минимальный элемент на первом проходе, он меняется местами с каждым элементом, стоящим от него слева, и, в конце концов, этот элемент помещается в позицию на левой границе массива. Затем на втором проходе в соответствующую позицию устанавливается второй по величине элемент и т.д. Таким образом, вполне достаточно выполнить N проходов, т.е., пузырьковую сортировку можно рассматривать как один из видов сортировки выбором, хотя при этом для помещения каждого элемента в соответствующую позицию приходится выполнять больший объем действий. Программа 12 представляет собой реализацию алгоритма пузырьковой сортировки, а на рис.21
показан пример работы этого алгоритма.
Рис.21. Пример выполнения пузырьковой сортировки
