Після мітки, що відмічає оператор, треба ставити двокрапку. Наприклад:
1995 : х := х +I; 1 : read(Y);
Увага! Дія оператора переходу усередину складеного оператора ззовні не визначена.
Оператор переходу слід використати у незвичайних, виняткових ситуаціях, коли доводиться порушувати природну структуру алгоритму. Треба пам’ятати, що будь-який алгоритм може бути реалізований без застосування Goto без втрати ефективності. Цей факт має принциповий характер. Саме тому структурний стиль програмування іноді називають “Програмування без Goto”.
У якості єдиного приклада програми з Goto розглянемо задачу пошуку елемента в одномірному масиві.
Приклад 7.8.
Program Search_in_Array;
Label 1;
Const
n = 100;
Type
Vector = array[1..n] of Real;
Var
A : Vector;
b : Real;
Flag : Boolean;
Procedure InpMas(Var V : Vector);
Var i : Integer;
Begin
For i := 1 to n do begin
Write(‘Введіть елемент масива : ‘);
Readln(V[i]);
end;
End;
Procedure InpData(Var b:Real);
Begin
Write(‘Введіть шукане значення : ‘);
Readln(b)
End;
Procedure Found (Var A : Vector; b : Real);
Var i : Integer;
Flag : Boolean;
Begin
Flag := true;
For i := 1 to n do
If A[i] = b then begin
Flag := false;
goto1
end; { переривання циклу }
1:If Flag
then Writeln(‘ Елемент ‘,b,’ у масиві відсутній ’)
else Writeln(‘ елемент ‘,b,’ стоїть на ’,i,’-тому місці ’);
End;
Begin
{Блок читання масиву A і елемента b}
InpMas(A);
InpData(b);
Found (A, b);
End.
Цікавий розв’язок цієї задачі без застосування Goto буде розглянуто нижче.
7.9. Постановка задачі сортування
Під сортуванням послідовності розуміють процес перестановки елементів послідовності у визначеному порядку. Мета такої впорядкованості – полегшення подальшої обробки даних (зокрема, задачі пошуку). Тому задача сортування – одна з найбільш важливих внутрішніх задач програмування.
Цікаво, що задача сортування є ідеальним прикладом великої кількості різноманітних алгоритмів, розв’язування одної й тієї ж задачі. Розглядаючи різні методи сортування, ми побачимо, як зміна алгоритму приводить до нових, більш ефективних у порівнянні з простими, розв’язувань задачі сортування.
Нехай дана послідовність елементів a1, a2, ... , an. Елементи цієї послідовності – дані довільного типу, на якому визначено відношення порядку “<<” (менше) таке, що будь-які два різні елементи можна порівняти.
Сортування означає перестановку елементів послідовності ak1, ak2, ... , akn таку, що ak1 << ak2 << ... << akn.
Приклад: послідовність документів, кожний з яких містить інформацію про людину, включаючи його вік. Потрібно розмістити документи цієї послідовності у порядку за віком, починаючи зі старшого.
7.10. Сортування масивів
Якщо послідовність a1, a2, ... , an реалізована як масив a[1..n], вся вона розміщена в адресованій пам’яті. Тому наряду з вимогами ефективності за часом основна вимога – економне використання пам’яті. Це означає, що алгоритм не повинен використовувати додаткові масиви і пересилання з масиву а в ці масиви.
Постановка задачі сортування в загальному виді передбачає, що існують тільки два типи дій з даними сортованого типу: порівняння двох елементів (x << y) і пересилання елемента (x := y). Тому зручна міра складності алгоритму сортування масиву a[1..n] за часом - кількість порівнянь C(n) і кількість пересилань M(n).
7.10.1. Прості алгоритми сортування
Прості алгоритми сортування можна класифікувати як сортування обміном, сортування вибором і сортування включеннями.
7.11 Сортування обмінами
Основна дія сортування обмінами – порівняння двох елементів і, якщо результат порівняння негативний, перестановка їх місцями:
Якщо при i < j a[i] > a[j] то переставити a[i] і a[j].
В найбільш простому варіанті порівнюються елементи a[j] і a[j+1], що стоять поряд:
Приклад 7.9.
Const
n = 100;
Type
Vector = array[1..n] of Real;
Procedure BublSort(Var a: Vector);
Var
i, j : Integer;
TempMem : Real;
Begin
For i := n - 1 downto 1 do
For j := 1 to i do
If a[j] > a[j+1]
then begin
TempMem := a[j+1];
a[j+1] := a[j];
a[j] := TempMem
end;
End;
Аналіз алгоритму сортування обмінами.
Аналіз алгоритму полягає в обґрунтуванні його властивостей. Важливішими властивостями алгоритму є: коректність (правильність), оцінка складності за часом та пам’яттю, а також деякі інші властивості.
Для обґрунтування алгоритму сортування необхідно довести, що алгоритм завжди (незалежно від входу) завершує свою роботу і його результат – впорядкований за зростанням масив. Оцінка складності (ефективності) алгоритму за часом полягає у находженні C(n), M(n) у гіршому випадку, у середньому.
Оскільки алгоритм сортує масив “на місці”, його складність за пам’яттю – константа.
До інших властивостей алгоритму можна віднести властивість стійкості. (Алгоритм сортування називається стійким, якщо він не переставляє місцями тотожні елементи.) Здійснимо аналіз алгоритму сортування обмінами.
Завершуваність.
Алгоритм BublSort завжди завершує свою роботу, оскільки він використовує тільки цикли з параметром, і в тілі циклів параметри примусово не змінюються.
Коректність.
Внутрішній цикл алгоритму (з параметром j) здійснює послідовний перегляд перших і елементів масиву. На кожному кроці перегляду порівнюються і, якщо це необхідно, переставляються два сусідніх елемента. Таким чином, найбільший серед перших і +1 елементів “ спливає ” на ( і + 1 )-е місце. Тому після виконання оператора If має місце співвідношення:
a[j+1] = Max(a[1], ..., a[i], a[j+1]) (1)
а після завершення циклу (i = j) має місце співвідношення
a[i+1] = Max(a[1], ..., a[i], a[i+1]) (2)
Зовнішній цикл (з параметром і ) керує довжиною частини масиву, що переглядається: вона зменшується на 1. Тому після завершення внутрішнього циклу має місце співвідношення:
a[i+1] £ a[i+2] £ ... £ a[n] (3)
Після завершення зовнішнього циклу отримаємо:
a[1] £ a[2], a[2] £ a[3] £ ... £ a[n] (4)
тобто масив відсортований.
Відзначимо, що більш докладне обґрунтування складається перш за все в доказі співвідношень (1), (3). Це можна зробити методом математичної індукції.
Ефективність за часом.
Зовнішній цикл виконався n-1 разів. Внутрішній цикл виконується і разів (i = n-1, n-2, ..., 1). Кожне виконання тіла внутрішнього циклу складається з одного порівняння і, можливо, з одної перестановки. Тому
C(n) = 1+2+ ... +n-1 = n*(n - 1)/2, M(n) £ n*(n - 1)/2.
У гіршому випадку (коли елементи вихідного масиву розміщені в порядку спадання)
C(n) = n*(n - 1)/2 = O(n2), M(n) = n*(n - 1)/2 = O(n2)
Стійкість.
Для доказу стійкості достатньо зауважити, що переставляються тільки сусідні нерівні елементи.
7.12. Сортування вибором
Приклад 7.10.
Основна дія сортування вибором – пошук найменшого елемента в частині масиву, що переглядається і перестановка з першим елементом цієї частини:
For i := 1 to n - 1 do begin
k := Індекс( Min(a[i], ..., a[n]));
Переставити a[i], a[k]
end;
Const
n = 100;
Type
Vector = array[1..n] of Real;
Procedure SelectSort (Var a: Vector);
Var
i, j, MinIndex : Integer;
Temp : Real;
Begin
For i := 1 to n - 1 do begin
{ пошук мінімального елемента }
MinIndex := i;
for j := i + 1 to n do
If a[j] < a[MinIndex]
then MinIndex := j;
{перестановка елементів}
Temp := a[MinIndex];
a[MinIndex] := a[i];
a[i] := Temp
end;
End;
