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

UptoLike

ВУЗ: 

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

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

Рубрика: 

45
освободим место A[k+1] для элемента A[ i ], куда его и поставим. После
того, как мы проделаем подобные действия для всех элементов со второго
по n-ный, получим отсортированную последовательность. Следует
отметить, что при сравнении A[ i ] элемента со всеми элементами,
стоящими леве его может оказаться, что не найдется такого эле
мента A[k ],
для которого выполняется условие A[ k ] ≤ A[ i ]. Это будет, если A[ i ]
меньше всех элементов, стоящих левее. Данная ситуация изображена на
Рисунке 22 дорожным знаком “прочие опасности”
!
. В этом случае
необходимо закончить просмотр по достижению первого элемента
последовательности и осуществить сдвиг А[1], …, А[i-1] вправо на одну
позицию, а элемент A[ i ] поставить на первое место. Кроме того, может
оказаться, что элемент A[ i ] стоит на своем месте, поэтому полученное
значение k+1 необходимо сравнивать со значением i. Если он
и совпадают,
то сдвига не требуется.
Таблица 10. Числовой пример алгоритма
Номер элемента
1 2 3 4 5 6 7 8 9
Исходный массив
82
31
22 16 7 12 63 29 54
2 31
82
22
16 7 12 63 29 54
3 22
31 82
16
7 12 63 29 54
4 16
22 31 82
7
12 63 29 54
5 7
16 22 31 82
12
63 29 54
6
7
12
16 22 31 82
63
29 54
7
7 12 16 22 31
63
82
29
54
8
7 12 16 22
29
31 63 82
54
После вставки элемента
номер
9
7 12 16 22 29 31
54
63 82
Упорядоченный массив
7 12 16 22 29 31 54 63 82
С учетом замечаний составим блок-схему изложенного метода.
Основой алгоритма будет цикл, параметр которого i определяет, для
какого элемента массива мы ищем место в упорядоченной левой части.
Значение параметра i будет меняться в пределах от 2 до n. Кроме того,
значение элемента A[ i ] необходимо запоминать, например, в переменной
x, так как он
о при сдвиге может потеряться. Необходимо также
зафиксировать номер элемента i-1, с которого будем начинать сравнение
j=i–1. Чтобы в ситуации, когда элемент A[ i ] окажется минимальным
среди элементов А[1], …, А[i-1], он мог занять первое место, положим
начальное значение k=1 (k – номер элемента, на место которого
помещается A[ i ] элемент). Так как мы не знаем значение k, то следует
испо
льзовать итерационный цикл по параметру j. В этом цикле будем
сравнивать элементы A[ j ] и A[ i ] и по результату сравнения судить,
оканчивать цикл или нет. Закончить цикл можно присваиванием
46
параметру j нулевого значения. Итак, если выполняется условие A[j]≤A[ i],
то следует п
родолжать движение влево по массиву, то есть полагать j=j–1.
При этом нужно следить, чтобы массив не кончился. Если левая часть
массива просмотрена или найден номер k, то необходимо проверить,
совпадают ли значения k и i, если совпадают, то вставляемый элемент
стоит на своем месте, поэтому переходим к следующему i. В пр
отивном
случае, необходимо в цикле сдвинуть все элементы от k-го до i–1-го
вправо на одну позицию и на место k-го элемента поместить вставляемый
элемент, значение которого хранится в x. Сдвиг необходимо начинать с
последнего элемента, чтобы не “затереть” значения последующих
элементов. Значение параметра цикла сдвига может из
меняться либо от
i–1-го до k, либо от i до k+1, это повлияет лишь на задание индексов
элементов массива. Блок-схема алгоритма метода сортировки вставками
представлена на Рисунке 25.
Программа 16. Процедура сортировки
методом вставок
Const n=20;
Type mass=array[1 . . n] of real;
procedure Insert(var A:mass; n: integer);
Label 1;
var i, j, k: integer; x: real;
begin for i:=1 to n do
begin x:=A[ i ]; j:=i–1; k:=1;
while j> 0 do
if A[ i ] ≥ A[ j ] then
begin k:=j+1; j:=0 end
else j:=j–1;
if k=i then goto 1;
for j:=1 downto k+1 do
A[ j ]:= A[ j–1 ];
A[ k ]:=x;
1: end;
end;
Рисунок 26. Блок-схема улучшенного
алгоритма сортировки методом вставок
НАЧАЛО
КОНЕЦ
i:=2, n
A( i ) ≥ A(k)
нет
да
k:=1, i–1
X:= A( i );
j:=1,k+1(–1)
A( j):= A(j–1);
A( k ):= X; 
освободим место A[k+1] для элемента A[ i ], куда его и поставим. После        параметру j нулевого значения. Итак, если выполняется условие A[j]≤A[ i],
того, как мы проделаем подобные действия для всех элементов со второго        то следует продолжать движение влево по массиву, то есть полагать j=j–1.
по n-ный, получим отсортированную последовательность. Следует                 При этом нужно следить, чтобы массив не кончился. Если левая часть
отметить, что при сравнении A[ i ] элемента со всеми элементами,              массива просмотрена или найден номер k, то необходимо проверить,
стоящими леве его может оказаться, что не найдется такого элемента A[k ],     совпадают ли значения k и i, если совпадают, то вставляемый элемент
для которого выполняется условие A[ k ] ≤ A[ i ]. Это будет, если A[ i ]      стоит на своем месте, поэтому переходим к следующему i. В противном
меньше всех элементов, стоящих левее. Данная ситуация изображена на           случае, необходимо в цикле сдвинуть все элементы от k-го до i–1-го
Рисунке 22 дорожным знаком “прочие опасности” ! . В этом случае               вправо на одну позицию и на место k-го элемента поместить вставляемый
необходимо закончить просмотр по достижению первого элемента                  элемент, значение которого хранится в x. Сдвиг необходимо начинать с
последовательности и осуществить сдвиг А[1], , А[i-1] вправо на одну          последнего элемента, чтобы не “затереть” значения последующих
позицию, а элемент A[ i ] поставить на первое место. Кроме того, может        элементов. Значение параметра цикла сдвига может изменяться либо от
оказаться, что элемент A[ i ] стоит на своем месте, поэтому полученное        i–1-го до k, либо от i до k+1, это повлияет лишь на задание индексов
значение k+1 необходимо сравнивать со значением i. Если они совпадают,        элементов массива. Блок-схема алгоритма метода сортировки вставками
то сдвига не требуется.                                                       представлена на Рисунке 25.
Таблица 10. Числовой пример алгоритма                                                     НАЧАЛО          Программа 16. Процедура сортировки
                                                                                                          методом вставок
      Номер элемента             1    2    3    4    5    6    7    8    9                                Const n=20;
      Исходный массив            82   31   22   16   7    12   63   29   54                 i:=2, n
                                      82        16   7    12   63   29   54                               Type mass=array[1 . . n] of real;
                             2   31        22
                             3   22   31   82   16   7    12   63   29   54               k:=1, i–1              procedure Insert(var A:mass; n: integer);
                             4   16   22   31   82   7    12   63   29   54                                      Label 1;
После вставки элемента       5   7    16   22   31   82   12   63   29   54        да
        номер                6   7    12   16   22   31   82   63   29   54                                         var i, j, k: integer; x: real;
                                                                                         A( i ) ≥ A(k)
                             7   7    12   16   22   31   63   82   29   54                                         begin for i:=1 to n do
                                                                                                 нет
                             8   7    12   16   22   29   31   63   82   54
                                                                                                                      begin x:=A[ i ]; j:=i–1; k:=1;
                             9   7    12   16   22   29   31   54   63   82               X:= A( i );
  Упорядоченный массив           7    12   16   22   29   31   54   63   82                                              while j> 0 do

       С учетом замечаний составим блок-схему изложенного метода.                                                        if A[ i ] ≥ A[ j ] then
                                                                                        j:=1,k+1(–1)
Основой алгоритма будет цикл, параметр которого i определяет, для                                                           begin k:=j+1; j:=0 end
какого элемента массива мы ищем место в упорядоченной левой части.
                                                                                                                            else j:=j–1;
Значение параметра i будет меняться в пределах от 2 до n. Кроме того,                   A( j):= A(j–1);
значение элемента A[ i ] необходимо запоминать, например, в переменной                                              if k=i then goto 1;
x, так как оно при сдвиге может потеряться. Необходимо также                                                        for j:=1 downto k+1 do
зафиксировать номер элемента i-1, с которого будем начинать сравнение                    A( k ):= X;
j=i–1. Чтобы в ситуации, когда элемент A[ i ] окажется минимальным                                                    A[ j ]:= A[ j–1 ];
среди элементов А[1], , А[i-1], он мог занять первое место, положим                                                 A[ k ]:=x;
начальное значение k=1 (k – номер элемента, на место которого
                                                                                                          1: end;
помещается A[ i ] элемент). Так как мы не знаем значение k, то следует                     КОНЕЦ
использовать итерационный цикл по параметру j. В этом цикле будем                                         end;
сравнивать элементы A[ j ] и A[ i ] и по результату сравнения судить,         Рисунок 26. Блок-схема улучшенного
оканчивать цикл или нет. Закончить цикл можно присваиванием                   алгоритма сортировки методом вставок


                                                                         45   46

Страницы