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

UptoLike

ВУЗ: 

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

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

Рубрика: 

41
Программа 14. Процедура алгоритма
сортировки методом выбора
Const n=20;
Type mass=array[1 . . n] of real;
procedure Select(var A:mass; n: integer);
var i, j, k: integer; x: real;
begin
for i:= 1 to n–1 do
begin
x:= А[ i ]; k:= i;
for j:= i+1 to n do
if А[ j ]<x then begin x:= А[ j ]; k:=j;
end;
А[ k ]:= А[ i ]; А[ i ]:=x;
End;
End;
Рисунок 23. Блок-схема алгоритма
сортировки методом выбора
Простой обмен
Любой метод, так или иначе, связан с обменом, то есть с
перестановкой двух элементов в памяти. Но, если для других методов
сортировки это действие является вспомогательным, то для сортировки
методом обмена – это основная характеристика метода.
Суть данного метода заключается в многократных сравнениях
ряд
ом стоящих элементов и их перестановке, если они расположены не в
заданном порядке.
Будем рассматривать исходный массив с конца к началу. В
принципе, можно организовать и обычный просмотр массива с начала в
конец. Сравниваем четвертый и пятый элементы. Они расположены в
порядке возрастания, поэтому их оставляем на своих местах. Сравнение
третьего и ч
етвертого элементов показывает, что их нужно переставить.
НАЧАЛО
X:= A( i );
k:= i;
КОНЕЦ
i:=1, n–1
A( j ) ≥ X
нет
да
j:=1+1, n
X:= A( j );
k:= j;
A( k ):= A( i );
A( i ):=X;
42
Таблица 7.
Номер элемента
1 2 3 4 5
Исходный массив
23 11 82 6 9
Теперь значение четвертого элемента будет равно 82, а третьего – 6.
При сравнении третьего и второго элементов видим, что их нужно также
переставить, тогда значение третьего элемента будет равно 11, а второго –
6. Наконец, сравниваем первый элемент со вторым. Их тоже нужно
переставить местами. Таким образом, в результате первого просмотра
получим следующее:
Таблица 8.
Номер элемента
1 2 3 4 5
Исходный массив
6 23 11 82 9
Видно, что в результате первого просмотра массива минимальный
элемент перемещается на первое место. Очевидно, что его можно не
включать в дальнейшие просмотры, то есть длина неупорядоченного
массива будет уменьшаться. Нетрудно убедиться, что каждый следующий
просмотр массива будет приводить к перестановке очередного
минимального элемента в левый конец рассматриваемой части массива.
Таким образом, в ре
зультате n–1 просмотров получим упорядоченный
массив.
Обратимся к листу опорного сигнала №3 (Рисунок 22.). Представьте
себе, что элементы массива – это пузырьки воздуха в стакане с водой.
Каждый пузырек весом, пропорциональным своему значению. Тогда
каждый проход с обменом по массиву пузырьков приводит к скорому
всплыванию пузырька на соответствующий его весу уровень. Бла
годаря
такой аналогии метод обмена получил название сортировки методом
“пузырька”. На рисунке первые два пузырька уже упорядочены и
“всплывает” третий пузырек. Знак ≤ (но не< !) показывает, что необходим
обмен между элементами. Этим достигается устойчивость метода.
Если массив частично упорядочен, то он будет отсортирован за
меньшее число просмотров. В числовом примере алгор
итма видно, что за
пятый, шестой и седьмой просмотры не было ни одной перестановки. Это
можно учесть в алгоритме, введя признак k. 
                          Программа 14. Процедура алгоритма                        Таблица 7.
         НАЧАЛО
                          сортировки методом выбора
                                                                                   Номер элемента      1     2    3    4    5
                          Const n=20;
          i:=1, n–1                                                                Исходный массив     23    11   82   6    9
                          Type mass=array[1 . . n] of real;
         X:= A( i );                                                                     Теперь значение четвертого элемента будет равно 82, а третьего – 6.
                                 procedure Select(var A:mass; n: integer);         При сравнении третьего и второго элементов видим, что их нужно также
           k:= i;
                                var i, j, k: integer; x: real;                     переставить, тогда значение третьего элемента будет равно 11, а второго –
                                                                                   6. Наконец, сравниваем первый элемент со вторым. Их тоже нужно
         j:=1+1, n              begin
                                                                                   переставить местами. Таким образом, в результате первого просмотра
                                   for i:= 1 to n–1 do                             получим следующее:
  да                                 begin
         A( j ) ≥ X                                                                Таблица 8.
                                     x:= А[ i ]; k:= i;                                                1    2     3    4    5
                                                                                   Номер элемента
                  нет
                                   for j:= i+1 to n do                             Исходный массив     6    23    11   82   9
         X:= A( j );
           k:= j;                  if А[ j ]

Страницы