1. Вопросы и упражнения

1. Как следует изменить алгоритм барьерного поиска, если свободная позиция находится не в конце, а в начале массива?

2. Есть такая математическая игра. Один человек задумывает число от 1 до 1 000, а другой должен определить это число, задав десять вопросов, на которые первый отвечает «Да» или «Нет». Какие вопросы следует задавать? Сколько потребуется вопросов, если задумано число от 1 до 1 000 000?

3. Дан массив целых чисел A= (–5, –2, 3, 8, 12, 12, 15, 20, 30, 35, 40, 41, 41, 49, 50). Выполните вручную алгоритм бинарного поиска для ключаx= 12 и для ключаx= 42, выписывая значенияi,j,q,A[q].

3. Алгоритмы сортировки массивов

   1. Задачи сортировки таблиц и массивов

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

Процедура перестановки записей таблицы в порядке возрастания значений заданного ключа называется сортировкой¹таблицы. Для массива сортировка – это перестановка его элементов в порядке возрастания.

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

В настоящее время известно много алгоритмов выполнения сортировки. Их разнообразие определяется особенностями конкретных задач.

В данном разделе описаны наиболее важные из алгоритмов сортировки таблиц, представленных массивом в оперативной памяти компьютера. В одном из подразделов рассматриваются также особенности сортировки файлов.

2. Простые алгоритмы сортировки

К простым алгоритмам относятся несколько широко известных алгоритмов, основанных на простых и очевидных идеях. В том случае, когда программист, незнакомый с теорией, сталкивается с необходимостью отсортировать массив, он обычно самостоятельно переоткрывает один из этих алгоритмов.

1. Алгоритм пузырька (BubbleSort)

Идея алгоритма заключается в следующем. Сравним элементы массива с индексами 1 и 2. Если первый больше второго, то поменяем эти элементы местами. Затем таким же образом сравним (и, если нужно, переставим) элементы с индексами 2 и 3, потом 3 и 4 и т.д. После сравнения элементов (n–1) иnпервый проход алгоритма завершается. Можно гарантировать, что после этого прохода максимальный элемент массива находится на последнем месте (т.е. имеет индексn). На втором проходе сравниваем пары 1 и 2, 2 и 3, ... (n–2) и (n–1). Далее аналогично. Послеn–1прохода все элементы займут свои законные места.

У многих программистов появляется желание сократить число проходов, отмечая с помощью специального флажка, были ли сделаны какие-либо перестановки на очередном проходе. Если ни одной перестановки за весь проход не было, то массив, очевидно, уже отсортирован и работу алгоритма можно завершить досрочно. Однако такое усовершенствование редко дает заметный выигрыш. Нетрудно показать, что для массива, заполненного случайным образом, с вероятностью 75 % все равно будут выполнены все проходы алгоритма.