Конспект лекций по программированию для начинающих. Гладков В.П. - 176 стр.

                                        178

                                    5     7 сравниваем,
                               3    5 сравниваем.

Четвертый просмотр:     1      2    3         |5   7     9
                                                   7     9 сравниваем,
                                              5    7 сравниваем.

Пятый просмотр: 1       2      3    5               |7      9
                                                    7       9 сравниваем.
   Завершены все n-1 (в данном случае пять) просмотров. Массив отсортирован. В
данном случае четвертый и пятый просмотр оказались лишними, однако в общем
случае они необходимы. Ниже приводится фрагмент программы, реализующий
данный алгоритм.
   for i:=1 to n-1 do {всплывание «пузырька» на i-ое место}
      for j:=n downto i+1 do
              if a[j-1]>a[j] then begin r:=a[j]; a[j]:=a[j-1]; a[j-1]:=r end.
   Упражнения:
   1. Перепишите фрагмент программы так, чтобы просмотр соседей
осуществлялся с первого элемента массива и «тяжелые» элементы оседали в конце
массива.
   2. Модифицируйте предложенный вариант алгоритма сортировки обменом,
чтобы убрать лишние просмотры.
   3. Постройте такой тест, для которого все n-1 просмотры будут
результативными, т.е. в ходе просмотра будет совершен хотя бы один обмен
элементов.
   4. Установите, какую задачу решает представленный ниже фрагмент
программы. Сравните данный алгоритм с алгоритмом метода «пузырька».
   for i:=1 to n-1 do
      for j:=i+1 to n do
              if a[i]>a[j] then begin r:=a[i]; a[i]:=a[j]; a[j]:=r end.

                            11.8. Двумерные массивы
   Двумерный массив можно рассматривать как одномерный массив, каждый
элемент которого сам является одномерным массивом. Поэтому для работы с
элементами двумерного массива нужно организовать два цикла. Каждый из них
отвечает за перебор значений соответствующего индекса. Для двумерного массива
можно использовать те же схемы перебора, что и для одномерного, но комбинаций
здесь будет в два раза больше (почему?).
   Рассмотрим один из способов ввода элементов двумерного массива. Будем
использовать схему перебора по одному от начала массива к концу.
Соответствующий фрагмент алгоритма приведен ниже. Считаем, что массив имеет
размерность n·m.
   for i:=1 to n do {перебираем строки двумерного массива}
       for j:=1 to m do {перебираем столбцы двумерного массива}
              read(a[i,j]).