Алгоритм сортировки по возрастанию одномерного массива

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

Псевдокод:

алг сорт (арг табцел N, арг табвещ X[1:N], резтабвещ M[1:N]) начцел i, k |    ввод N, X[1:N] |    M[1:N]:=X[1:N] |    k:=1 |    нцпока k=1 |    |    k:=0 |    |    нц для i от 2 до N |    |    |    если M[i-1]>M[i] |    |    |    |    то b:=M[i] |    |    |    |             M[i]:=M[i-1] |    |    |    |             M[i-1]:=b |    |    |    |             k:=1 |    |    |    все |    |    кц |    кц |    вывод M кон

 

 

Данный алгоритм, как это видно из его описания, содержит в себе вложенный цикл (цикл со счетчиком – цикл «для» внутри цикла с предусловием – цикла «пока»).

 

Развёрнутая схема алгоритма (самостоятельно):

 

 

 

Схема с альтернативными обозначениями циклов (самостоятельно):

 

 

Тема 5.4 Рекурсивные алгоритмы

Обращение к подпрограммам

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

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

 

Пример использования подпрограмм:

 

алг Alg(аргвещ X, Y, Z, резвещ D)                 алг F1(аргвещ Arg, резвещ Res)

нач                                                                      нач

|    ввод X, Y, Z                                                 |    Res:=Arg*Arg

|    A:=F1(X)                                                       кон

|    B:=F2(Y,Z)                                                        

|    C:=F2(A,B)                                                    алг F2(аргвещ Arg1, Arg2, резвещ Res)

|    D:=A+B+C                                                    нач

|    вывод D                                                       |    Res:=Arg1*Arg2

кон                                                                           кон

 

 

Схема алгоритма:

 

 

Понятие рекурсии

Рекурсивным называется алгоритм (или функция), содержащий в себе вызов самого себя (обращение к самому себе). Простой рекурсией является использование операции присваивания в следующем виде:

a:=a+1.

 

Классическим примером рекурсивного алгоритма является функция вычисление факториала целого числа N! = 1·2·3·…·N, N ≥ 0, 0! = 1.

 

алг Факториал(аргцел N, резцел F)

Нач

|    если N=0

|    |    то F:=1

|    |    иначе F:=Факториал(N-1)*N

|    все

Кон

 

Результатом работы следующего алгоритма:

 

Алг

Нач

|    A:=Факториал(5)

|    вывод A

Кон

 

является значение A=120=5!.

 

Из рекурсивной функции необходимо предусмотреть выход, иначе вызов такой функции может привести к «зависанию» алгоритма. В рассмотренном примере условием выхода из рекурсии является проверка условия N=0, при выполнении которого функция возвращает 1. Однако данное условие неработоспособно, если будет введено отрицательное значение (N<0) аргумента функции. В этом случае функция F будет бесконечно вызывать саму себя, поэтому для предотвращения бесконечной рекурсии здесь необходимо предусмотреть и проверку условия N<0, при выполнении которого должно выдаваться сообщение об ошибке ввода.

Виды рекурсии

Рекурсия бывает прямой и косвенной:

· прямой называется рекурсия, когда обращение к самому себе содержится в самом алгоритме (функции);

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