По убыванию

Рис. 7 Нахождение наименьшего значения одномерного массива и его индекса

Рис. 5 Схема обмена значениями между двумя переменными

3 Нахождение наибольшего (наименьшего) значения одномерного массива

Под структурой данных типа массив понимают однородную структуру однотипных данных, одно-временно хранящихся в последовательных ячейках оперативной памяти. Эта структура должна иметь имя и определять заданное количество данных (элементов). Однотипность данных дает возможность использования циклических алгоритмов для обработки всех элементов массива. Количество итераций цикла определяется количеством элементов массива. Одновременное хранение в памяти всех элементов

массива позволяет решать большой набор задач, таких как поиск элементов, упорядочение и изменение порядка следования элементов. Доступ к любому элементу массива осуществляется по его номеру (ин-дексу). Поэтому для обращения к элементу массива используют имя переменной-массива и значение номера элемента.

Вход

Вход

 

Summa = О

Faktorial = 1

 

N, 1

►С ^к = '•

Summa

Summa + x_k

I

k = 2, N,l

Ч

I

Faktorial = Faktorial * k

 

Вывод

Summa

Выход

L

Вывод

Faktorial

 

J

Выход

а) b)

Рис. 6 Схемы алгоритмов вычисления суммы (а) и произведения (б)

Рассмотрим алгоритм нахождения наименьшего значения и его индекса в одномерном массиве, со-стоящем из N элементов – М(N) (рис. 23). При выборе наименьшего значения вначале задают или вы-бирают некое эталонное значение. Для массива этим значением может являться первый элемент. Затем в цикле начинают перебирать все оставшиеся элементы массива и сравнивать каждый из них с эталон-ным значением. В случае если текущий элемент оказывается лучше эталона, его принимают за новый эталон. При выборе наибольшего значения поступают аналогичным образом.

4 Сортировка массивов

Под сортировкой понимается процесс размещения объектов некоторого списка в порядке следова-ния их значений (по возрастанию или по убыванию). Во всем спектре задач, связанных с применением ЭВМ, сортировке принадлежит исключительно важное место.

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

Алгоритм линейной сортировки заключается в следующем. Выбирается первый элемент ряда и по-следовательно сравнивается со всеми стоящими за ним элементами. В случае если два сравниваемых элемента расположены неверно друг по отношению к другу, то они меняются местами. И так до конца ряда. В итоге на первом месте в ряду окажется либо самый маленький, либо самый большой элемент ряда (в зависимости от сортировки: по убыванию или по возрастанию). Затем берется второй элемент ряда и также сравнивается со всеми стоящими за ним элементами, в случае необходимости выполняется перестановка. Подобные действия выполняются со всеми элементами ряда до конца. После всех опи-санных действий получается отсортированный ряд. На рис. 24 приведен пример линейной сортировки одномерного массива S(N) по возрастанию.

Несмотря на простоту программной реализации, производительность линейной сортировки невысо-ка, так как для обработки любого n-элементного ряда требуется одно и то же число сравнений. К при-

меру, для сортировки n элементов требуется выполнить около n²/2 сравнений независимо от их перво-начального расположения, включая даже случай, когда задан полностью упорядоченный ряд. Таким об-разом, путь к повышению производительности линейной сортировки лежит через уменьшение общего числа сравнений, для чего необходимо учитывать характер предварительного распределения значений элементов.

Указанный недостаток отсутствует в методе "пузырьковой" сортировки, в основе которого лежит следующая идея: если каждый элемент ряда находится в правильном положении по отношению к двум соседним с ним, то весь ряд отсортирован. В соответствии с этой идеей алгоритм "пузырьковой" сор-тировки заключается в следующих действиях. Берется первая пара рядом стоящих элементов (1-й и 2-й элементы) и сравнивается между собой. В случае если элементы стоят неверно друг по отношению к другу, то они меняются местами. Далее таким же образом сравнивается следующая пара (2-й и 3-й эле-менты) и так до конца ряда, пока не произойдет сравнение предпоследнего и последнего элемента. Та-кое сравнение всех членов ряда равносильно прохождению одного "пузырька" через ряд. После этого возвращаются в начало ряда и повторяют сравнение всех элементов (второй "пузырек") и т.д. Описан-ные действия продолжаются многократно – до тех пор, пока очередной проход через ряд не зарегистри-рует отсутствие перестановок (для этого можно использовать логическую либо какую другую перемен-ную). В этом случае сортировка считается законченной. На рис. 25 приведен алгоритм "пузырьковой" сортировки одномерного массива по убыванию.

 

Рис. 8. Линейная сортировка Рис. 9. Пузырьковая сор-
nо возрастанию тировка