mozok.click » Інформатика » Алгоритми впорядкування елементів масиву
Інформація про новину
  • Переглядів: 3259
  • Автор: admin
  • Дата: 14-09-2017, 06:39
14-09-2017, 06:39

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

Категорія: Інформатика

Під час опрацювання сукупностей даних часто виникає потреба впорядкувати ці дані за деякою ознакою. Числові дані можна відсортувати за величиною (наприклад, створити рейтинг навчальних досягнень), рядкові дані — в алфавітному порядку (упорядкувати список учнів).

Сортування елементів масиву — це впорядкування їх за деякою ознакою.

Розглянемо два найпростіші методи сортування масиву. Нехай потрібно впорядкувати масив X: array[1..10] of Real; за неспаданням: X[1] < X[2] < ... < X[10].

Сортування вибором максимального елемента

Цей метод заснований на тому, що під час кожного проходу циклу переглядається частина масиву завдовжки К елементів. Наприклад, для масиву Х[1..10] під час першого проходу К = 10.

Алгоритм сортування за зростанням (рис. 36.1):

• відшукати максимальний з елементів Х[1]..Х[10];

• максимальний елемент поміняти місцями з Х[10];

• відшукати максимальний елемент із частини масиву Х[1]..Х[9];

• максимальний елемент із цієї частини поміняти місцями з Х[9];

<...>

• максимальний елемент із частини масиву Х[1]..Х[2] поміняти місцями з Х[2].



Вигляд масиву Х[1..10] на кожному кроці сортування за неспаданням вибором максимального елемента зображено на рис. 36.1.

Сортування обміном (метод бульбашки)

Метод бульбашки ґрунтується на порівнянні та перестановці сусідніх чисел.

Алгоритм сортування за зростанням:

1) послідовно порівнювати пари сусідніх елементів Х[і] і Х[і + 1] (i:1..N - 1), і, якщо Х[і] > Х[і + 1], то поміняти їх місцями і логічній змінній Prap надати значення True. У результаті першого перегляду елементів масиву на N-му місці буде найбільший з усіх елементів, тобто він, як бульбашка, «спливе» вгору;

2) виконати такі самі дії з елементами від 1 до (N - 2): на (N - 1)-му місці з’явиться найбільший серед (N - 1) елементів і т. д.

Змінна Prap: Boolean виконує роль прапорця. Вона отримує значення True за умови, що відбулась хоча б одна перестановка сусідніх елементів. Якщо значення Prap не змінилось, це означає, що елементи масиву вже впорядковані і подальший перегляд послідовності значень не потрібний (рис. 36.2):


Дано масив А[1..10], значення якого задані випадковим чином і містяться в діапазоні від 0 до 19. Упорядкувати масив за спаданням (А[1] > А[2] > ... > А[10]) методом бульбашки.

Для покрокового аналізу ходу впорядкування додамо на форму компонент БїгіпдСгїС і налаштуємо його властивості таким чином:

Виведення заголовків стовпців запрограмуємо в процедурі обробки події ОпСгеаїе (див. § 35). Алгоритм упорядкування масиву реалізуємо в процедурі обробки події ОпСІіск командної кнопки Виїїоп1.

Опис величин. Опишемо змінні, потрібні для реалізації алгоритму: var А: array[1..10] of Integer; i, c, j: Integer; Prap: Boolean;

Очищення рядків таблиці StringGridl:

For i := 1 to 10 do StringGridl.Rows[i].Clear;

Задавання значень елементів масиву А випадковим чином: Randomize;

For i := 1 to 10 do begin

A[i] := Random(20);

StringGrid1.Cells[i - 1, 1] := IntToStr(A[i]); end;

Упорядкування масиву A[1..10] за спаданням методом бульбашки.

До тіла циклу Repeat додамо оператори для виведення елементів масиву А на кожному кроці сортування: j := 1;  // номер кроку сортування

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;

j := j+1;

{ виведення масиву; j — номер кроку сортування і рядка таблиці } For i := 1 to 10 do

StringGrid1.Cells[i - 1, j] := IntToStr(A[i]);

Until Prap = False;

Перевірка роботи програми. Запустимо програму на виконання і проаналізуємо хід сортування.

Для різних наборів значень елементів масиву А може знадобитися різна кількість кроків сортування (у випадку на рис. 36.2 знадобилось 7 кроків).

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

1. У чому полягає сутність сортування масиву методом вибору максимального елемента?

2. У чому полягає сутність сортування масиву методом бульбашки?

3. На якому місці в масиві може міститися його найбільший елемент, якщо масив не впорядковано?

4. На якому місці в масиві може міститися його найменший елемент, якщо масив упорядковано за зростанням; за спаданням?

5. Для кожної пари сусідніх елементів масиву А виконується операція

S := S + Byte (A[i] >= A[i + 1]) { Byte (True) = 1; Byte (False) = 0 }

Початкове значення S дорівнює 0. Визначте, чому дорівнює кінцеве значення S, якщо вхідний масив: а) було впорядковано за зростанням; б) було впорядковано за спаданням; в) не було впорядковано.

6. Дано список результатів забігу на 100 м восьми спортсменів. Складіть програму для визначення трьох кращих результатів.

Вправа 36

Дано одновимірний масив із 6 елементів. Визначити, чи є масив упорядкованим за зростанням або спаданням. Якщо масив не впорядковано, вивести відповідь «Невпорядкована послідовність». Блок-схему алгоритму розв’язування завдання наведено на рис. 1.

1) Створіть новий проект. Змініть значення властивості Caption форми, додайте на форму компонент Label для виведення відповіді на запитання завдання і компонент Button згідно з рис. 2.

2) Розмістіть на формі компонент БїгїпдСгїС і налаштуйте його властивості таким чином:

У процедурі обробки події OnCreate для форми запрограмуйте виведення індексів елементів масиву до зафіксованого рядка заголовків стовпців.

3) Опишіть масив A: array[1..6] of Integer; як глобальний. У процедурі обробки події onclick для кнопки Ввести значення запрограмуйте введення елементів масиву з клавіатури в ході виконання програми.

4) Створіть процедуру обробки події onclick для кнопки Чи упорядкований масив?. Опишіть змінні, які будуть необхідні для розв’язування завдання:

var i: Integer; Prap: Boolean;

Перевірте, чи є масив упорядкованим за неспаданням.

Алгоритм розв’язування завдання: перебрати всі елементи з другого до останнього. Якщо поточний елемент менший за попередній, то прапорцевій змінній Prap присвоїти значення False. Якщо після перегляду масиву прапорцева змінна має значення False — це означає, що послідовність не була неспадною.

Prap := True;

For i := 2 to 6 do

If A[i] <= A[i - 1] Then Prap := False;

If Prap Then Labell.Caption := 'За неспаданням';

5) Користуючись рис. 1, додайте до оператора If, який перевіряє стан прапорцевої змінної Prap, гілку Else для перевірки послідовності на незростання.

6) Перевірте роботу програми для послідовності, упорядкованої за неспаданням; за незростанням; неупорядкованої послідовності. Збережіть проект у папці Вправа 36. Завершіть роботу за комп’ютером.

Комп'ютерне тестування

Виконайте тестове завдання 36 із автоматичною перевіркою на сайті «Інтерактивне навчання».


Практична робота 12

Складання і виконання алгоритмів знаходження сум і кількостей значень елементів табличних величин за заданими умовами в середовищі програмування

Завдання: створити проект для розв’язання задачі.

Дано таблицю кількості опадів протягом року за місяцями:

Визначити:

а) кількість опадів за рік;

б) місяць, в якому кількість опадів була найменшою;

в) місяць, в якому кількість опадів була найбільшою;

г) місяці, в які кількість опадів була менша від 40, та кількість таких місяців.

Обладнання: комп’ютер зі встановленим середовищем програмування Lazarus.

Хід роботи

Під час роботи з комп’ютером дотримуйтеся правил безпеки.

І. Розміщення елементів керування на формі

1. Створіть новий проект. Розробіть інтерфейс програми згідно

з рисунком. Поле списку ListBoxI призначене для виведення відповідей.

2. Налаштуйте властивості елементів керування згідно з рисунком.

II. Розробка програмного коду

3. Опишіть масиви-константи для збереження назв місяців і кількостей опадів у інтерфейсному блоці як глобальні: const month: array[1..12] of String = ('січень', 'лютий', 'березень', 'квітень', 'травень', 'червень', 'липень', 'серпень', 'вересень', 'жовтень', 'листопад', 'грудень');

Mas: array[1..12] of Integer = (54, 13, 30, 15, 40, 32, 10, 20, 46, 60, 56, 38); 4. У процедурі обробки події OnCreate для форми запрограмуйте виведення назв місяців до рядка заголовків стовпців, а значення елементів масиву кількостей опадів — до першого рядка таблиці.

5. Створіть процедуру обробки події onclick для командної кнопки Кількість опадів за рік, мм, користуючись алгоритмом знаходження суми елементів масиву.

6. Створіть процедуру обробки події onclick для командної кнопки Найсухіший місяць, користуючись алгоритмом визначення найменшого елемента масиву.

7. Створіть процедуру обробки події onclick для командної кнопки Найвологіший місяць, користуючись алгоритмом визначення найбільшого елемента масиву.

8. Створіть процедуру обробки події для кнопки Місяці, в які кількість опадів менша від 40, користуючись алгоритмом визначення кількості елементів із заданою властивістю.

9. Додайте до процедури обробки події для кнопки Місяці, в які кількість опадів менша від 40 мм оператори для обчислення К — кількості елементів масиву mas, що задовольняють умові, і виведення значення К у поле списку ListBox1.

10. Додайте до процедури обробки події для кнопки Кількість опадів за рік, мм оператори для обчислення середнього арифметичного елементів масиву mas і виведення цього значення в поле списку ListBox1.

III. Тестування проекту

11. Перевірте роботу програми.

12. Збережіть проект у папці Практична робота 12. Завершіть роботу за комп’ютером.

Зробіть висновок: як застосовувати типові алгоритми опрацювання одновимірних масивів для розв’язування задач.

 

Це матеріал з підручника Інформатика 9 клас Бондаренко

 






^