Сортування одновимірного масиву і пошук даного числа у впорядкованому масиві

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

Існує більше 10 різноманітних методів сортування одновимірного масиву. Одні з них виконуються швидше, інші повільніше, одні – більш складні за своєю логічною структурою, інші – простіші. Ми розглянемо один з методів сортування одновимірного масиву – метод вибору.

Пояснимо сутність цього методу на прикладі. Нехай нам потрібно впорядкувати за зростанням такий одновимірний масив з 6 елементів (табл. 2.5, рядок 0):

 

Таблиця 2.5. Упорядкування масиву методом вибору

№	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]

 

На першому кроці визначимо значення найменшого елемента в усьому масиві (a[4] = 2) і обміняємо його зі значенням першого елемента. Одержуємо масив у рядку 1, в якому найменший елемент зайняв своє місце. На другому кроці визначимо значення найменшого елемента серед усіх елементів масиву, крім першого, (a[6] = 4) і обміняємо його зі значенням другого елемента. Одержуємо масив у рядку 2, в якому перші 2 елементи зайняли своє місце. На третьому кроці визначимо значення найменшого елемента серед усіх елементів масиву, крім перших двох, (a[5] = 6) і обміняємо його зі значенням третього елемента. Одержуємо масив у рядку 3, в якому перші 3 елементи зайняли своє місце. Повторивши аналогічні дії ще 2 рази разів, одержуємо масив, впорядкований за зростанням.

Звертаємо вашу увагу: хоча масив має 6 елементів, достатньо 5 разів знайти найменше значення елементів з ще не впорядкованої частини масиву і обміняти його місцями із значенням першого з ще не впорядкованої частини масиву елемента. На останньому кроці не лише 5-й, а й 6-й елемент масиву займає своє місце у впорядкованій частині масиву, і таким чином увесь масив стає впорядкованим.

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

Відповідна процедура, в якій реалізується цей метод, виглядає так:

procedure TForm1.Button2Click(Sender: TObject);

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

Begin

for i:= 1 to 10 do

a[i]:= StrToInt(Memo1.Lines[i-1]);

for i:= 1 to 9 do

Begin

min:= a[i]; nmin:= i;

for j:= i+1 to 10 do

if a[j] < min Then

Begin

min:= a[j]; nmin:= j;

end;

a[nmin]:= a[i];

a[i]:= min;

end;

Memo2.Lines.Clear;

for i:= 1 to 10 do

Memo2.Lines.Append (IntToStr(a[i]))

end;

 

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

Якщо масив невпорядкований, то її можна розв’язати методом, розглянутим вище. При реалізації цього методу, якщо даного числа в масиві немає, то для з’ясування цього факту потрібно буде порівняти дане число зі значеннями усіх елементів масиву. І якщо кількість елементів масиву велика, наприклад, 1 000, то й число порівнянь (а значить і час виконання проекту) буде відповідним.

Якщо ж масив впорядкований, то можна з’ясувати, чи є дане число в масиві, іншим способом, значно ефективнішим. Пояснимо його на прикладі. Нехай маємо впорядкований за зростанням масив з 10 чисел: 2, 5, 8, 12, 13, 16, 17, 20, 22, 30 і деяке дане число х. Порівняємо це число із значенням елемента масиву, який знаходиться посередині масиву (з числом 13). Якщо дане число х дорівнює 13, то воно в масиві є, якщо ні, то з’ясуємо, чи більше дане число числа 13 (х>13). Якщо так, то його потрібно шукати тільки серед правої половини масиву, якщо ні, то тільки серед лівої половини масиву. Таким чином область пошуку звужується вдвічі. На наступному кроці поступаємо так саме: порівнюємо дане число із значенням елемента масиву, який знаходиться посередині тієї частини масиву, яка залишилися для пошуку. Знову або дане число дорівнює значенню цього елемента масиву, або залишаємо для пошуку або ліву, або праву половини тієї частини масиву, що залишилася, тобто область пошуку знову зменшується вдвічі.

Такий метод пошуку є значно ефективнішим, ніж попередній, бо значно швидше приводить до результату, особливо для великих N (максимум за [log₂N] +1 кроків, де N – кількість елементів у масиві, а квадратними дужками тут позначена ціла частина числа).

Такий метод пошуку заданого числа в одновимірному масиві називається методом половинного (бінарного) пошуку.

Відповідна процедура, в якій реалізується цей метод для впорядкованого масиву з 10 цілих чисел, виглядає так:

procedure TForm1.Button1Click(Sender: TObject);

var a: array [1..10] of Integer; i, x, left, right, m: Integer; f: Boolean;

Begin

for i:= 1 to 10 do

a[i]:= StrToInt(Memo1.Lines[i-1]);

x:= StrToInt(Edit1.Text);

left:= 1; // Початковий номер елемента тієї частини масиву, де відбуватиметься пошук

right:= 10; // Кінцевий номер елемента тієї частини масиву, де відбуватиметься пошук

f:= false; // Задане число в масиві поки що не знайдене

while (left <= right) and not f do

Begin

m:= (left + right) div 2; // Номер елемента посередині тієї частини масиву, де далі продовжуватиметься пошук

if x > a[m]

then left:= m+1 // Змінюється початковий номер елемента тієї частини масиву, де відбуватиметься пошук

else if x < a[m]

then right:= m-1 // Змінюється останній номер елемента тієї частини масиву, де відбуватиметься пошук

else f:= true; // Число в масиві знайшлося

end;

If f

then Edit1.Text:= 'Число в масиві є'

else Edit1.Text:= 'Числа в масиві немає';

end;

Цікаві факти з історії

Метод половинного поділу використовували в своїх логічних міркуваннях, класифікаціях, методах розв’язування задач ще стародавні греки. Вони називали цей метод дихотомією (грец. δῐχῆ – навпіл, τομή – поділ). Може й ви використовували цей метод у грі "Відгадай задумане число".

Перевірте себе

1. º Що таке одновимірний масив?

2. º З чого складається ім’я елемента масиву?

3. · Що може використовуватись як номер елемента масиву?

4. * При складанні проектів для розв’язуванні яких задачах зручно використовувати масиви?

5. · Як записати змінну типу одновимірний масив у рядку var?

6. º Яким може бути діапазон номерів елементів масиву?

7. · Назвіть та охарактеризуйте відомі вам властивості багаторядкового поля.

8. · Назвіть та поясніть відомі вам стандартні методи багаторядкового поля.

9. · Як увести числа в багаторядкове поле до запуску проекту?

10. · Опишіть різні способи визначення, чи зустрічається задане число серед значень елементів масиву.

11. · Опишіть послідовність дій для визначення найбільшого значення серед значень елементів масиву.

12. º Який масив називається динамічним? Як описується динамічний масив у рядку var?

13. ·Поясніть, у чому полягають відмінності між статичним та динамічним масивами.

14. · Поясніть сутність методу вибору при сортуванні масиву.

15. · Поясніть сутність методу половинного (бінарного) пошуку даного числа в одновимірному масиві.

16. * Поясніть, у чому перевага пошуку заданого елемента у впорядкованому масиві порівняно з не впорядкованим. Наведіть приклади такого пошуку у вашій навчальній діяльності.

 

Виконайте завдання

1. º Складіть таблицю виконання фрагмента програми та визначте значення змінної dob після його завершення для масиву, значеннями елементів якого є числа 2; -3,5; 1,2; 0,25; -4:

dob:= 1;

for i:= 1 to 5 do

dob:= dob * a[i];

2. (ДЗ) º Cкладіть таблицю виконання фрагмента програми та визначте значення змінної sum після його завершення для масиву, значеннями якого є числа 0,2; -1,5; 2; -1,4:

sum:= 0;

for i:= 1 to 4 do

if a[i] mod 2 =0 then sum:= sum + a[i]*a[i];

3. · Запишіть рядок оголошення змінних типу одновимірний масив:

а) масив змінних цілого типу з іменем х та діапазоном номерів від 1 до 50;

б) масив змінних дійсного типу з іменем mas та діапазоном номерів від 10 до 35;

в) масив змінних цілого типу з іменем tab та діапазоном номерів від -7 до 12.

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

5. (ДЗ) º Запишіть фрагмент програми, що здійснює виведення вже відомих значень елементів масиву з 11 чисел у рядки багаторядкового поля.

6. º Створіть проект, в якому потрібно сформувати масив з 10 цілих чисел, що знаходяться в рядках багаторядкового поля, знайти середнє арифметичне значень елементів масиву та вивести результат у напис. Створіть у власній папці папку Проект 2.11.6 і збережіть у ній проект.

7. · Створіть проект, в якому потрібно сформувати масив з 12 дійсних чисел, що знаходяться в рядках багаторядкового поля, збільшити значення кожного елемента масиву в 3 рази і вивести нові значення в інше багаторядкове поле. Створіть у власній папці папку Проект 2.11.7 і збережіть у ній проект.

8. (ДЗ) · Створіть проект, в якому потрібно сформувати масив з 9 чисел, що знаходяться в рядках багаторядкового поля, зменшити значення кожного елемента масиву на 5 і вивести нові значення в інше багаторядкове поле. Створіть у папці Мої документи папку Проект 2.11.8 і збережіть у ній проект.

9. · Випускник 11-го класу може отримати грамоту за особливі успіхи у навчанні з певного предмету, якщо його річна оцінка з цього предмету – 12. Річні оцінки з інформатики учнів класу введені у багаторядкове поле. Створіть проект для визначення кількості грамот, які можуть отримати учні цього класу. Створіть у власній папці папку Проект 2.11.9 і збережіть у ній проект.

10. (ДЗ) · Створіть проект, в якому потрібно сформувати масив з 7 цілих чисел, що знаходяться в рядках багаторядкового поля, визначити суму парних чисел серед значень елементів цього масиву і вивести результат у напис. Створіть у папці Мої документи папку Проект 2.11.10 і збережіть у ній проект.

11. · Створіть проект, в якому потрібно сформувати масив з 9 цілих чисел, що знаходяться в рядках багаторядкового поля, визначити, чи зустрічаються серед значень елементів цього масиву числа, кратні числу 3, і вивести результат у напис. Створіть у власній папці папку Проект 2.11.11 і збережіть у ній проект.

12. · Створіть проект, в якому потрібно сформувати масив з 10 дійсних чисел, що знаходяться в рядках багаторядкового поля, визначити найменше серед значень елементів цього масиву і обміняти його місцями з першим елементом масиву. Отриманий масив вивести в інше багаторядкове поле. Створіть у власній папці папку Проект 2.11.12 і збережіть у ній проект.

13. * Створіть проект, в якому потрібно сформувати масив з 10 дійсних чисел, що знаходяться в рядках багаторядкового поля, визначити найбільше серед значень елементів цього масиву і порахувати, скільки елементів з таким значенням зустрічається в масиві. Отриманий результат вивести в напис. Створіть у власній папці папку Проект 2.11.13 і збережіть у ній проект.

14. (ДЗ) · Створіть проект, в якому потрібно сформувати масив з 9 дійсних чисел, що знаходяться в рядках багаторядкового поля, визначити найбільше серед значень елементів цього масиву і обміняти його місцями із значенням елемента масиву, що знаходиться посередині масиву. Отриманий масив вивести в інше багаторядкове поле. Створіть у папці Мої документи папку Проект 2.11.14 і збережіть у ній проект.

15. · Створіть проект, в якому потрібно сформувати динамічний масив з дійсних чисел, що знаходяться в рядках багаторядкового поля, визначити середнє арифметичне значення елементів цього масиву і знайти елементи, які більші за середнє арифметичне значення. Для зберігання результатів використайте динамічний масив. Створіть у власній папці папку Проект 2.11.15 і збережіть у ній проект.

16. * Створіть проект, в якому потрібно сформувати масив з дійсних чисел, що знаходяться в рядках багаторядкового поля, відсортувати його і знайти кількість різних значень елементів масиву. Створіть у власній папці папку Проект 2.11.16 і збережіть у ній проект.

17. * Створіть проект, в якому потрібно сформувати два масиви з дійсних чисел, що знаходяться в рядках багаторядкових полів, і визначити, чи співпадають ці масиви. Створіть у власній папці папку Проект 2.11.17 і збережіть у ній проект.

 

 

Практична робота № 11

«Опрацювання одновимірних масивів»

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

 

1. Відкрийте середовище розробки Turbo Delphi 2006.

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

а) Розмістіть на формі потрібні елементи керування: багаторядкові поля, написи, кнопки.

б) Складіть обробник події OnClick першої кнопки, виконання якого призведе до виведення у напис середньої температури за тиждень.

в) Складіть обробник події OnClick другої кнопки, виконання якого призведе до визначення, скільки разів на тиждень температура була вище нуля і виведення результату у напис.

г) Складіть обробник події OnClick третьої кнопки, виконання якого призведе до сортування значень температур і визначення, чи є в масиві однакові значення, виведення відсортованого масиву у багаторядкове поле, повідомлення про наявність однакових елементів – у напис.

д) Виконайте складені процедури і переконайтеся, що результати їх роботи правильні.

3. Створіть у власній папці папку Практична 11 і збережіть у ній проект.