Алгоритми впорядкування елементів масиву

Увага! Під час роботи з комп'ютером дотримуйтеся правил безпеки і санітарно-гігієнічних норм.

Види навчальної діяльності

Обговорюємо

1. У чому полягає сутність сортування масиву методом вибору максимального елемента?
2. У чому полягає сутність методу сортування масиву методом бульбашки?
3. На якому місці у масиві може міститися його найбільший/найменший елементи, якщо масив впорядковано за зростанням; за спаданням; масив невпорядкований?

Діємо разом

• Вправа 1. Створіть проект, у якому знаходять різницю між найбільшим і найменшим елементом лінійної таблиці з 10 дійсних чисел, які набувають значень від 5 до 10 випадково.
• Створення проекту з використанням мови Object Pascal

1. Відкрийте середовище Lazarus, створіть новий проект, розмістіть на екранній формі об'єкти, як показано на скріншоті
   
2. Створіть процедуру опрацювання події натиснення кнопки Знайти. У вікні редактора коду опишіть змінні, які будуть використовуватись у проекті: а - масив дійсних чисел, i - номер (індекс) елемента масиву, max - найбільше значення серед елементів, min - найменше значення серед елементів.

var i: integer;
    max, min: real;
    a: array [1..10] of real;

3. У вікні редактора коду запишіть команди для випадкового генерування елементів масиву та виведення їх у таблицю, пошуку найбільшого й найменшого елементів масиву, виведення різниці значень max і min. Зверніть увагу на вираз, який використовується для отримання випадкового дійсного числа. 

begin
   // заповнення таблиці
   Randomize;
   StringGrid1.Cells[0,1] := 'a';
   for i := 1 to 10 do
       begin
         a[i] := 10.0 - random * 5.0;
         StringGrid1.Cells[i,0] := IntToStr(i);
         StringGrid1.Cells[i,1] := FloatToStrF(a[i], ffFixed, 3, 2);
       end;
   // пошук максимального і мінімального значень та обчислення їх різниці
   max := a[1];
   min := a[1];
   for i := 2 to 10 do
       begin
         if a[i] > max then max := a[i];
         if a[i] < min then min := a[i];
       end;
   Edit1.Text := FloatToStrF(max, ffFixed, 2, 2);
   Edit2.Text := FloatToStrF(min, ffFixed, 2, 2);
   Edit3.Text := FloatToStrF(max-min, ffFixed, 2, 2);
end;

4. Виконайте проект і проаналізуйте результати. Якщо є помилки, виправте їх і збережіть зміни. Знайдіть на екранній формі найбільше та найменше значення елементів згенерованої таблиці. Обчисліть їх різницю самостійно і порівняйте з результатами роботи програми.

• Створення проекту з використанням мови Python

1. Відкрийте середовище програмування мовою Python, створіть новий файл і збережіть його під іменем Випробування.
2. У вікні редактора коду запишіть команди випадкового генерування елементів масиву (списку) та виведення елементів списку у вікні виконання проекту, пошуку найбільшого й найменшого елементів списку, виведення різниці значень max і min. Зверніть увагу на вираз для генерування випадкових дійсних чисел мовою Python.

import random
a = []
for i in range(10):
    a.append(round((10.0 - random.random() * 5.0), 2))
print('Вхідний масив випадкових дійсних чисел: ', a)
a.sort()
print('Відсортований масив за зростанням: ',a)
print('max = {0}; min = {1}'.format(a[-1], a[0]))
print('Різниця max-min: ', round(a[-1] - a[0], 2))

3. Запустіть проект на виконання. Якщо є помилки - виправте їх. Обчисліть різницю найбільшого і найменшого значень самостійно і порівняйте її з результатом роботи програми.

• Вправа 2. Створіть проект, у якому елементи лінійної таблиці з 10 цілих чисел впорядковуються за зростанням.
• Створення проекту з використанням мови Object Pascal

1. Відкрийте середовище Lazarus і створіть новий проект, розмістіть на екранній формі об'єкти, як на скріншоті, самостійно надайте значення їхнім властивостям.
   
2. Створіть процедуру опрацювання події Упорядкувати. У вікні редактора коду опишіть змінні, які будуть використовуватись у проекті: а - масив цілих чисел, і - номер ітерації пошуку мінімального елемента масиву, j - номер елемента масиву, min - найменше значення елемента, nmin - номер найменшого елемента. 

var a: array[1..10] of integer;
    i, j, min, nmin: Integer;

3. У вікні редактора коду запишіть команди введення елементів масиву в багаторядкове текстове поле, впорядкування елементів та їх виведення в багаторядкове текстове поле. 

begin
    for i := 1 to 10 do
        a[i] := StrToInt(Memo1.Lines[i-1]);
    j := 0;
    for i := 1 to 10 do
        begin
          min := a[i];
          nmin := i;
          for j := i to 10 do
              if a[j] < min then
                 begin
                   min := a[j];
                   nmin := j;
                 end;
          a[nmin] := a[i];
          a[i] := min;
        end;
    for i := 1 to 10 do
        Memo2.Lines[i-1] := IntToStr(a[i]);
end;

4. Запустіть проект на виконання і проаналізуйте результати виконання. У разі появи помилок, виправте їх і збережіть зміни.

• Створення проекту з використанням мови Python

1. Відкрийте середовище програмування мовою Python, створіть новий файл і збережіть його під іменем Упорядкування.
2. Реалізуйте проект, додавши в нього можливість сортувати і за спаданням. Скористайтеся поданим програмним кодом. 

a = []
for i in range(10):
    a.append(int(input('Введіть елемент масиву: ')))
print('Вхідний список: ', a)
a.sort()
print('Впорядкований список за зростанням: ', a)
a.sort(reverse = True)
print('Впорядкований список за спаданням: ', a)

3. Зверніть увагу на методи сортування масивів (списків) мовою Python. Проаналізуйте результати роботи програми.

• Вправа 3. Створіть проект Прогноз погоди, у якому за поданою таблицею (списком) температури протягом тижня знаходять найбільший і найменший показники температури.
• Створення проекту з використанням мови Python

1. Відкрийте середовище програмування мовою Python, створіть новий файл і збережіть його під іменем Прогноз погоди.
2. У вікні редактора коду запишіть команди випадкового генерування елементів масиву (списку) та виведення елементів списку у вікні виконання проекту, пошуку найбільшого й найменшого елементів списку.

import random
a = []
for i in range(10):
    a.append(round(random.randint(-100, 100) * 0.5, 2))
print('Вхідний масив значень температури протягом тижня: ', a)
a.sort()
print('Відсортований масив значень температури протягом тижня (за зростанням): ',a)
print('max = {0} градусів\nmin = {1} градусів'.format(a[-1], a[0]))

3. Запустіть проект на виконання і перевірте, чи відповідають умові завдання отримані результати. Якщо є помилки, виправте їх, збережіть зміни.

Виконуємо самостійно

• Завдання 1. Створіть проект у середовищі Lazarus під назвою Фігурне катання, у якому визначається загальна оцінка якості виконання елемента. У фігурному катанні загальна оцінка якості виконання елемента обчислюється за такими правилами: відкидаються найвища і найнижча оцінки, а з решти обчислюється середнє арифметичне.
  
  
  Проаналізуйте програмний код, наведений нижче і скористайтеся ним для реалізації проекту.

procedure TForm1.FormCreate(Sender: TObject);
var i: Integer;
begin
   For i := 1 to 10 do StringGrid1.Cells[i-1, 0] := 'Суддя ' + IntToStr(i);
end;

procedure TForm1.Button1Click(Sender: TObject);
var a: array[1..10] of Real;
    i: Integer;
    c, s: real;
    prap: boolean;
begin
  ListBox1.Clear;
  // заповнення масиву і відображення у таблиці
  Randomize;
  For i := 1 to 10 do
      begin
        a[i] := Random(20)*0.5;
 StringGrid1.Cells[i-1, 1] := FloatToStr(a[i]);
      end;
  // впорядкування масиву за спаданням
  Repeat
        prap := False;
 For i := 1 to 9 do
     If a[i] < a[i+1] Then
               begin
      c := a[i];
                    a[i] := a[i+1];
                    a[i+1] := c;
      prap := True
               end;
        For i := 1 to 10 do
     StringGrid1.Cells[i-1, 2] := FloatToStr(a[i]);
  Until prap = False;
  ListBox1.Items.Add('Найбільша оцінка: ' + FormatFloat('0.##', a[1]) + ' балів.');
  ListBox1.Items.Add('Найменша оцінка: ' + FormatFloat('0.##', a[10]) + ' балів.');
  For i := 2 to 9 do
     s := s + a[i];
  ListBox1.Items.Add('Середнє арифметичне: ' + FormatFloat('0.##', s/8) + ' балів.');
end;

• Завдання 2. Створіть у середовищі Lazarus проект під назвою Результати забігу, у якому дано список результатів забігу на 100 метрів восьми спортсменів. Необхідно визначити три кращі результати і вивести разом з іменами спортсменів.
  
  
  Проаналізуйте програмний код і використайте його для реалізації проекту.

procedure TForm1.Button1Click(Sender: TObject);
var athletes_results: array[1..8] of Real;
    athletes_name: array[1..8] of String;
    i: Integer;
    c: Real;
    n: String;
    Prap: Boolean;
begin
  // очищення таблиці результатів
  For i := 1 to 8 do StringGrid1.Cols[i-1].Clear;
  // заповнення таблиці випадковими значеннями результатів забігу спортсменів
  Randomize;
  For i := 1 to 8 do
    begin
       athletes_results[i] := (Random(100-20) + 100)/10.5; { нумерація елементів масиву з одиниці, а стовпців таблиці StringGrid1 — з нуля, тому і-й елемент масиву А виводиться в (і-1)-й стовпець таблиці}
       athletes_name[i] := IntToStr(i) + ' спортсмен';
       StringGrid1.Cells[i-1,0] := athletes_name[i];
       StringGrid1.Cells[i-1,1] := FormatFloat('0.###', athletes_results[i]);
    end;
   // сортування вибором максимального елемента
   n := '';
   Repeat
        Prap := False;
 For i := 1 to 7 do
     If athletes_results[i] < athletes_results[i+1] Then
               begin
                    // поміняти у масиві athletes_results[1..8] місцями сусідні результати спортсменів
                    c := athletes_results[i];
                    athletes_results[i] := athletes_results[i+1];
                    athletes_results[i+1] := c;
                    // поміняти у масиві athletes_name[1..8] місцями сусідні імена спортсменів відповідно до зміни результатів
                    n := athletes_name[i];
                    athletes_name[i] := athletes_name[i+1];
                    athletes_name[i+1] := n;

                    Prap := True
               end;
   Until Prap = False;
   // виведення результатів, не враховуються однакові результати
   ListBox1.Clear;
   ListBox1.Items.Add('Результати змагань:');
   For i := 1 to 3 do
       ListBox1.Items.Add(IntToStr(i) + ' місце: ' + FormatFloat('0.###', athletes_results[9-i]) + ' секунд, ' + athletes_name[9-i]);
end;

• Завдання 3. Використовуючи мову програмування Python створіть проект гри Відгадай число. Користувач вводить число, яке, на його думку, може міститися в лінійній таблиці з 10 цілих чисел, що генеруються випадково від 1 до деякого випадкового цілого числа. Якщо таке число відгадане, то гра припиняється й виводиться повідомлення про перемогу; якщо після 5 спроб число не вгадують, то гра припиняється з повідомленням про невдалі спроби. У грі можуть бути підказки, які спрямовуватимуть користувача на правильний вибір значення.

1. Відкрийте середовище програмування мовою Python, створіть новий файл і збережіть його під іменем Відгадай число.
2. У вікні редактора коду введіть команди.

import random
a = []
for i in range(10):
    a.append(random.randint(1, 20))
number = random.choice(a)
guessesTaken = 0
myName = input('Привіт! Як тебе звати? ')
print('Отже, ' + myName + ', я задумав число від 1 до 20.')
while guessesTaken < 6:
    guess = int(input('Спробуй відгадати. '))
    guessesTaken += 1
    if guess < number:
        print('Твоє число менше від задуманого.')
    elif guess > number:
        print('Твоє число більше за задумане.')
    else:
        break
if guess == number:
    print('Дуже добре, ' + myName + '! Для відгадування тобі знадобилося ' + str(guessesTaken) + ' разів!')
else:
    print('Ні. Число, яке я задумав: ' + str(number))

3. Запустіть проект на виконання і проаналізуйте результат.
4. Змініть правила гри, наприклад, зменшіть/збільшіть кількість спроб для вгадування задуманого числа. Реалізуйте ситуацію, коли число можна вгадати з першої спроби.

• Завдання 4. Створіть проект у середовищі Lazarus, у якому дано одновимірний масив із 6 елементів і визначається, чи є масив упорядкованим за зростанням або спаданням. Якщо масив не впорядковано, вивести відповідь: "Невпорядкована послідовність". Блок-схему алгоритму розв'язування завдання показано на малюнку.
  

1. Створіть новий проект. Розмістіть на формі компоненти і налаштуйте їхні властивості згідно із скріншотами. 
   
   
   
2. У процедурі обробки події OnCreate для форми запрограмуйте виведення індексів елементів масиву до зафіксованого рядка заголовків стовпців.

procedure TForm1.FormCreate(Sender: TObject);
var i: Integer;
begin
   For i := 1 to 6 do StringGrid1.Cells[i-1, 0] := IntToStr(i);
end;

3. Опишіть масив А: array[1..6] of Integer; як глобальний.

var
  Form1: TForm1;
  A: array[1..6] of Integer;

implementation

4. Створіть процедуру обробки події для кнопки Ввести значення і запрограмуйте введення елементів масиву з клавіатури в ході виконання програми.

procedure TForm1.Button1Click(Sender: TObject);
var i: Integer;
begin
   For i := 1 to 6 do
       begin
            A[i] := StrToInt(InputBox('Уведіть значення елемента ','A[' + IntToStr(i) + ']:', '0'));
            StringGrid1.Cells[i-1, 1] := IntToStr(A[i]);
       end;
end;

5. Створіть процедуру обробки події для кнопки Чи упорядкований масив? Додайте до оператора if, який перевіряє стан прапорцевої змінної prap, гілку else для перевірки послідовності на спадання.  

procedure TForm1.Button2Click(Sender: TObject);
var i: Integer;
    Prap, Prap2: Boolean;
begin
    Prap := True;
    For i := 2 to 6 do
        If A[i] <= A[i-1] Then Prap := False;
    If Prap then
      Label1.Caption := 'За зростанням'
    else
        begin
          Prap2 := True;
          For i := 2 to 6 do
              If A[i] >= A[i-1] Then Prap2 := False;
          if Prap2 then
             Label1.Caption := 'За спаданням'
          else
             Label1.Caption := 'Неупорядкована послідовність';
        end;
end;

6. Алгоритм розв'язування завдання наступний: перебрати усі елементи з другого до останнього. Якщо поточний елемент менший за попередній, то прапорцевій змінній prap присвоїти значення False. Якщо після перегляду масиву прапорцева змінна має значення False - це означає, що послідовність не була зростаючою.
7. Перевірте роботу програми для послідовності, упорядкованої за зростанням, за спаданням, неупорядкованої послідовності. Збережіть зміни.

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

• Опрацювати підручник: §36 с. 198-202 (Інформатика, 9 клас, автори: Бондаренко О. О., Ластовецький В. В., Пилипчук О. П., Шестопалов Є. А.)