birmaga.ru
добавить свой файл

1 2 ... 4 5
4.5 Сортировка и поиск


Сортировка и поиск являются одними из наиболее распространенных процессов обработки данных. Списки учеников в журналах и телефонные справочники сортируются в алфавитном порядке. Аналогично отображаются списки переменных, массивов и функций в системе АЛГОРИТМ. Перечень поставщиков, предлагающих один и тот же товар по разной цене, обычно сортируется в порядке возрастания цены, а список футбольных и других спортивных команд – в порядке убывания набранных очков. В любом случае сортировки приходится иметь дело с данными, записанными в массиве, и требуется поменять местами элементы массива так, чтобы они размещались в определенном порядке их значений.

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

Существуют различные алгоритмы сортировки, которые в конечном итоге дают одинаковый результат, но отличаются объемом вычислений. В принципиальном отношении различие между ними заключается в степени учета возможности того, что в каких-то фрагментах массива данные уже расположены в требуемом порядке. Учет указанного обстоятельства влечет за собой усложнение алгоритма. Более высокая эффективность сложных алгоритмов сортировки проявляется лишь при обработке больших массивов (тысячи и более элементов). Для относительно небольших массивов (состоящих из десятков – сотен элементов) вполне оправдано использование простейших алгоритмов сортировки. Рассмотрим два таких алгоритма. Они, в частности, интересны тем, что моделируют естественное поведение человека, который выполняет сортировку вручную.

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

ЗАДАЧА 4.6. Задан массив а, состоящий из n чисел, размещенных в произвольной последовательности. Требуется упорядочить элементы массива в порядке возрастания.


Математическая модель

В результате сортировки элементы массива a должны удовлетворять неравенству

aiai+1 для всех i = 1, 2,…, n – 1.

Вычислительная модель решения задачи зависит от метода сортировки.

4.5.1 Линейная сортировка

Данный метод является наиболее простым для понимания и реализации.

Среди всех n элементов массива a найдем минимальный (см. п.4.4.1 задача 4.3) и поменяем местами 1-й элемент и найденный. Для этого запомним значение минимального элемента в переменной am, а его индекс – в переменной jm. Затем запишем значение 1-го элемента a[1] на место найденного элемента с индексом jm

a[jm] := a[1], (4.28а)

а на место 1-го элемента запишем найденное минимальное значение

a[1] := am. (4.28б)

Повторим поиск минимального значения среди элементов с индексами 2, 3,…, n и найденное минимальное значение запишем на место a[2]. Аналогично поступим с оставшейся частью массива.

Обозначим:

i – индекс элемента, куда записывается очередное найденное минимальное значение;

j – индекс анализируемых элементов массива, среди которых отыскивается минимальный.

Из рассмотренного выше принципа линейной сортировки следует, что для его реализации необходимо организовать два цикла: один цикл с параметром i является внешним, а второй цикл с параметром j является внутренним. Для каждого значения индекса i = 1, 2,…, n поиск минимального элемента производится в диапазоне индексов j = i, i+1,…, n. При этом не исключено, что i-й элемент является минимальным. Поэтому в теле цикла по i в самом начале следует выполнить присваивания

am := a[i]; jm := i. (4.29)

Тогда в цикле с параметром j анализ элементов массива можно начинать с индекса j = i+1 и заканчивать индексом n. При этом если i = n, то j = n+1 и внутренний цикл по j с начальным значением n+1 и конечным значением n просто не выполнится (см. в п.4.4.1 свойства цикла с параметром для признака to).



Проиллюстрируем операции сортировки на примере массива a = {3, 7, 2, 5, 9, 4, 6, 8}. Последовательность выполнения операций для 1-го и 2-го проходов внешнего цикла по i приведена на рис. 4.18.

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



следующая страница >>