мими элементами (если ключи большие) либо с указателями (если ключи небольших размеров). Можно переупорядочить элементы после сортировки, но часто в этом нет необходимости, поскольку теперь уже имеется возможность обращения к ним в порядке, установленном сортировкой (косвенным путем). Непрямые методы сортировки рассматриваются в разделе 6.8.

Упражнения

t> 6.1. Детская игрушка, в которой используются свойства сортировки, состоит из / карт, каждую из них можно нанизать на колышек в /-й позиции, причем / принимает значения от 1 до 5. Разработать метод, который можно использовать для нанизывания карт на колышки, принимая во внимание то обстоятельство, что по виду карты нельзя сказать, можно ли ее надеть на тот или иной колышек (для этого потребуется предпринять попытку надеть карту на колышек).

6.2. Карточный трюк требует, чтобы колода карт была упорядочена по мастям (сначала пики, далее черви, трефы и бубны), а внутри каждой масти - по старшинству. Попросите нескольких своих друзей решить эту задачу (перед каждой попыткой перетасуйте карты!) и запишите методы, которыми они пользовались.

6.3. Объясните, как вы будете сортировать колоду карт при условии, что карты необходимо укладывать в ряд лицевой стороной вниз, причем допускается проверка значений только двух карт и (при необходимости) обмен местами этих карт.

о 6.4. Объясните, как вы будете сортировать колоду карт при условии, что карты хранятся в колоде, а единственная допустимая операция с ними состоит в том, что выявляются значения двух верхних карт в колоде, обмен этих карт местами и перемещение верхней карты в низ колоды.

6.5. Приведите пример последовательностей из трех операций сравнения-обмена, посредством которых выполняется сортировка совокупности из трех элементов.

о 6.6. Приведите пример последовательностей из пяти операций сравнения-обмена, посредством которых выполняется сортировка совокупности из четырех элементов.

6.7. Напишите клиентскую программу, которая проверяет, является ли используемая подпрограмма сортировки устойчивой.

6.8. Проверка того, что массив отсортирован в результате применения функции sort, не дает никаких гарантий того, что сортировка работает. Почему так получается?

6.9. Написать клиентскую программу, представляющую собой драйвер, измеряющий эффективность сортировки, который многократно выполняет функцию sort на файлах различных размеров, измеряет время каждого выполнения этой функции и выводит на печать (в виде текста или графического изображения) значения среднего времени выполнения сортировки.

6.10. Написать учебную клиентскую программу-драйвер, которая выполняет функцию sort в сложных или патологических случаях, которые могут иметь место в практических приложениях. Примерами могут служить уже упорядоченные файлы, файлы, представленные в обратном порядке, файлы, все записи которых имеют одни и те же ключи, файлы, содержащие только два отличных друг от друга значения, файлы размерами О или 1.

6.2. Сортировка выбором

Один из самых простых алгоритмов сортировки работает следующим образом. Сначала отыскивается наименьший элемент массива, затем он меняется местами с элементом, стоящим первым в сортируемом массиве. Далее, находится второй наименьший элемент и меняется местами с элементом, стоящим вторым в исходном массиве. Этот процесс продолжается до тех пор, пока весь массив не будет отсортирован. Изложенный метод называется сортировкой выбором, поскольку он работает по принципу выбора наименьшего элемента из числа неотсортированных. На рис 6.2. представлен пример работы этого метода.

Программа 6.2 -- суть реализация сортировки выбором, в которой выдержаны все принятые нами соглашения. Внутренний цикл представляет собой сравнение текущего элемента с наименьшим из выявленных к тому времени элементом (плюс программный код, необходимый для увеличения на единицу индекса текущего элемента и проверки того, что он не выходит за границы массива); трудно себе представить более простой метод сортировки. Действия по перемещению элементов выходят за пределы внутреннего цикла: каждая операция обмена элементов местами устанавливает один из них в окончательную позицию, так что всего потребуется выполнить 7V - 1 таких операций (для последнего эле-

РИСУНОК 6.2. ПРИМЕР СОРТИРОВКИ ВЫБОРОМ

В этом примере первый проход не дал резулыпата, поскольку слева от к в массиве нет элемента, меньшего А. На втором проходе другой элемент А оказался наименьшим среди оставшихся, поэтому он меняется местами с элементом S, занимающим вторую позицию. Далее, на третьем проходе, элемент Е, находящийся в середине массива, меняется местами с О, занимающим третью позицию; затем, на четвертом проходе, еще один элемент Е меняется местами с R, занимающим четвертую позицию и т.д.

мента эту операцию выполнять не нужно). Таким образом, основную составляющую времени выполнения сортировки представляет количество осуществленных операций сравнения. В разделе 6.5 будет показано, что это время пропорционально Л, а также представлены способы вычисления общего времени выполнения программы сортировки и корректного сравнения сортировки выбором и других элементарных методов.

Программа 6.2. Сортировка выбором

Для каждого i от I до г-1 поменять местами элемент a[i] с минимальным элементом в последовательности a[i],...,a[r],. По мере продвижения индекса 1 слева направо, элементы слева от него занимают свои окончательные позиции в массиве (дальнейшим перемещениям они не подлежат), таким образом, массив будет полностью отсортирован, когда i достигнет его правого конца.

template <class Item>

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[inin]);

Недостаток сортировки выбором заключается в том, что время ее выполнения лишь в малой степени зависит от того, насколь упорядочен исходный файл. Процесс нахождения минимального элемента за один проход файла дает очень мало сведений о том, где может находиться минимальный элемент на следующем проходе этого файла. Например, пользователь, применяющий этот метод, будет немало удивлен, когда узнает, что на сортировку почти отсортированного файла или файла, записи которого имеют одинаковые ключи, требуется столько же времени, сколько и на сортировку файла, упорядоченного случайным образом! Как мы убедимся позже, другие методы с большим успехом используют преимущества присутствия порядка в исходном файле.

Несмотря на всю ее простоту и очевидный примитивизм подхода, сортировка выбором превосходит более совершенные методы в одном из важных приложений: этому методу сортировки файлов отдается предпочтение в тех случаях, когда записи файла огромны, а ключи занимают незначительное пространство. В подобного рода приложениях затраты ресурсов на перемещения записей намного превосходят стоимость операций сравнения, а что касается перемещения данных, то никакой алгоритм не способен выполнить сортировку файла с меньшим числом перемещений данных, нежели метод выбора (см. лемму 6.5, раздел 6.5).

Упражнения

> 6.11. в стиле рис. 6.2 показать, как сортируется учебный файл EASYQUES Т I О N методом выбора.

6.12. Какой максимальной величины достигает число обменов для любого конкретного элемента в процессе сортировки выбором? Что собой представляет среднее количество обменов, приходящееся на один элемент?

6.13. Приведите пример файла из Л элементов, в котором число случаев невыполнения условия a[j] < a[min] достигает максимального значения (вследствие чего min принимает новое значение) в процессе выполнения сортировки выбором.

о 6.14. Является ли сортировка выбором устойчивой?

6.3. Сортировка вставками

Метод сортировки, который часто применяют игроки в бридж по отношению к картам на руках, заключается в том, что отдельно анализируется каждый конкретный элемент, который затем помещается в надлежащее место среди других, уже отсортированных элементов. В условиях компьютерной реализации следует позаботиться о том, чтобы освободить место для вставляемого элемента путем смещения больших элементов на одну позицию вправо, после чего на освободившееся место помещается вставляемый элемент. Функция sort из программы 6.1 является профаммной реализацией этого метода, получившего название сортировки вставками (insertion sort).