const n=9;  amax=99;
var a: array [0..n] of integer;
                  s,j: integer;
BEGIN
               {Заповнення масиву}
randomize;
for j:=1 to n do begin
  a[j]:=random(amax);
  write(a[j]:4)      end;
writeln;
write('Сума парних чисел з поданих дорівнює ');

{Обчислення суми елементів масиву}  
s:=0;
for j:=1 to n do if (a[j] mod 2) = 0 then s:=s+a[j];
writeln(s)
END.

Визначення найменшого елемента масиву
Ідея пошуку така: змінній min — найменшому значенню з проглянутих — спочатку надають значення елемента масиву з найменшим номером. Послідовно переглядаючи значення наступних елементів масиву при виявленні значення, меншого від min, надаємо змінній min цього значення.

const n=9;  amax=99;
var a: array [0..n] of integer;
                min,j: integer;
BEGIN
                      {Заповнення масиву}
randomize;
for j:=1 to n do begin
  a[j]:=random(amax);
  write(a[j]:4)      end;
writeln;
write('Найменше з поданих чисел дорівнює ');

     {Визначення найменшого елемента масиву}  
min:=a[1];
for j:=2 to n do if a[j]<min then min:=a[j];
writeln(min)
END.

Впорядкування елементів масиву вибором найменшого елемента
(опис подано для лінійного масиву з діапазоном індексу 1..n)

Змінюючи j від 1 — найменшого значення індексу — до (n – 1) — найбільшого значення індексу, зменшеного на 1, — робимо таке:

• визначаємо номер l найменшого елемента для індексів у межах від j до n включно;
• міняємо місцями значення елементів з індексами j та l. У результаті такої заміни на місце з номером (індексом) j стане те значення, що потрібно.

Подамо для наочності ілюстрацію такого впорядкування 10-елементного масиву, запози­чену зі сторінки Вікіпедії.

Тут червоним тлом виділено те значення, яке серед елементів з номером від j до n вважають найменшим у поточний момент виконання алгоритму, блакитним — значення поточного елемента масиву, яке порівнюють з тим, що наразі вважають найменшим, жовтим — ті значення, які вже стоять на потрібному місці.

Код програми мовою Pascal має такий вигляд.

const n=9;  amax=99;
var a: array [1..n] of integer;
            min,j,k,l: integer;
BEGIN
                      {Заповнення масиву}
randomize;
for j:=1 to n do begin
  a[j]:=random(amax);
  write(a[j]:4)   end;
writeln;
writeln('Результат впорядкування цього масиву такий');

                      {Впорядкування масиву}  
for j:=1 to n-1 do
begin
  l:=j;
  for k:=j+1 to n do if a[l]>a[k] then l:=k;
  min:=a[l];
       a[l]:=a[j];
             a[j]:=min
end;
for j:=1 to n do begin
  write(a[j]:4)   end;
writeln;
END.

Метод швидкого сортування
Основу цього алгоритму розробив у 1962 році британський учений Чарлз Ентоні Річард Гоар (Charles Antony Richard Hoare).

Рекурсивний алгоритм для впоряд­кування за неспаданням масиву зі значеннями індексів від l до r включно має такий вигляд:

1. Вибирати значення елемента масиву.

2. Значення елементів масиву, що не менші за вибране, розташувати на місцях з номерами (індексами) більшими від індексу обраного значення, а ті, що не перевищують — на місцях з номерами меншими від індексу обраного значення. У результаті вибране значення матиме той номер j у масиві, що потрібно. Тому надалі відповідний елемент масиву буде незмінним.

3. Якщо l < (j – 1), виконати алгоритм для індексів від l до (j – 1) включно.

4. Якщо (j + 1) < r, виконати алгоритм для індексів від (j + 1) до r включно.

Пункт 2 цього алгоритму можна деталізувати:

• надати змінним i, j значення l, r відповідно;
• збільшувати значення l, поки l-й елемент менший від обраного;
• збільшувати значення r, поки r-й елемент більший від обраного;
• при l < r:
  • поміняти місцями елементи з індексами l і r;
  • збільшити значення l на 1;
  • зменшити значення r на 1.

Рекурсивність алгоритму означає виклик цього алгоритму в ньому самому — див. кроки 3–4. На малюнку нижче подано частину схеми впорядкування.

Тут кольоровими кругами позначено вибрані значення елементів масиву. Після переставлянь навколо них ці значення надалі залишаються нерухомими у масиві. Спочатку буде впорядковано елементи, менші від значення, позначеного зеленим кольором, потім — менші від значення, позначеного червоним кольором, ще пізніше — менші від значення, позначеного синім кольором.

Примітка. Поданий вище запис стане алгоритмом лише після того, як буде деталізовано вибір значення. У багатьох описах алгоритму можна зустріти вибір елемента з найменшим чи з найбільшим номером. Розглянемо спробу впорядкувати вже впорядкований масив при такому виборі. Глибина занурення — кількість послідовних викликів рекурсивного алгоритму без виходу з нього — буде майже збігатися з довжиною масиву. Останнє може призвести до переповнення стеку частини оперативної пам'яті, куди програма заносить дані про виклик програмі та функцій, їхні аргументи, точку повернення тощо. А переповнення стеку означає аварійне завершення роботи. Який би не був детерміністичний (без випадковостей) вибір значення (наприклад, із середини масиву), завжди можна вказати вхідні дані, для яких глибина занурення для цих вхідних даних лише на 1 відрізнятиметься від довжини масиву. Тому вибір потрібно робити з використанням генератора випадкових чисел. І в цьому випадку можливе переповнення стеку, але ймовірність цієї події настільки мала, що аварійне припинення роботи зазвичай не відбувається.

Проаналізуйте на відповідність опису ілюстрацію для вибору правого краю (елемента з найбільшим номером), запозичену із сайту http://uk.wikipedia.org/wiki

і код програми.

const n=9;  amax=99;
var a: array [1..n] of integer;
    j: integer;
procedure QSort(l,r: integer); 
        var x,y,i,j: integer; 
BEGIN 
x:=a[l+random(r-l+1)]; {Випадковий вибір значення}
i:=l; j:=r; 
while i<=j do   begin{1} 
  while a[i]<x do i:=i+1; 
  while a[j]>x do j:=j-1; 
  if i<=j then  begin{2} 
    y:=a[i];  {Заміна значень елементів}
       a[i]:=a[j];     {з номерами i, j}
             a[j]:=y;
    i:=i+1;
    j:=j-1        end{2}
                  end{1};
if l<j then qsort(l,j); 
if i<r then qsort(i,r); 
END; 
BEGIN 
{Заповнення масиву}
randomize;
for j:=1 to n do begin
  a[j]:=random(amax);
  write(a[j]:4)   end;
writeln;
writeln('Результат впорядкування цього масиву такий');
qsort(1,n);
for j:=1 to n do begin {Виведення результату}
  write(a[j]:4)   end;
writeln;
END.

При прямуванні n — довжини лінійного масиву — до нескінченності кількість виконуваних операцій при впорядкуванні (майже) пропорційна:

• n² — для методів впорядкування вибором найменшого елемента або бульбашки і шейкерного, не описаних у цій розробці;

• n log₂n — для методів впорядкування Хоара або пірамідального і злиттям, не описаних у цій розробці;

• n + m — для методу обліку з m — кількістю елементів діапазону зміни значень елементів масиву.

Іншими словами про це кажуть так: часові складності алгоритмів дорівнюють відповідно O(n²), O(n log₂n) і O(n + m). У більшості випадків доречно використати саме швидкий метод Хоара, хоча бувають випадки, коли для розв'язування поставленої задачі (не лише впорядкування) потрібно використати, наприклад, метод злиття, або використати метод обліку, щоб задовольнити обмеження на час виконання програми. Обидва випадки зустрічалися на ІІІ (міському) етапі Всеукраїнської учнівської олімпіади з інформатики у місті Києві.

Метод обліку передбачає використання окремого масиву з нульовими початковими значеннями, який після проглядання масиву, що підлягає впорядкуванню, містить інформацію про те, скільки разів те чи інше значення зустрілося серед значень елементів масиву.

const n=9;  amax=99;
var a: array [1..n] of integer;
    b: array [1..amax] of integer;
                   j,k,l: integer;
BEGIN
randomize;
for j:=1 to n do begin
  a[j]:=random(amax);
  write(a[j]:4)   end;
writeln;
writeln('Результат впорядкування цього масиву такий');

for j:=0 to amax do b[j]:=0;
for j:=1 to n do inc(b[a[j]]);
l:=0;
for j:=0 to amax do 
for k:=1 to b[j] do begin
      inc(l); a[l]:=j end;

for j:=1 to n do begin
  write(a[j]:4)   end;
writeln;
END.

(Бінарний) пошук заданого елемента
Розглянемо задачу пошуку номера елемента упорядкованої за зростанням послідовності {a_n}, який (елемент) має значення b. Зазвичай для цього викорис­товують двійковий (бінарний) пошук. Він полягає у послідовному поділі (приблизно) навпіл діапазону номерів, у якому проводять пошук. На початку виконання цього алгоритму:

j — менша межа діапазону номерів, на якому шукають потрібний номер, дорівнює меншій межі діапазону номерів масиву;

k — більша межа діапазону номерів, на якому шукають потрібний номер, дорівнює більшій межі діапазону номерів масиву.

Алгоритм бінарного пошуку має такий вигляд:

1. Поки справджується нерівність j ≤ k, робити таке:

   • надати значення змінній l = [(j + k)/2] — знайти індекс l, що поділяє досліджуваний діапазон навпіл;

   • якщо a_l = b, завершити пошук зі знайденим номером l;

   • якщо a_l < b, надати значення змінній j = (l + 1), тобто вибрати для подальшого пошуку діапазон, розташований правіше від l;

   • якщо a_l > b, надати значення змінній k = (l – 1), тобто вибрати для подальшого пошуку діапазон, розташований лівіше від l.

2. Завершити пошук, вважаючи його неуспішним.

Тут квадратні дужки (у першій дії всередині циклу) позначають операцію визначення цілої частини.

У поданій далі програмі крім описаних вже змінних використано булеву змінну s (англійською search — шукати): s справджується, якщо шуканого номеру немає або пошук ще не завершено.

const n=9;  amax=3;
var       b,j,k,l: integer;  s: boolean;
a: array [0..n] of integer;

BEGIN              {Заповнення масиву}
randomize;
a[0]:=0;
for j:=1 to n do begin
  a[j]:=a[j-1]+1+random(amax);
  write(a[j]:4)   end;
writeln;
b:=1+random(a[n]);

write('Серед елементів цього масиву значення ',b);
s:=true;
j:=1;                {Бінарний пошук}
k:=n;
while (j<=k) and s do    begin
  l:=(j+k) div 2;
  if a[l]=b then s:=false else
  if a[l]<b then j:=l+1   else
  if a[l]>b then k:=l-1    end;
if not s then writeln (' має елемент з номером ',l)
         else writeln (' не має жоден елемент');
END.

5. Закріплення вивченого матеріалу

1. Що таке масив?
2. Які властивості має масив?
3. Що таке форма масиву?
4. Як описують масив?
5. Які методи впорядкування лінійних масивів Ви знаєте?
6. У чому полягає впорядкування масиву швидким методом Хоара?
7. У чому полягає бінарний пошук?

6. Підбиття підсумків уроку
Виставлення оцінок.

7. Домашнє завдання

1. Вивчити матеріал уроку.
2. Написати програму розв'язання такої задачі: заповнити лінійний масив випадковим чином і визначити, скільки разів досягається найбільше значення у даному масиві та найменший порядковий номер (індекс) для такого найбільшого значення.

Текст упорядкував Вовк Олександр Валерійович, вчитель ліцею «Наукова зміна» Дарницького району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 15.09.2014 по 03.10.2014.