Основы алгоритмизации и программирования. Часть вторая. Типовые алгоритмы обработки массивов. Асламова В.С - 22 стр.

UptoLike

ВУЗ: 

АГТА | Ангарск

Составители: 

Рубрика: 

43
Таблица 9. Числовой пример алгоритма
После просмотра нижних элементов
Номер
элемента
Исходный
массив
8 7 6 5 4 3 2
Итог
1 14
1
1 1 1 1 1 1 1
2 42 14
7
7 7 7 7 7 7
3 65 42 14
8
8 8 8 8 8
4 7 65 42 14
9
9 9 9 9
5 8
7
65 42
14 14
14 14 14
6 9 8
8
65 42 42
15
15 15
7
1
9 9
9
65 65
42 42
42
8 15 15 15 15 15
15
65 65 65
Составим алгоритм для решения задачи. Ясно, что основной
алгоритм будет цикл, выполняющийся n–1
раз. Выбор границ для параметра цикла,
например, от i от 1 до n–1 или от 2 до n
повлияет лишь на задание индексов
сравниваемых элементов. Остановимся на
второй паре границ. Для сравнения нужен
оператор цикла с параметром j, зависящим от
i, так как пр
и каждом проходе по массиву его
длина укорачивается. Следовательно, для
второй пары границ j будет меняться в
пределах от n до i с шагом –1. После
очередного просмотра необходимо
анализировать значение признака x. Значение
k=0 означает, что за просмотр не было ни
одной перестановки элементов, то есть
сортировка закончена, а пр
и k=1
упорядочение массива следует продолжать.
Блок-схема рассмотренного алгоритма
приведена на Рисунке 24.
Программа 15. Процедура сортировки
методом обмена
Const n=20;
Type mass=array[1 . . n] of real;
procedure Exchange(var A:mass; n: integer);
Label 1;
var i, j, k: integer; x: real;
Рисунок 24. Блок-схема алгоритма
сортировки методом обмена
НАЧАЛО
k:= 0;
КОНЕЦ
i:=2, n
A(j–1)>A( j )
да
нет
j:=n, i (–1)
X:= A( j–1);
k:= 1;
A(j–1):= A( j);
A( j ):=X;
A(j–1)>A( j )
да
нет
44
begin for i:=2 to n do
begin k:=0;
for j:= n downto i do
if A[ j–1]>A[ j ] then
begin k:=j; X:=A[ j–1];
A[j–1]:=A[ j ]; A[ j ]:=x
end;
if k=0 then goto 1
1: end;
A[k]:= A[ i ]; A[ i ]:=x;
end;
end;
Метод простых вставок
Обратимся к листу опорного сигнала №3
(Рисунок 22.). Часть массива слонов уже
упорядочена (это первые три слона). Четвертый
слон, который ищет свое место, сравнивает
свой размер с размером слонов, стоящих левее
его (об этом свидетельствуют знаки сравнения).
Знак ≤ (но не < !) показывает, когда нужно
прекратить сравнение, то есть движение влево
по послед
овательности – этим достигается
устойчивость метода. Строй, состоящий из
второго и третьего слонов, сдвигается вправо,
освобождая ему место, куда он и становится.
Рисунок 25. Блок-схема алгоритма
сортировки методом вставок
Пусть в заданной последовательности А[1], А[2],…,А[ n ] первые i–1
элементов уже упорядочены и ищется место для i-го элемента. Будем
сравнивать А1 эле
мент по порядку со всеми элементами, стоящими левее,
до тех пор, пока не окажется, что некоторый A[ k ] ≤ A[ i ]. Затем сдвинем
часть последовательности A[k+1], …, A[j–1] на один элемент вправо и
НАЧАЛО
X:=A( i );
j:= i–1; k:= 1;
КОНЕЦ
i:=2, n
j = 0
нет
да
k:= j+1;
j:= 0;
j:= j–1;
k = i
нет
да
A( i )<A( j )
нет
да
A( j ):=A( j–1)
j:=1,k+1(–1)
A( k ):= X; 
Таблица 9. Числовой пример алгоритма                                                                           begin for i:=2 to n do
                                                                                   НАЧАЛО
 Номер      Исходный    После просмотра нижних элементов                                                            begin k:=0;
                                                               Итог                  i:=2, n
элемента     массив      8    7    6    5   4    3    2                                                               for j:= n downto i do
       1           14    1    1    1    1   1    1    1          1                                                         if A[ j–1]>A[ j ] then
                                                                                    X:=A( i );
       2           42   14    7    7    7   7    7    7          7               j:= i–1; k:= 1;
       3           65   42   14         8   8    8    8          8                                                           begin k:=j; X:=A[ j–1];
                                   8
       4            7   65   42   14    9   9    9    9          9                                 да                           A[j–1]:=A[ j ]; A[ j ]:=x
       5            8    7   65   42 14     14   14   14         14                   j=0
                                                                                                                             end;
       6            9    8    8   65   42   42   15   15         15                       нет
       7            1    9    9    9   65   65   42   42         42                                                   if k=0 then goto 1
                                                                                                   да
       8           15   15   15   15   15   15   65   65         65               A( i )A( j )    очередного         просмотра        необходимо                                  его (об этом свидетельствуют знаки сравнения).
                        анализировать значение признака x. Значение
                                                                                 A( j ):=A( j–1)        Знак ≤ (но не < !) показывает, когда нужно
                   да   k=0 означает, что за просмотр не было ни
                        одной перестановки элементов, то есть                                           прекратить сравнение, то есть движение влево
       X:= A( j–1);
           k:= 1;       сортировка      закончена,        а  при     k=1                                по последовательности – этим достигается
                        упорядочение массива следует продолжать.                  A( k ):= X;           устойчивость метода. Строй, состоящий из
      A(j–1):= A( j);   Блок-схема       рассмотренного       алгоритма                                 второго и третьего слонов, сдвигается вправо,
         A( j ):= X;    приведена на Рисунке 24.
                                                                                     КОНЕЦ              освобождая ему место, куда он и становится.
                        Программа 15. Процедура сортировки
  нет                   методом обмена
       A(j–1)>A( j )    Const n=20;                                        Рисунок 25. Блок-схема алгоритма
                        Type mass=array[1 . . n] of real;                  сортировки методом вставок
                 да        procedure Exchange(var A:mass; n: integer);
                            Label 1;                                             Пусть в заданной последовательности А[1], А[2], ,А[ n ] первые i–1
           КОНЕЦ              var i, j, k: integer; x: real;               элементов уже упорядочены и ищется место для i-го элемента. Будем
Рисунок 24. Блок-схема алгоритма                                           сравнивать А1 элемент по порядку со всеми элементами, стоящими левее,
сортировки методом обмена                                                  до тех пор, пока не окажется, что некоторый A[ k ] ≤ A[ i ]. Затем сдвинем
                                                                           часть последовательности A[k+1], , A[j–1] на один элемент вправо и

                                                                      43   44

Страницы