69112

Одномірні масиви. Поняття масиву та його властивості. Базові операції обробки одновимірних масивів

Лекция

Информатика, кибернетика и программирование

Характерною ознакою простих типів даних є те, що вони атомарні, тобто не містять як складові елементи дані інших типів. Типи даних, що не эадовольняють зазначеній властивості, називаються структурованими. У мові Раsсаl означено такі структуровані типии: масиви, рядки, множини, записи та файли.

Украинкский

2014-09-30

214.5 KB

5 чел.

Лекція 21. Тема: Одномірні масиви.Поняття масиву та його властивості.

                             Базові операції обробки одновимірних масивів.

План:

1. Одновимірні масиви

2. Поняття масиву та його властивості

3. Базові операції обробки одновимірних масивів

4. Сортування масиву

5. Масиви як параметри

1. Одновимірні масиви

Характерною ознакою простих типів даних є те, що вони атомарні, тобто не містять як складові елементи дані інших типів. Типи даних, що не эадовольняють зазначеній властивості, називаються структурованими. У мові Раsсаl означено такі структуровані типии: масиви, рядки, множини, записи та файли. Структурований тип характеризується множиною елементів, з яких складаються дані цього типу. Елементи структурованого типу називаються компонентами (компоненти масивів найчастіше називають елементами масивів). Отже, змінна або константа структурованого типу завжди містить декілька компонентів. У свою чергу, кожний компонент може належати до структурованого типу, що дозволяє говорити про вкладеність типів. 3 простих елементів даних, або компонентів, більш складні структури утворюються двома способами: об'єднанням однорідних елементів даних з метою створення масивів та об'єднанням різнорідних елементів даних з метою створення записів.

Потреба у масивах виникає тоді, коли в оперативній пам'яті зберігається велика, але визначена кількість однотипних даних. Наприклад, можна задати масив щоденних значень температури повітря протягом місяця з метою визначення середньої температури або масив логічних значень, що зображуватиме наявність квитків на кіносеанс на всі місця у кінозалі. Розрізняють одновимірні та багатовимірні масиви. Зокрема, масив температур є одновимірним, а масив квитків - двовимірним. Одновимірні масиви розглядаються в розділ 7.1, а багатовимірні -в розділі 7.2. У розділі 7.3 розглянуто рядки, які є різновидом одновимірних масивів.

2. Поняття масиву та його властивості

Дано означення одновимірного масиву, розрізняючи тип масиву та дані цього типу. Терміном «масив» надалі позначатимемо саме дані деякого типу масиву.

Одновимірний масив – це послідовність однотипних даних.

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

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

розмірність;

базовий тип;

індексний тип;

множину значень індексу.

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

З точки зору математики одновимірний масив – це вектор. Наприклад, масив або вектор А, що має п’ять елементів, які записують у математиці у вигляді індексованих змінних а1, а2, а3, а4, а5, можна зобразити значеннями цих змінних у сусідніх ділянках оперативної пам’яті.

     

А

 

Напрям збільшення адрес пам’яті

Ідентифікатор типу масиву можна оголосити в розділі type з використанням такого синтаксису:

<ім’я типу масиву> = array [<нижній індекс>..<верхній індекс>] of <тип елементів>;

У цьому оголошенні array, of – зарезервовані слова, що перекладаються як «масив», «з»; <ім’я типу масиву> - деякий ідентифікатор; <тип елементів> - будь-який тип даних, окрім файлового типу; <нижній індекс> і <верхній індекс> - константи, що визначають межі діапазону допустимих значень. Розмірність масиву дорівнює величіні                      ord (<верхній індекс>)-ord (<нижній індекс>)+1.

У розділі varоголошується змінна, що матиме раніше оголошений тип масиву:

<ім’я масиву> : <ім’я типу масиву>

Синтаксис мови Pascal дає можливість поєднати у розділі var оголошення змінної-масиву із визначенням її типу. При цьому ідентифікатор типу масиву не оголошується:

<ім’я масиву> : array [<нижній індекс>..<верхній індекс>] of <тип елементів>;

Нагадаємо, що обсяг пам'яті, яка виділена для зберігання всіх оголошених у розділах  var змінних, не повинен перевищувати 64 Кбайт. Тому є обмеження на максимальну кількість елементів у масиві. Так, максимальна кількість елементів типу integer не може перевищувати 32 767, а елементів типу real - 10 922.

Оголосити змінну типу масиву можна із використанням такого синтаксису:

<ім'я масиву> : аrrау [<тип індексів>] оf <тип елементів>;

Тут <тип індексів> - цілі типи shortint або byte, для яких кількість допустимих значень становить 256, або оголошений в розділі tуре перелічуваний тип. Як типи індексів не дозволяється вказувати типи integer, word i longint, оскільки розмір оголошеного в такий спосіб масиву становив би не менш ніж 64 Кбайт.

Приклад 7.1

Наведемо декілька прикладів оголошень одновимірних масивів.

Program ex7_1;

const

  start=10;        {нижній індекс}

  finish=30;        {верхній індекс}

type

  day=(Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday);            {перелічувальний тип}

  vector=array[1..10] of integer;

  STR=array[byte] of char;

var

  a: vector;       {масив 10 змінних типу integer}

  str: STR;      {масив 256 змінних символьного типу}

  digit: array[5..20] of integer;    {масив 16 змінних типу integer}

  float: array[start..finish] of real;    {масив 21 змінної типу real}

  temperature: array[day] of real;

begin

writeln(‘ex7_1’);

end.

Підсумовуючи матеріал розділу 7.1.1, назвемо основні властивості масивів, притаманні як одновимірним, так і багатовимірним масивам:

однорідність — усі елементи належать одному типу;

сталість - вимірність масиву задається під час його оголошення і не змінюється протягом роботи з ним;

рівнодоступність — спосіб доступу до всіх елементів є однаковим;

послідовність розташування — усі елементи масиву розташовані в послідовних комірках оперативної пам'яті;

індексованість — елементи однозначно ідентифікуються своїми індексами;

упорядкованість індексу - індексний тип має бути простим порядковим типом даних.

3. Базові операції обробки одновимірних масивів

Будь-яка обробка масивів здійснюється шляхом виконання операцій над їх елементами. Двома найпростішими операціями над елементами одновимірного масиву є вибір певного елемента та зміна його значення. Для доступу до окремого елемента масиву застосовується операція індексування [ ], за допомогою якої утворюються вирази             <ім'я масиву>[<індексний вираз>]. Елемент масиву є окремою змінною, що  ідентифікується вище зазначеним виразом. Приклад ідентифікації елементів масиву а з індексами 1, 2, ..., 10 та масиву digit з індексами 5, 6, ..., 20 наведено нижче:

а[1], а[2], …, а[10], digit[5], digit[6], ..., digit[20];

Значення елементів масиву змінюються так само, як і значення інших змінних.  Наприклад, для першого елемента масиву а це можна зробити операцією присвоєння a[1]:=5 або операцією введення даних readln (a[1]).

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

введення та виведення масиву;

ініціалізація масиву;

копіювання масиву;

пошук максимального або мінімального елемента;

обчислення узагальнювальних характеристик (сум елементів, їх добутків);

пошук заданого елемента;

перестановка елементів або обмін значеннями між елементами масиву;

вставка та видалення елемента.

Базові операції обробки масивів зручно реалізовувати у вигляді процедур, що згодом можуть бути використані як «архітектурні блоки» при розв’язанні більш складних задач. Серед таких задач найважливішою є задача упорядкування масивів. Декілька алгоритмів розв'язання цієї задачі буде розглянуто в розділі 7.1.3, а решту розділу 7.1.2 присвятимо розгляду базових операцій обробки одновимірних масивів.

Введення та виведення масиву

Мова Pascal не має засобів введення та виведення масиву як цілісного об’єкта, ця операція виконується поелементно за допомогою оператора циклу. під час введення елементів масиву необхідно врахувати те, що їх кількість, тип та тип індексів задаються в оголошенні масиву до початку виконання програми і не можуть бути змінені. Якщо межі індексів масиву точно не відомі, їх добирають так, щоб введена кількість елементів масиву під час виконання програми не перевищувала верхньої межі індексу. Наприклад, після оголошення масиву a: array[1..100] of real кількість елементів, що до нього вводяться, не повинна перевищувати 100.

Приклад 7.2.

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

program ex7_2;

var

  mas: array[1..10] of integer;

  n: integer;       {кількість елементів масиву}

  i: integer;        {поточний індекс}

begin

  writeln (‘Enter number of elements <=10’);

  read (n);

  writeln (‘Enter elements values’);

  for i:=0 to n do

     read (mas[i]);

  writeln (‘Entered array’);

  do

     write (mas[i], ‘ ’);

  writeln;

end.

Ініціалізація масиву

Введення злачень елементів із клавіатури фактично є одним із способів ініціалізації масиву. Іншій спосіб ініціалізації масиву полягає у присвоєнні кожному його елементу деякого значення. Найбільш ефективно ця операція виконується за допомогою оператора for. Наприклад, у наведеному нижче коді десяти елементам масиву arr присвоюються квадрати цілих чисел від 1 до 10.

for i:=1 to 10 do

  arr[i]:=sqr(i);

Одновимірні масиви-константи записуються за наведеним нижче зразком як перелік значень їх елементів:

const a: array[1..5] of integer= (1, 3, 2, -5, 6);

Така ініціалізація еквівалентна серії присвоювань

a[1]:=1;   a[2]:=3;   a[3]:=2;   a[4]:=-5;   a[5]:=6;

Для однотипних масивів А та В як для цілісних об'єктів визначена операція присвоєння А:=В. Однотипність масивів означає, що вони мають однакові типи индексів та однакові типи елементів. У результаті виконання операції присвоєння А:=В значення елементів масиву В присвоюються відповідним елементам масиву А, тобто здійснюється копіювання масиву В до масиву А.

Пошук максимального та мінімального значень

Розкриємо ідею найпростішого способу знаходження максимального значення у масиві (мінімальне значення можна знайти аналогічним способом). Деякій змінній,  скажімо, змінній max, присвоюється значення першого елемента масиву. Після цього виконується цикл, що послідовно порівнює значення кожного елемента, починаючи з другого, із поточним значенням змінної max. Якщо значення елемента перевищує max, воно присвоюється змінній max. Отже, на кожній ітерації циклу у змінній max міститиметься найбільше значення з пройденої частини масиву, а по завершенні циклу змінна max зберігатиме максимальне значення в усьому масиві.

Приклад 7.3

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

Оцінки суддів вважатимемо елементами масиву дійсних чисел. Кількість суддів, а значить, і кількість оцінок вводитимемо до змінної n. Якщо знайдемо максимальний та мінімальний бал (змінні max i min) та накопичену суму балів у змінній sum, то за формулою res=(sum-min-max)/(n-2) можна обчислити шукане значення. Цю задачу розв’язує програма ех7_3. Результати її роботи зображено на рис. 7.1.

program ex7_3;

uses crt;

var

  mark: array[1..10] of real;     {масив оцінок суддів}

  i, n: integer;       {індекс оцінок та їх кількість}

  min, max,      {мінімальна та максимальна оцінки}

  sum,        {сума оцінок суддів}
  result: real;       {середнє арифметичне оцінок}

begin

  clrscr;

  writeln (‘grade defining’);

  writeln (‘enter numbers of arbiters (<=10)’);

  read (n);

  writeln (‘enter’, n, ‘grades’);

  for i:=1 to n do      {цикл уведення масиву оцінок}

     read (mark[i]);

  min:= mark[1];      {ініціалізація мінімальної,}

  max:= mark[1];       {максимальної}

  sum:= mark[1];       {та сумарної оцінки}

  for i:=2 to n do    {пошук мінімальної та максимальної оцінок}

  begin

     if min>mark[i] then min:= mark[i];  {модифікація поточного мінімуму}

     if max<mark[i] then max:= mark[i];  {модифікація поточного максимуму}

     sum:=sum+mark[i];     {підсумовування результатів}

  end;

  writeln (‘margin grades’);

  writeln (‘max=’, max:3:2, ‘min=’, min:3:2);

  result:=(sum-min-max)/(n-2);

  writeln (‘rezult grade=’, result:3:2);

end.

Під час пошуку найбільшого або найменшого елемента масиву може виникнути потреба у визначенні його індексу. Значення індексу, як правило, використовується при подальшій перестановці елементів масиву, їх видаленні тощо. Для розв'язання цієї задачі застосований у прикладі 7.3 алгоритм потрібно модифікувати. А саме, окрім змінної  max (min) слід використати змінну, в якій зберігатимуться значення індексів. Припустимо, це буде змінна nom. Цій змінній спочатку присвоюється індекс першого елемента масиву, а в тілі циклу вона змінює значення тоді, коли і змінна max (min). Отже, змінній  nom присвоюється значення індексу того елемента, який виявився більшим за поточне значення  max (меншим за поточне значення min).

Приклад 7.4.

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

Легко побачити, що час перебування кожного покупця у черзі дорівнює сумарному часу обслуговування його та всіх попередніх покупців. Якщо позначити час обслуговування і-го покупця змінною ti, а час його перебування в черзі — servi, то це значення визначається за формулою servi=t1+t2+…+tі. Можна застосувати рекурентну формулу, згідно з якою час перебування покупця в черзі визначається як сума часу його обслуговування та часу перебування в черзі попереднього покупця: servi= servi-1+ti. Якщо час обслуговування n покупців подати у вигляді n-елементного масиву, то номер покупця з мінімальним часом обслуговування — це індекс мінімального елемента в масиві. Програмне розв'язання цієї задачі наведено нижче.

program ex7_4;

uses crt;

var

  n,        {кількість покупців}

  i: integer;       {поточний індекс покупця}

  t: array[1..10] of real;     {масив часу обслуговування}

  serv: array[1..10] of real;     {масив часу перебування в черзі}

  nom: integer;   {номер покупця з мінімальним часом обслуговування}

  min: real;       {мінімальний час обслуговування}

begin

  clrscr;

  randomize;

  writeln (‘defining the number of buyer with a minimum service time’);

  writeln (‘enter number of buyers (<=10)’);

  readln (n);       {ввести кількість покупців}

  for i:=1 to n do    {генерувати час обслуговування покупців}

     t[i]:=random*10;

  writeln (‘service time of buyers’);

  for i:=1 to n do

  write (t[i]:5:2, ‘ ’);

  writeln;

  serv[1]:=t[i];    {час перебування у черзі першого покупця}

  for i:=2 to n do     {розрахувати час перебування у черзі}

     serv[i]:=serv[i-1]+t[i];

  writeln (‘service time’);

  for i:=1 to n do

     write (serv[i]:5:2, ‘ ’);

  writeln;

  nom:=1;    {пошук покупця з мінімальним часом обслуговування}

  min:= t[1];

  for i:=2 to n do

     if t[i]< min then

  begin

     min:=t[i];

     nom:=i;    {індекс мінімального елемента}

  end;

  write (‘number of buyer having min service time =’);

  writeln (nom);

end.

Зауважимо, що кількість циклів і масивів, які входять до складу програми ех7_4 може бути зменшена. Спробуйте розв'язати задачу з прикладу 7.4, використовуючи якомога менше циклів та масивів.

Пошук у неупорядкованому та упорядкованому масивах

Пошук є однією з найбільш поширених задач програмування. Пошук в масиві за певним ключем полягає у визначенні номерів елементів масиву або їх значень, для котрих деяка умова, «ключ», виконується. Розрізняють задачі пошуку в упорядкованому та неупорядкованому масивах. В неупорядкованому масиві пошук можна здійснити лише за допомогою перегляду всього масиву. Такий пошук називається лінійним. Якщо значення елементів в масиві повторюються, то шляхом лінійного пошуку можна знайти лише перший з таких елементів, перервавши подальший пошук, або знайти усі потрібні значення, переглянувши весь массив. Приклади програм пошуку в неупорядкованому масиві першого з елементів і всіх елементів, які відповідають ключу пошуку, наведені нижче.

Приклад 7.5.

Створити масив за допомогою генератора псевдовипадкових чисел. Ввести з клавіатури деяке значення та визначити номер найпершого з елементів, що дорівнюють цьому значенню. Якщо таких елементів не існує, вивести відповідне повідомлення.  Лінійний пошук здійснюється шляхом перебирання всіх елементів масиву та порівняння кожного з них із заданим значенням. Якщо елемент знайдено, цикл пошуку переривається і виводиться знайдений індекс. А якщо цикл пошуку дійшов останнього елемента, і цей елемент не дорівнює заданому значенню, виводиться повідомлення про відсутністъ шуканого елемента. Описаний алгоритм пошуку елемента в неупорядкованому масиві реалізовано в програмі ех7_5, код якої наведено нижче. На рис. 7.3 зображено результати роботи програми ех7_5.

program ex7_5;     {пошук у неупорядкованому масиві}

uses crt;

var n, i: integer;     {кількість елементів масиву та їх індекси}

     a: array[1..10] of integer;       {вхідний масив}

     value: integer;        {шукане значення}

begin

  clrscr;

  randomize;    {ініціалізація генератора псевдо випадкових чисел}

  writeln (‘defining the number of the given component’);

  writeln (‘enter number of the component (<=10)’);

  readln (n);

  for i:=1 to n do       {генерація масиву}

     a[i]:=random(10);

  writeln (‘generated array’);

  for i:=1 to n do       {виведення масиву}

     write ( a[i], ‘ ’);

  writeln;

  writeln (‘enter value for search’);

  readln (value);       {введення ключа пошуку}

{---------------------------------------------------------------------------------------------------}

  for i:=1 to n do      {пошук першого елемента,}

     if a[i]=value then      {що відповідає ключу пошуку}

    begin

       writeln (‘nom=’, i);

       break;     {переривання циклу пошуку}

    end;

  if a[i]<>value then writeln (‘value not found’);

{---------------------------------------------------------------------------------------------------}

  readln;

end.

Приклад 7.6.

Розглянемо задачу пошуку в неупорядкованому масиві всіх елементів, що їх значення відповідає заданому ключу. Алгоритм розв'язання цієї задачі відрізняється від алгоритму розв'язання попередньої задачі тим, що пошук не переривається, якщо знайдено перший з потрібних елементів. Цикл завершується, коли переглянуто всі елементи масиву. Використання змінної булевого типу, яка перед виконанням циклу пошуку має значення false, а коли елемент знайдено, набуває значення true, дає можливість визначити результат пошуку. Для розв’язання цієї задачі слід замінити у програмі ех7_5 оточений пунктирними лініями цикл пошуку елемента на нижченаведений код та додати оголошення змінної flag. Модифікованій в такий спосіб програмі ех7_5 дамо назву ех7_5А.

{---------------------------------------------------------------------------------------------------}

  flag:=false;       {ознака успішності пошуку}

  for i:=1 to n do      {пошук значення у масиві}

     if a[i]=value then

    begin

       writeln (‘nom=’, i);

       flag:=true;     {пошук вважати успішним}

    end;

  if not flag then writeln (‘Value not found’);

{---------------------------------------------------------------------------------------------------}

Найвідомішим методом прискорення пошуку заданого елемента в упорядкованому масиві є метод бінарного пошуку, що має також назву методу половинного ділення. Якщо масив упорядковано, то половину його елементів після порівняння шуканого значення із середнім елементом можна відкинути. Коли ці значення рівні, вважаємо, що шуканий елемент знайдено. Якщо еталонне значення менше ніж значення середнього елемента масиву, то шуканий елемент може бути лище серед елементів лівої частини масиву, до котрої застосовується той самий метод, якщо — більше, то пошуковий метод застосовується до правої частини массиву. В результаті бінарного пошуку досліджується не більше ніж [log2n] елементів, де n – кількість елементів масиву, а квадратними дужками позначено цілу частину числа. Тому цей метод працює значно швидше за лінійний пошук.

Приклад 7.7.

Розглянемо задачу пошуку в упорядкованому масиві. Оголосимо змінні left, right та middle типу byte для позначення індексів першого (ліва межа), останнього (права межа) і середнього елементів ділянки масиву, що аналізується. Нехай масив елементів цілого типу позначено змінною mas. Кількість задіяних елементів масиву користувач вводить до змінної n. Використовуватимемо рекурсивну процедуру бінарного пошуку. Умовою припинення рекурсивного виклику процедури буде умова завершення пошуку (шукане значення збігається із значенням деякого елемента масиву) або умова відсутності шуканого значення в масиві (номер першого елемента ділянки масиву, що аналізується, перевищує номер останнього).

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

Ввести розмір масиву.

Ввести елементи масиву та ключ пошуку.

Покласти ліву межу масиву рівною одиниці, праву межу - рівною введеній кількості елементів.

3.1. Якщо ліва межа масиву більше правої, то завершити пошук, вважаючи його     безрезультатним, інакше виконати дії, зазначені в пунктах 3.2-3.4.ї

3.2.  Визначити індекс середнього елемента за наведеною нижче формулою

middle=(left+right) div 2

3.3. Порівняти ключ пошуку зі значенням середнього елемента. Якщо ці значення збігаються, то завершити пошук, вважаючи його успішним, інакше визначити підмасив, в якому треба продовжити пошук. Для цього перейти до пункту 3.4.

3.4. Якщо ключ пошуку менше значення середнього елемента, виконати процедуру бінарного пошуку для лівого підмасиву з межами left та middle-1, інакше виконати процедуру бінарного пошуку для правого підмасиву з межами  middle+1та right.

Якщо пошук завершено успішно, вивести знайдений елемент та його індекс, інакше вивести повідомлення про безуспішність пошуку.

Цей алгоритм реалізовано програмою ех7_6. Результати роботи програми зображено на рис. 7.5.

Program ex7_6;    {бінарний пошук в упорядкованому масиві}

uses crt;

var mas: array[1..15] of integer;    {вихідний масив}

     i, n: integer;      {індекс і кількість елементів}

     flag: boolean;      {ознака успішності пошуку}

     x: integer;       {ключ пошуку}

     middle: integer;      {індекс середнього елемента}

procedure BinSearch (left, right: integer);

{рекурсивна процедура бінарного пошуку, параметрами є індекси лівого та правого елементів}

begin

  if left>right       {умова виходу з рекурсії}

     then flag:=false;      {елемент не знайдено}

     else

        begin

           middle:=(left+right) div 2;

           if x=mas[middle]     {умова виходу з рекурсії}

              then flag:=true     {елемент знайдено}

              else if x<mas[middle]

                    then BinSearch (left, middle-1)

                    else BinSearch (middle+1, right);

           end;

end;

begin        {основна програма}

  clrscr;

  writeln (‘binary search’);

  writeln (‘enter number of components’);

  readln (n);

  writeln (‘enter array’);

  for i:=1 to n do      {введення елементів масиву}

     read (mas[i]);

  writeln (‘enter value to search’);

  readln (x);       {введення ключа пошуку}

  BinSearch (1, n);

  if flag then writeln (‘item=’, middle)

             else writeln (‘value not found’);

  readln;

end.

Перестановка елементів масиву

Перестановка або обмін значеннями між двома елементами масиву здійснюється аналогічно до обміну значеннями між двома змінними (рис. 7.6).

Значення одного елемента масиву зберігається в допоміжній змінній.

Значення іншого елемента присвоюється першому елементу.

Значення допоміжної змінної присвоюється другому елементу.

2

                                 1            3

Рис. 7.6. Обмін значеннями між двома елементами массиву

Запишемо програму перестановки першого та другого елементів масиву.

var mas: array[1..10] of integer;    {вхідний масив}

     tmp: integer;      {допоміжна змінна}

begin

  mas[1]:=5;       {вхідні значення}

  mas[2]:=7;

  tmp:=mas[1];    {обмін значеннями через допоміжну змінну}

  mas[1]:=mas[2];

  mas[2]:=tmp;

end.

Приклад 7.8.

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

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

Ввести n - розмір масиву та згенерувати значення його елементів.

Починаючи з першого елемента і до середини масиву виконувати обмін значеннями між і-м та (n-і+1)-м елементами масиву.

Вивести масив.

Program ex7_7;      {інвертувати масив}

var mas: array[1..10] of integer;    {вхідний масив}

     i, n: integer;   {індекс поточного елемента та кількість елементів}

     tmp: integer;      {допоміжна змінна}

begin

  writeln (‘Array inversion’);

  writeln (‘Enter number of elements’);

  readln (n);

  writeln (‘Generated array’);

  randomize;     {ініціалізація генератора випадкових чисел}

  for i:=1 to n do     {генерація псевдовипадкових чисел}

     mas[i]:=random(30);

  for i:=1 to n do      {виведення згенерованого коду}

     write (mas[i], ‘ ’);

  writeln;

  for i:=1 to n div 2 do     {інвертування масиву}

  begin

     tmp:=mas[i];

     mas[i]:=mas[n-i+1];

     mas[n-i+1]:=tmp;

  end;

  writeln (‘Inverted array:’);

  for i:=1 to n do      {виведення інвертованого масиву}

     write (mas[i], ‘ ’);

  readln;

end.

Вставка та видалення елемента, циклічний зсув елементів масиву

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

       

2

5

4

8

2

5

-1

4

8

Рис. 7.8 (а). Вставка елементів масиву

 

2

5

-1

4

8

2

5

-1

8

Рис. 7.8 (б). Видалення елементів масиву

Перед тим як вставляти до масиву новий елемент, для нього слід звільнити місце. Це можна зробити шляхом переміщення на одну позицію вправо підмасиву, що починається з позиції, у яку буде вставлено новий елемент. Так, якщо необхідно вставити новий елемент tmp на позицію 3 в (n-1)-вимірний масив а, то підмасив а[3], ..., а[n-1] треба зсунути вправо на одну позицію. Переміщення підмасиву слід здійснювати поелементно, починаючи від його правого елемента і рухаючись до лівого (якщо зсув здійснювати зліва направо, то весь підмасив буде заповнений значенням елемента а[3]).

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

writeln (‘enter value and position’);

readln (tmp, j);

for i:=n downto j do

  mas[i+1]:=mas[i];      {зсув під масиву вправо}

mas[j]:=tmp;

n:=n+1;      {збільшення кількості елементів масиву}

for i:=1 to n do

  write (mas[i], ‘ ’);

Під час видалення певного елемента з масиву слід зсунути на одну позицію вліво частину масиву, що розташована праворуч від цього елемента. Так, якщо необхідно видалита третій елемент n-вимірного масиву, то підмасив а[4], ..., а[n] треба зсунути вліво на одну позицію. Переміщення підмасиву слід здійснювати поелементно, починаючи від його лівого елемента і рухаючись до правого (якщо зсув здійснювати справа наліво, то весь підмасив буде заповнений значенням останнього елемента масиву). Після видалення кількість елементів масиву необхідно зменшити на одиницю. Наведемо фрагмент програми, який демонструє видалення j-го елемента масиву.

writeln (‘enter position for delete’);

readln (j);

for i:=j to n-1 do

  mas[i]:=mas[i+1];      {зсув під масиву вліво}

n:=n-1;      {зменшення кількості елементів масиву}

for i:=1 to n do

  write (mas[i], ‘ ’);

На відміну від операцій видалення або вставки елементів, під час циклічного зсуву масиву кількість його елементів не змінюється. Для циклічного зсуву вправо (рис. 7.9, а) слід зберегти в резервній змінній останній елемент та на одну позицію вправо перемістити підмасив, що починається з першого елемента і завершується передостаннім. Після цього необхідно записати на місце першого елемента той, який раніше був останнім. Коли виконують циклічний зсув вліво (рис 7.9, б), у резервній змінній зберігають перший елемент, зсувають на одну позицію вліво підмасив, що починається з другого елемента і завершується останнім, та записують на місце останнього елемента той, який раніше був першим.

5

-1

4

8

2

2

5

-1

4

8

Рис. 7.9 (а). Циклічний зсув елементів масиву вправо

5

-1

4

8

2

-1

4

8

2

5

Рис. 7.9 (б). Циклічний зсув елементів масиву вліво

Наведені нижче фрагменти програми демонструють циклічний зсув елементів вправо та вліво на одну позицію.

writeln (‘right shift’);      {циклічний зсув елементів вправо}

tmp:=mas[i];       {останній елемент стає першим}

for i:=n-1 downto 1 do

  mas[i+1]:=mas[i];

mas[1]:=tmp;

writeln (‘left shift’);      {циклічний зсув елементів вліво }

tmp:=mas[1];       {перший елемент стає останнім}

for i:=1 to n-1 do

  mas[i]:=mas[i+1];

mas[n]:=tmp;

4. Сортування масиву

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

Відомо багато методів, сортування масиву, що відрізняються швидкодією й обсягом оперативной пам'яті, яка при цьому використовується. Серед цих методів можна вирізнити методи внутрішнього та зовнішнього сортування. Методи внутрішнього  сортування не передбачають використання допоміжних масивів. Ці методи застосовують до масивів, що повністю розташовані в оперативній пам'яті. Методи зовнішнього сортування застосовують до великих масивів даних, які зберігаються на зовнішніх носіях. У цьому розділі розглянемо методи внутрішнього сортування масиву, обмежуючись задачею сортування за зростанням. Методи внутрішнього сортування прийнято поділяти на дві групи: елементарні (прямі) та удосконалені методи.

Найбільш відомими елементарними методами сортування масиву є:

сортування вставкою (включенням);

сортування вибором;

сортування обміном (бульбашкове сортування).

З удосконалених методів сортування найчастіше використовуються такі:

швидке сортування, або метод Хоара;

сортування включенням зі спадним приростом, або метод Шелла;

сортування за допомогою дерева, або пірамідальне сортування;

сортування методом злиття.

Нижче буде розглянуто всі три вищезгаданих елементарних методи сортування та два удосконалених - метод Хоара й метод злиття.

Сортування методом вставки

На кожному кроці цього методу масив розділений на дві частини: ліву, вже відсортовану, та праву, ще не відсортовану. Перший елемент правої частини вставляється до лівої частини так, щоб ліва частина залишалася відсортованою. У результаті відсортована частина збільшується на один елемент, а невідсортована – на один елемент зменшується. Отже, на кожному кроці алгоритму сортування методом вставки слід виконати дві операції: пошук позиції для вставки елемента та власне його вставку із подальшим зсувом на одну позицію вправо від елементів відсортованої частини. Цей зсув «затре» перший елемент невідсортованого підмасиву останнім елементом відсортованого. Спочатку відсортованим підмасивом вважаємо перший елемент, а решту елементів масиву відносимо до невідсортованої частини.

Приклад 7.9.

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

Зберегти перший елемент невідсортованого підмасиву в допоміжній змінній.

Визначити позицію вставки збереженого елемента у масив. Для цього дотримуватися перелічених далі вказівок.

2.1.  Вважати перший елемент масиву поточним.

2.2. Доки елемент для вставки більше за поточний, збільшувати індекс поточного    елемента.

Вставити збережений на кроці 1 елемент на знайдену позицію вставки, зсунувши на одну позицію вправо решту відсортованої частини.

Пересунути початок невідсортованої частини на одну позицію вправо.

program ex7_8;      {сортування вставкою}

uses crt;

var n, i, j, k: integer;      {кількість та індекси елементів}

     a: array[1..10] of integer;

     tmp: integer;  {елемент, що вставляється у відсортовану частину чисел}

begin

  clrscr;

  randomize;     {ініціалізувати генератор випадкових чисел}

  writeln (‘insertion sort’);

  writeln (‘enter number of the components (<=10)’);

  readln (n);      {ввести кількість елементів масиву}

for i:=1 to n do       {генерувати масив}

  a[i]:=random(30);

writeln (‘generated array’);

for i:=1 to n do      {вивести згенерований масив}

  write (a[i], ‘ ’);

writeln;

writeln (‘sort process’);

for i:=2 to n do      {сортувати методом вставки}

begin       {і – початок невідсортованого підмасиву}

  tmp:=a[i];       {вибрати елемент для вставки}

  j:=1;        {цикл пошуку позиції вставки}

  while tmp>a[j] do      {якщо елемент, що вставляється}

     j:=j+1;  {менший або рівний поточному, то  j фіксує позицію вставки}

  for k:=i-1 downto j do     {зсунути вправо елементи}

     a[k+1]:=a[k];      {невідсортованої частини}

  a[j]:=tmp;      {вставка вибраного елемента у позицію j}

  for k:=1 to n do     {виведення проміжних результатів}

     write (a[k], ‘ ’);

  writeln;

end;

writeln (‘sorted array’);

for i:=1 to n do     {виведення відсортованого масиву}

  write (a[i], ‘ ’);

  readln;

end.

Сортування методом вибору

Цей метод, як і метод сортування вставкою, розділяє масив на дві частини: ліву, вже впорядковану, та праву, ще не впорядковану. Ви6ирають_найменший елемент невідсортованої частини. Цей елемент міняють місцями з її першим елементом, збільшуючи на одиницю довжину відсортованої частини масиву. Отже, на першому кроці алгоритму невпорядкованою частиною є весь масив, з котрого вибирають мінімальний елемент. Цей елемент міняють місцями з першим елементом масиву На другому кроці невпорядковану частину масиву складають елементи від другого до останнього. Серед цих елементів вибирають найменший, котрий міняють місцями з другим. Процес триває доти, доки у невідсортованій частині не залишиться один елемент.

Приклад 7.10.

Формалізуємо алгоритм сортування методом вибору і реализуємо його мовою Раsсаl. Весь масив вважати невідсортованою частиною. Поки ця частина містить більше одного елемента, виконувати такі дії:

Вибрати перший елемент невідсортованої частини масиву і вважати його мінімальним; эапам'ятати індекс цього елемента.

Для елементів від наступного після вибраного і до останнього повторювати такі дії.

2.1. Порівняти вибраний елемент і поточний.

2.2. Якщо вибраний елемент більший за поточний, запам'ятати поточний елемент як мінімальний, а його індекс - як індекс мінімального елемента.

Поміняти місцями мінімальний і вибраний на кроці 1 елементи.

Пересунути початок невідсортованої частини на одну позицію вправо.

program ex7_9;      {сортування методом вибору}

uses crt;

var n, i, j: integer;      {кількість та індекси елементів}

     a: array [1...10] of integer;

     min, imin: integer;    {мінімальний елемент і його індекс}

begin

  clrscr;

  randomize;     {ініціалізувати генератор випадкових чисел}

  writeln (‘selection sort’);

  writeln (‘enter number of the components (<=10)’);

  readln (n);      {ввести кількість елементів масиву}

  for i: =1 to n do       {генерувати масив}

  a[i]:=random (30);

writeln (‘generated array’);

for i: =1 to n do      {вивести згенерований масив}

  write (a[i], ‘ ’);

writeln;

writeln (‘series of selection’);

for i:=1 to n-1 do      

begin    

min:=a[i];  {пошук мінімального елемента в діапазоні від і-го до останнього елемента}

  imin:=i;       {індекс мінімального елемента}

  for j:=i+1 to n do      {пошук мінімального елемента}

     if min>a[j] then

  begin

     min:=a[j];

     imin:=j;

  end;

  a[imin]:=a[i];   {обмін місцями мінімального та поточного елементів}

  a[i]:=min;

  for j:=1 to n do     {виведення проміжних результатів}

    write (a[j], ‘ ’);

  writeln;

end;

writeln (‘sorted array’);

for i:=1 to n do     {виведення відсортованого масиву}

  write (a[i], ‘ ’);

readln;

end.

Сортування методом обміну

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

Приклад 7.11.

Розглянемо алгоритм сортування методом обміну та його реалізацію мовою Раsсаl. 1. Установити лічильник ітерацій рівним одиниці.

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

2.1. Якщо поточний елемент більший за попередній, поміняти ці елементи місцями.

2.2. Перейти до попереднього елемента.

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

program ex7_10;     {сортування обміном}

uses crt;

var n, i, j, k: integer;     {кількість та індекси елементів}

     a: array[1..10] of integer;

     tmp: integer;     {допоміжний елемент для обміну}

begin

  clrscr;

  randomize;

  writeln (‘exchange sort’);

  writeln (‘enter number of the components (<=10)’);

  readln (n);  

  for i: =2 to n do       {генерувати масив}

     a[i]:=random (30);

  writeln (‘generated array’);

  for i: =1 to n do      {вивести згенерований масив}

     write (a[i], ‘ ’);

  writeln;

  writeln (‘sort process’);

  for i: =2 to n do      {сортувати методом обміну}

     for j:=n downto i do

        if a[j]<a[j-1] then

       begin     {поміняти елементи місцями}

          tmp:=a[j];

          a[j]:=a[j-1];

          a[j-1]:=tmp;   {виведення проміжних результатів}

       for k:=1 to n do

          write (a[k], ‘ ’);

       writeln;

       end;

  writeln (‘sorted array’);

  for i: =1 to n do      {вивести відсортований масив}

     write (a[i], ‘ ’);

  readln;

end.

Алгоритми сортування масивів методами вибору, вставки та обміну не потребують додаткової оперативної пам'яті. Час виконання розглянутих алгоритмів сортування пропорційний кількості операцій порівняння або перестановок елементів. Сортування n-елементного масиву методом вибору потребує n2/2 операцій порівняння та n операцій обміну елементів. Метод сортування вставкою потребує n2/4 операцій порівняння та стільки ж операцій обміну, а метод сортування обміном - n2/2 операцій порівняння та n2/2 операцій обміну. Отже, методи вставки та вибору за характеристиками приблизно еквівалентні, проте метод обміну поступається перед ними швидкодією.

Удосконалені методи сортування масиву використовують значно меншу кількість операцій порівняння та перестановок елементів. Детальний аналіз алгоритмів сортування зроблено у [5, 12, 13]. Розглянемо один з удосконалених методів сортування масиву.

Швидке сортування

Автор цього метода Ч. Хоар назвав його швидким сортуванням, оскільки для більшості масивів цей метод потребує приблизно (n/6) log n обмінів елементів і n log n порівнянь, тобто набагато менше, ніж будь-який з елементарних методів. Метод функціонує за принципом «розділяй та пануй»: елементи масиву діляться на дві частини, і кожна з них потім сортується окремо. Для цього обирають деякий елемент х, назвемо його розділовим. Мета полягає у розташуванні всіх менших за х елементів зліва від х, а всіх більших за х елементів – справа від х. поділивши масив, слід повторити процедуру сортування для кожної частини, потім – для частин цих частин і т.д., доки кожна з частин масиву не міститиме лише один елемент. Зауважимо, що у деяких модифікаціях методу Хоара розташування та значення розділового елемента можуть змінюватися під час розподілу елементів. Розглянемо одну з таких модифікацій [5].

Отже, алгоритм методу Хоара є рекурсивним і для його реалізації було б зручно застосувати рекурсивну процедуру. Параметрами цієї процедури будуть змінні left та right, що позначатимуть ліву та праву межу розглядуваної частини масиву. Розділовим елементом вважатимемо середній за номером елемент частини масиву і присвоїмо значення цього елемента змінній х. Рекурсивний виклик процедури для поділу лівого підмасиву на дві частини здійснюється в тому разі, якщо ліва межа підмасиву менша за індекс його середнього елемента, а для поділу правого підмасиву - якщо права межа більша за індекс середнього елемента. Для поділу елементів на дві частини застосовуємо два цикли while у середині циклу repeat-until. На кожній ітерації зовнішнього циклу здійснюватиметься один обмін елементами між лівою та правою частинами. Внутрішні цикли (здійснюють перегляд масиву зліва та справа) призначені для знаходження чергової пари елементів, що мають бути переставлені. Зазначимо, що переставленим може бути і сам розділовий елемент, при цьому він може втратити властивість розділовості. Цей факт не впливає на коректність роботи розглянутої далі програми.

Нижче наведено код програми ех7_11, а на рис. 7.13 зображено результати її виконання. Цикл, що здійснює виведення проміжних результатів, у код програми ех7_11 не включено.

Приклад 7.12

program ex7_11;     {швидке сортування – метод Хоара}

uses crt;

var i, n: integer;     {кількість елементів масиву та їх індекси}

     a: array[1..10] of integer;    {вихідний масив}

procedure quicksort (left, right: integer);

var i, j, k, x, tmp: integer;    {розділовий елемент та допоміжні змінні}

begin

  i:=left;       {ліва границя підмасиву}

  j:= right;       {права границя підмасиву}

  x:=a[(left+right) div 2];     {значення бар’єрного елемента}

  writeln (‘left=’, left, ‘right=’, right, ‘x=’, x);

  repeat       {розділити масив на підмасиви}

     while a[i]<x do i:=i+1;     {визначити індекси елементів,}

     while a[j]>x do j:=j-1;     {що обмінюються}

     if i<=j then

     begin      {обміняти елементи місцями}

         tmp:=a[i];

         a[i]:=a[j];

         a[j]:=tmp;

         i:=i+1;

         j:=j-1;     {виведення проміжних результатів}

         for k:=1 to n do

            write (a[k], ‘ ’);

         writeln;

      end;

  until i>j;

  if left<j then

     quicksort (left, j);      {впорядкувати лівий підмасив}

  if i<right then

     quicksort (i, right);     {впорядкувати правий підмасив}

  end;

begin

  clrscr;

  randomize;    {ініціалізація генератора псевдовипадкових чисел}

  writeln (‘quick sort’);

  writeln (‘enter number of the components (<=10)’);

  readln (n);

  for i:=1 to n do       {згенерувати масив}

     a[i]:=random(30);

  writeln (‘generated array’);

  for i:=1 to n do      {вивести згенерований масив}

     write (a[i], ‘ ’);

  writeln;

  writeln (‘sort process’);

  quicksort (1, n);

  writeln (‘sorted array’);

  for i:=1 to n do      {вивести відсортований масив}

     write (a[i], ‘ ’);

  writeln;

  readln;

end.

Сортування методом злиття

У запропонованому Дж. фон Нейманом методі сортування злиттям, як і в методі Хоара, реалізовано принцип «розділяй та пануй». Масив ділиться навпіл, до кожної половини застосовується рекурсивно та сама процедура сортування злиттям, а відсортовані частини з’єднуються в один впорядкований масив (рис.7.13).

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

Час злиття упорядкованих масивів лінійно эалежить від їх сумарної довжини. Враховуючи цей факт, неважко буде довести, що повне сортування методом злиття, як і сортування методом Хоара, потребує виконання O (n log n) базових операцій над елементами масиву розмірності n.

Програму сортування методом злиття наведемо у прикладі 7.13 з наступного розділу. Задачу злиття двох масивів реалізуємо за допомогою процедури. Оскільки процедура злиття має бути застосована до різних підмасивів, то зручно було б передавати масив до процедури як параметр. Особливостям використання масивів як параметрів підпрограм і присвячено наступний розділ.

5. Масиви як параметри

Масиви можна використовувати як параметри процедур і функцій. Загальні правила використання формальних параметрів і заміни їх аргументами (фактичними параметрами) застосовуються і до масивів. Масиви можуть бути передані у процедури як параметри-значення або як параметри-змінні. Коли масив передають як параметр-значення, у стековій пам’яті створюється його копія, і під час виконання підпрограми він не змінюється. Якщо масив передають як параметр-змінну, то у стекову пам'ять пересилається покажчик, тобто адреса першого елемента масиву. Це приводить до того, що під час виконання процедури сам массив змінюється, і його можна повернути з процедури для подальшого використання. Можна рекомендувати передавати масиви як покажчики (параметри-змінні) за умови, що вони містять велику кількість елементів і потребують великого обсягу оперативної пам’яті для свого зберігання. У цьому разі стекової пам’яті, розмір якої становить 16 Кбайт, може не вистачити для збереження копії масиву.

Приклад 7.13.

Наведемо програмну реалізацію методу сортування злиттім. Саме сортування злиттям реалізуємо процедурою Sort, а злиття упорядкованих масивів – процедурою Merge. Параметрами-значеннями процедури Merge будуть виступати масиви, які необхідно злити, та їх довжина. Параметром-змінною буде масив, до якого треба записати результат злиття. Крім того, знадобиться допоміжна процедура

CopyArr (a: Arr; x, y: integer; var b: Arr; z: integer)

що копіює частину масиву а, від елемента з номером х до елемента з номером у, до масиву b, а також процедура Output, яка виводитиме до вікна програми вміст масиву, що передається їй як аргумент.

program ex7_12;     {сортування методом злиття}

uses crt;

type

  Arr=array[1..10] of integer;   {тип масиву з 10 цілих чисел}

var i, n: integer;     {індекс і кількість елементів масиву}

     a, g, e, f: Arr;   {а – масив, що сортується, g, e, f  - допоміжні масиви}

{злиття упорядкованих масивів а та b}

procedure Merge (a, b: Arr; n, m: integer; var c: Arr);

var

  i, j: integer;

begin

  i:=1; j:=1;

  while (i<=n) and (j<=m) do   {формувати вихідний масив}

     if a[i]<b[j] then     {якщо елемент масиву а менший}

     begin

        c[i+j-1]:=a[i];

        i:=i+1;     {перейти до наступного елемента масиву а}

     end

     else      {якщо елемент масиву b менший}

     begin

        c[i+j-1]:=b[j];

        j:=j+1;     {перейти до наступного елемента масиву b}

     end;

  for i:=i to n do     {якщо масив а не вичерпано}

     c[j+i-1]:=a[i];

  for j:=j to m do     {якщо масив b не вичерпано}

     c[i+j-1]:=b[j];

end;

{копіювання частини масиву а до масиву b}

procedure CopyArr (a: Arr; x, y: integer; var b: Arr; z: integer);

var

  i: integer;

begin

  for i:=x to y do

     b[i-x+z]:=a[i];

end;

{виведення масиву а, що має довжину n}

procedure Output (a: Arr; n: integer);

var

  i: integer;

begin

  for i:=1 to n do

     write (a[i], ‘ ’);

  writeln;

end;

{сортування частини масиву від і-го елемента до j-го}

procedure Sort (i, j: integer);

var

  t: integer;

begin

  if i<j then     {якщо сортується більше ніж один елемент}

  begin

     t:=i+(j-1) div 2;      {середина частини, що сортується}

     if i<j-1 then    {якщо сортується більш ніж два елементи}

     begin

        Sort (i, t);      {сортування лівої частини}

        Sort (t+1, j);      {сортування правої частини}

     end;

     CopyArr (a, i, t, g, 1);    {копіювання відсортованих частин}

     CopyArr (a, t+1, j, e, 1);    {до резервних масивів g та e}

     Merge (g, e, t-i+1, j-t, f);     {злиття відсортовани частин}

     CopyArr (f, 1, j-i+1, a, i);     

     write (‘The sorted [‘, i, ’, ‘, j, ’] part ’);

     Output (f, j-i+1);     {виведення проміжних результатів}

  end;

end;

begin

  clrscr;

  randomize;

  writeln (‘merge sort’);

  writeln (‘enter number of the components (<=10)’);

  readln (n);

  for i:=1 to n do       {генерувати масив}

     a[i]:=random(30);

  writeln (‘generated array’);

  Output (a, n);      {вивести згенерований масив}

  Sort (1, n);        {сортувати масив}

  writeln (‘sorted array’);

  Output (a, n);      {вивести відсортований масив}

  readln;

end.

Контрольні питання

1. Одновимірні масиви

2. Поняття масиву та його властивості

3. Базові операції обробки одновимірних масивів

4. Сортування масиву

5. Масиви як параметри


 

А также другие работы, которые могут Вас заинтересовать

12492. Составить список учебной группы, включающей n человек 657.5 KB
  Отчет по лабораторной работе №3 по дисциплине Языки программирования Задание: Составить список учебной группы включающей n человек. Для каждого учащегося указать фамилию дату рождения день месяц год год поступления в ВУЗ экзаменационные оценки за первые два ...
12493. Динамическая маршрутизация 582.43 KB
  Во время лабораторной работы мы научились строить топологию с настройкой динамической маршрутизации. Научиться строить топологию с настройкой динамической маршрутизации.
12494. Определение увеличения объектива микроскопа и измерение размеров объектов с помощью микроскопа 39 KB
  Определение увеличения объектива микроскопа и измерение размеров объектов с помощью микроскопа: методические указания по выполнению лабораторной работы № 62 по курсу Физика для студентов инженернотехнических специальностей всех форм обучения / ЮгоЗап.. гос. унт; сос...
12495. Определение показателя преломления стекол 89.5 KB
  PAGE 3 Определение показателя преломления стекол: методические указания по выполнению лабораторной работы № 63 по курсу Физика для студентов инженернотехнических специальностей / Курск гос. техн. унт; сост.: Л.А. Желанова А.А. Родионов. Курск 2010. 7 с. Библи...
12496. Определение радиуса кривизны линзы и длины световой волны с помощью колец ньютона 327 KB
  Определение радиуса кривизны линзы и длины световой волны с помощью колец ньютона: методические указания по выполнению лабораторной работы по оптике № 66 по курсу Физика / Курск гос. техн. унт; сост.: Л.А. Желанова А.А. Родионов. Курск 2010. 7 с. Библиогр.: с.7. Содержат све...
12497. Лесное хозяйство 84.5 KB
  Многие важнейшие элементы лесного хозяйства, включая охрану лесов, лесоустройство, учёт и инвентаризацию лесов, лесовосстановление, защитное лесоразведение, профилактическую работу с населением и лесную науку, или уже прекратили своё существование, или неизбежно перестанут существовать в течение одного-двух лет при сохранении существующих тенденций.
12498. Изучение внутреннего фотоэффекта 43 KB
  Изучение внутреннего фотоэффекта: методические указания по выполнению лабораторной работы № 83 по курсу Физика для студентов инженернотехнических специальностей / Курск гос. техн. унт; сост.: Л.А. Желанова А.А. Родионов. Курск 2010. 7 с. Библиогр.: с.7. Содержат сведения...
12499. Анализ фондового рынка Российской Федерации за 2009 -2014 года 4.01 MB
  Ведущим индикатором фондового рынка России является Индекс ММВБ. Кроме основного композитного индекса ММВБ, рассчитывается Индекс РТС. Основные индексы Московской Биржи (Индекс ММВБ и Индекс РТС)
12500. Определение показателя преломления, концентрации и дисперсии растворов сахара с помощью рефрактометра Аббе 302 KB
  Определение показателя преломления концентрации и дисперсии растворов сахара с помощью рефрактометра Аббе [Текст]: методические указания по выполнению лабораторной работы по оптике № 64 для студентов инженернотехнических специальностей / ЮгоЗап. гос. унт; сост.: А.А. Ро