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

1. Основні поняття. Чи знаєте ви, як складно відшукати прізвища осіб у списку, якщо список великий і невпорядкований і як просто це зробити, якщо список упорядкований? Ось чому задачі впорядкування даних є актуальними. Вони виникають у різних застосуваннях, зокрема, в базах даних. У неупорядкованому масиві з n елементів пошук потрібного даного виконують методом перебирання усіх значень. Такий підхід потребує виконання у найгіршому випадку n операцій порівняння. Якщо ж масив упорядкований, то операцій порівняння потрібно лише log₂n. Тому перед пошуком даних масив спочатку необхідно упорядкувати, тобто переставити елементи місцями так, щоб вони розташовувалися за зростанням або спаданням значень.

Є багато способів упорядкування масивів. їх можна поділити на прямі методи та поліпшенні. До прямих методів належать:

· метод обміну (метод «бульки»);

· метод мінімальних елементів;

· метод вставок.

Поліпшені методи — це методи Шелла, Xoapa (швидке упорядкування), пірамідального упорядкування, злиття тощо.

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

Поліпшені методи упорядкування використовують меншу кількість порівнянь та перестановок елементів. Зазвичай вони особливо ефективні для упорядкування великих масивів даних. Для наборів даних, які складаються з невеликої кількості елементів, ліпше застосовувати прямі методи упорядкування. Прямі методи впорядкування не потребують додаткової оперативної пам'яті.

Можна упорядковувати дані різних типів: числових, символьних, рядкових, застосовуючи один і той же алгоритм.

Без втрати загальності розглянемо послідовність а₁, a₂, ..., а_n, з n натуральних чисел. Наведемо алгоритми, програми та характеристики декількох методів упорядкування даних за зростанням.

2. Метод обміну. У методі обміну спочатку розглядають першу пару елементів масиву. Якщо перший елемент більший від сусіднього (a₁ > а₂), то їх міняють місцями. Далі другий елемент порівнюють із третім і, якщо потрібно, обмінюють місцями і т. д. Після n порівнянь максимальний елемент буде розташований в кінці масиву, тобто там, де потрібно. Тепер знову розглядають масив, але вже без останнього елемента, і застосовують до нього метод обміну — другий за величиною елемент буде розміщений в масиві на передостанній позиції і т.д. Упорядковані елементи нагромаджуватимуться в кінці масиву. Елементи переміщаються до хвоста масиву подібно до бульок, які переміщаються на поверхню води під час кипіння. Звідси і друга назва — «метод бульок».

Якщо масив має n елементів, то метод треба застосувати п-1 разів (кожного разу до меншої кількості елементів).

Кількість порівнянь утворює спадну арифметичну професію з елементами від n-1 до 1. Тому кількість операцій порівнянь n(n-l)/2, тобто O(n²/2). Кількість операцій обміну елементів у найгіршому випадку є порядку n²/2.

Розглянемо модель масиву з п'ятьма елементами (n = 5) — невпорядкований набір п'яти чисел:

4,2,7,9, 1. Упорядкуємо його методом обміну.

Під час першого (j = 1) перегляду набору даних матимемо:

1-й крок: 4 > 2 — умова істина, тому міняємо 4 і 2 місцями, отримаємо 2,4,7,9, 1;

2-й крок: 4 > 7 — умова хибна, обміну немає, послідовність залишається незміненою: 2, 4, 7, 9, 1;

3-й крок: 7 > 9 — умова хибна, залишається 2, 4, 7, 9, 1;

4-й крок: 9 > 1, тому міняємо 9 і 1 місцями, отримаємо 2, 4, 7, 1, 9.

Під час першого перегляду було n - 1 порівняння і два обміни.

Для j = 2 розглядаємо вже набір з чотирьох елементів (2, 4, 7, 1) і застосовуємо до нього метод обміну, отримаємо 2, 4, 1, 7, 9.

Для j = 3 розглядаємо лише перші три елементи. Отримаємо 2,1,4, 7,9.

Для j = 4 розглядаємо перші два і отримуємо 1, 2,4, 7, 9.

Наведемо програму впорядкування даних методом обміну.

program MetodObminu;

Uses

crt;

Const

n = 10; {кількість елементів може бути будь-якою}

Var

а : array [l..n] of integer; {mun може бути інший}

і, j : integer;

c : integer;

Begin

clrscr;

for i := 1 to n do

Begin

write ('Введіть елемент масиву — ');

readln(a[i]);

end;

for j := 1 to n - 1 do

for i := 1 ton -j do

if a[i] > a[i + 1] then

Begin

c := a[i + 1];

a[i + l]:=a[i];

a[i] := c;

end;

writeln('Упорядкований масив');

for i := 1 to n do writeln(a[i]);

End.

Завдання 1. Виконайте програму та проаналізуйте результати. Модифікуйте програму для упорядкування даних рядкового типу. Це і наступні завдання розв'язуйте для середовищ типу Turbo Pascal або Delphi.

3. Метод мінімальних елементів. У цьому методі розглядають набір даних, знаходять номер мінімального елемента і міняють його місцями з першим елементом. Далі знов розглядають масив, але вже без першого елемента і до нього застосовують метод мінімальних елементів. I так n-l разів. Упорядковані елементи поступово переміщуватимуться на початок масиву.

Якщо масив має n елементів, то метод треба застосувати п-1 разів (кожного разу до меншої кількості елементів). Упорядковані елементи будуть нагромаджуватися на початку масиву.

Кількість порівнянь є величиною O(n²/2). Кількість операцій обміну дорівнює n.

Розглянемо неупорядкований набір чисел з п'яти елементів (4,2, 7, 9, 1) та упорядкуємо його методом мінімальних елементів.

Під час першого (j = 1) перегляду набору даних знайдемо мінімальний елемент — це 1 і поміняємо його місцями з першим елементом (4). Отже, отримаємо 1, 2, 7, 9, 4. Було виконано чотири порівняння.

Для (j = 2) розглянемо набір з чотирьох елементів (2, 7, 9, 4) і застосуємо до нього метод обміну. Отримаємо 1,2,7, 9,4.

Для j = 3 розглянемо лише останні три елементи й отримаємо 1, 2,4,9,7.

Для j = 4 розглянемо останні два, отримаємо 1, 2, 4, 7, 9.

Наведемо програму впорядкування даних методом мінімальних елементів.

program MetodMinEl;

Uses

crt;

Const

n = 10;

Var

a:array[l..n] of integer;

i,j, min, c : integer;

Begin

clrscr;

for i := 1 to n do

Begin

write ('Введіть елемент масиву — ');

readln(a[i]);

end;

forj := 1 to n- 1 do

Begin

min := j;

for i := j + 1 to n do

If a[min] >a[i] then

Begin

c := a[min];

a[min] := a[i];

a[i] := c;

end;

writeln(‘Упорядкований масив');

for i := 1 to n do writeln(a[i]);

readln

end.

Завдання 2. Виконайте програму та проаналізуйте результати. Модифікуйте програму для упорядкування послідовності даних рядкового типу.

4. Метод вставок. У методі вставок розглядають весь масив і перший елемент порівнюють з іншими, доки не знаходять меншого від нього. Перша позиція в масиві стає позицією вставки. Знайдений менший елемент і позицію вставки запам'ятовують. Усі елементи масиву, починаючи від позиції вставки до того, що передує знайденому, зміщують на одну позицію праворуч. Значення знайденого елемента записують у позицію вставки і порівнюють його з елементами, що залишилися. Якщо виявляють ще менший елемент, то повторюють метод вставки. I так доти, доки не доходять до кінця масиву — лише після цього перший елемент буде на місці. Далі розглядають масив без першого елемента і застосовують до нього описаний метод і т.д.

У методі вставок кількість операцій порівнянь та обміну однакова і є величиною O(n²/4).

Розглянемо невпорядкований набір чисел 4, 2, 9, 7, 1 та упорядкуємо його методом вставки.

Під час першого (j = 1) перегляду набору даних матимемо:

1-й крок: 4 > 2, тому запам'ятовуємо число 2 і позицію числа 4, переміщуємо 4 праворуч, а 2 вставляємо на місце 4. Отримаємо 2, 4, 9, 7, 1;

2-й крок: 2 > 9 — умова хибна, маємо 2, 4, 9, 7, 1;

3-й крок: 2 > 7 — умова хибна, маємо 2, 4, 9, 7, 1;

4-й крок: 2 > 1, тому запам'ятовуємо число 1 і позицію числа 2; переміщуємо 2, 4, 9, 7 праворуч, а 1 вставляємо на місце 2. Отримаємо 1, 2, 4, 9, 7.

Далі застосовуємо метод вставки до набору 2, 4, 9, 7 і т.д.

Наведемо програму впорядкування даних методом вставок.

program MetodVstavok;

Uses

crt;

Const

n = 10;

Var

а : array [1 .. n] of integer;

i,j, k, c : integer;

Begin

clrscr;

for i := 1 to n do

Begin

write ('Введіть елемент масиву — ');

readln(a[i]);

end;

for i := 2 to n do

Begin

c := a[i]: [Вибираємо невпорядкований елемент}

j:=l;

while c > a[j] do [Знаходіто позицію вставки)

j := j + i;

for k := i - 1 downtoj do

a[k + 1] := a[k];

а[j] :=c;

end;

writeln('Упopядкoвaний масив');

for i := 1 to n do write(a[i],' ');

readln

end.

Завдання З. Виконайте програму. Модифікуйте програму так, щоб вона виводила на екран усі проміжні обчислення. Проаналізуйте одержані результати.