Вопросы и упражнения. 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].

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

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

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

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

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

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

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