Информатика конспект лекций_2012

end;

B[j]:=A[i];

end;

{Вывод массива B}

…

End.

Алгоритм 2. Пузырьковая сортировка.

Реализация данного метода не требует дополнительной памяти. Метод очень прост и состоит в следующем: берется пара рядом стоящих элементов, и если элемент с меньшим индексом оказывается больше элемента с большим индексом, то они меняются местами. Эти действия продолжаются, пока есть такие пары. Легко понять, что когда таких пар не останется, то данные будут отсортированными. Для упрощения поиска таких пар данные просматриваются по порядку, от начала до конца. Из этого следует, что за такой просмотр находится максимум, который помещается в конец массива, а потому следующий раз достаточно просматривать уже меньшее количество элементов. Максимальный элемент как бы всплывает вверх, отсюда и название алгоритма. Так как каждый раз на свое место становится, по крайней мере, один элемент, то не потребуется более N проходов, где N – количество элементов. Вот как это можно реализовать:

Program BubbleSort;

Var A : array[1..1000] of integer; N,i,j,p : integer;

Begin

{Определение размера массива A (N) и его заполнение}

…

{сортировка данных} for i:=1 to n do

for j:=1 to n-i do

if A[j]>A[j+1] then

begin {Обмен элементов} p:=A[j];

A[j]:=A[j+1];

A[j+1]:=P;

end;

{Вывод отсортированного массива A}

…

End.

240

Алгоритм 3. Сортировка Шейкером.

Когда данные сортируются не в оперативной памяти, а на жестком диске, особенно если ключ связан с большим объемом дополнительной информации, то количество перемещений элементов существенно влияет на время работы. Этот алгоритм уменьшает количество таких перемещений, действуя следующим образом: за один проход из всех элементов выбираются минимальный и максимальный. Потом минимальный элемент помещается в начало массива, а максимальный, соответственно, в конец. Далее алгоритм выполняется для остальных данных. Таким образом, за каждый проход два элемента помещаются на свои места, а значит, понадобится N/2 проходов, где N – количество элементов. Реализация данного алгоритма выглядит так:

Program ShakerSort;

Var A : array[1..1000] of integer; N,i,j,p : integer;

Min, Max : integer; Begin

{Определение размера массива A - N) и его заполнение}

…

{сортировка данных} for i:=1 to n div 2 do begin

if A[i]>A[i+1] then begin

Min:=i+1;

Max:=i; end

else begin Min:=i;

Max:=i+1;

end;

for j:=i+2 to n-i+1 do if A[j]>A[Max] then Max:=j

else

if A[j]<A[Min] then

241

Min:=j;

{Обмен элементов} P:=A[i]; A[i]:=A[min]; A[min]:=P;

if max=i then max:=min; P:=A[N-i+1]; A[N-i+1]:=A[max]; A[max]:=P;

end;

{Вывод отсортированного массива A}

…

End.

Рассмотрев эти методы, сделаем определенные выводы. Их объединяет не только то, что они сортируют данные, но также и время их работы. В каждом из алгоритмов присутствуют вложенные циклы, время выполнения которых зависит от размера входных данных. Значит, общее время выполнения программ есть O(n2) (константа, умноженная на n2). Следует отметить, что первые два алгоритма используют также O(n2) перестановок, в то время как третий использует их O(n). Отсюда следует, что метод Шейкера является более выгодным для сортировки данных на внешних носителях информации.

Алгоритм 4. Сортировка слиянием.

Эта сортировка использует следующую подзадачу: есть два отсортированных массива, нужно сделать (слить) из них один отсортированный. Алгоритм сортировки работает по такому принципу: массив разбивается на две части, каждая из них отсортировывается, а потом обе части сливаются в одну отсортированную. Корректность данного метода практически очевидна, поэтому перейдем к реализации.

Program SlivSort;

Var A,B : array[1..1000] of integer; N : integer;

Procedure Sliv(p,q : integer); {процедура сливающая массивы} Var r,i,j,k : integer;

Begin

242

r:=(p+q) div 2; i:=p;

j:=r+1;

for k:=p to q do

if (i<=r) and ((j>q) or (a[i]<a[j])) then begin

b[k]:=a[i];

i:=i+1; end else begin

b[k]:=a[j];

j:=j+1; end ;

for k:=p to q do a[k]:=b[k]; End;

Procedure Sort(p,q : integer); {p,q – индексы начала и конца сор-

тируемой части массива} Begin

if p<q then {массив из одного элемента тривиально упорядочен} begin

Sort(p,(p+q) div 2); Sort((p+q) div 2 + 1,q); Sliv(p,q);

end;

End;

Begin

{Определение размера массива A – N) и его заполнение}

…

{запуск сортирующей процедуры} Sort(1,N);

{Вывод отсортированного массива A}

…

243

End.

Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай T(n) – время сортировки массива длины n, тогда для сортировки слиянием справедливо:

T(n) = 2T(n/2) + O(n) (O(n) – это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:

T(n) = 2T(n/2) + O(n) = 4T(n/4) + 2O(n/2) + O(n) = 4T(n/4) + 2O(n) = … = 2kT(1) + kO(n).

Осталось оценить k. Мы знаем, что 2k = n, а значит k = log2n.

Уравнение примет вид: T(n) = nT(1) + log2nO(n). Так как T(1) – константа, то T(n) = O(n) + log2nO(n) = O(nlog2n). То есть оценка време-

ни работы сортировки слиянием меньше, чем у первых трех алгоритмов.

244

ЛЕКЦИЯ 27. ЦИКЛИЧЕСКИЕ АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ

Циклом называют повторение одних и тех же действий (шагов). Последовательность действий, которые повторяются в цикле, называют телом цикла. Существует несколько типов алгоритмов циклической структуры. На рис. 66 изображен цикл с предусловием, а на рис. 67 – цикл с постусловием, которые называют условными циклическими алгоритмами. Нетрудно заметить, что эти циклы взаимозаменяемы, но обладают и некоторыми различиями, заключающимися

вследующем:

1.В цикле с предусловием условие проверяется до тела цикла,

вцикле с постусловием – после тела цикла.

2.В цикле с постусловием тело цикла выполняется хотя бы один

раз, в цикле с предусловием тело цикла может не выполниться ни разу.

3. В цикле с предусловием проверяется условие продолжения цикла, в цикле с постусловием – условие выхода из цикла.

Рис. 66. Алгоритм циклической	Рис. 67. Алгоритм циклической
структуры с предусловием	структуры с постусловием

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

245

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

Рис. 68. Алгоритм циклической структуры без условия

Выполнение безусловного циклического алгоритма начинается с присвоения переменной i стартового значения in. Затем следует проверка, не превосходит ли переменная i конечное значение iк.

Рис. 69. Условный циклический алгоритм с известным числом повторений

Если превосходит, то цикл считается завершенным, и управление передается следующему за телом цикла оператору. В противном случае выполняется тело цикла, и переменная i меняет свое значение

246

в соответствии с указанным шагом di. Далее снова производится проверка значения переменной i и алгоритм повторяется. Понятно, что безусловный циклический алгоритм можно заменить любым условным. Например, так, как показано на рис. 69.

Отметим, что переменную i называют параметром цикла, так как это переменная, которая изменяется внутри цикла по определенному закону и влияет на его окончание.

247

ЛЕКЦИЯ 28. ОСНОВНЫЕ ОПЕРАТОРЫ ЦИКЛОВ И ВЕТВЛЕНИЯ

Если в программе возникает необходимость неоднократного выполнения некоторых операторов, то используются операторы повтора (цикла). В языке Паскаль различают три вида операторов цикла: while, repeat, for. Они используются для организации циклов различных типов. Выражение, управляющее повторениями, должно иметь булевский тип.

Если число повторений оператора (составного оператора) заранее неизвестно, а задано лишь условие его повторения (или окончания), используются операторы while, repeat. Оператор for используется, если число повторений заранее известно.

Оператор while

Оператор while (пока) часто называют оператором цикла с предусловием, за то, что проверка условия выполнения тела цикла производится в самом начале оператора.

Синтаксическая диаграмма для данного оператора выглядит следующим образом:

Рис. 70. Синтаксическая диаграмма для оператора while

Форма записи:

While < условие продолжения пговторений> do <тело цикла>

Условие – булевское выражение, тело цикла – простой или составной оператор. Перед каждым выполнением тела цикла вычисляется значение выражения условия. Если результат равен True, тело цикла выполняется и снова вычисляется выражение условия. Если результат равен False, происходят выход из цикла и переход к первому после while оператору.

Оператор повтора repeat

Оператор повтора repeat аналогичен оператору while, но отличается от него, во-первых, тем, что условие проверяется после очередного выполнения операторов тела цикла (очередной итерации) и таким обра-

248

зом гарантируется хотя бы однократное выполнение цикла, а во-вторых, тем, что критерием прекращения цикла является равенство выражения константе True. За это цикл repeat часто называют циклом с постусловием, или циклом «ДО», так как он прекращает выполняться, как только значение выражения условия, записанного после слова until, становятся равным True (истина).

Оператор повтора repeat состоит из заголовка repeat, тела и условия окончания until.

Синтаксическая диаграмма (рис. 71) для данного оператора выглядит следующим образом:

Рис. 71. Синтаксическая диаграмма для оператора repeat

Формат записи: Repeat <оператор>

…

<оператор> Until

<условие окончания цикла>

Операторы, заключенные между словами repeat и until, являются телом цикла. Вначале выполняется тело цикла, затем проверяется условие выхода из цикла. Именно поэтому цикл, организованный с помощью оператора repeat, в любом случае, выполнится хотя бы один раз. Если результат булевского выражения равен False, то тело цикла активизируется еще раз; если результат True, происходит выход из цикла.

Оператор повтора for

В случаях, когда число повторений может быть заранее известно, для организации циклической обработки информации применяется оператор повтора for. Часто этот оператор повтора называют оператором цикла с параметром, так как число повторений задается переменной, называемой параметром цикла, или управляющей переменной.

Оператор повтора for состоит из заголовка и тела цикла.

249