5. Упорядкування і пошук даних

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

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

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

Методи внутрішнього впорядкування базуються на таких підходах:

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

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

3. Вставка: кожний новий елемент уставляється в правильну позицію стосовно вже розміщених у масиві і впорядкованих елементів.

4. Злиття: впорядковані підмножини елементів об’єднуються в більші впорядковані підмножини.

5. Розподіл: машинна модифікація ручних методів упорядкування. Наприклад, упорядкування листів на пошті. Перша механічна версія такого впорядкування називається цифровим упорядкуванням. Ключ упорядкування розділяється на цифри, дані впорядковуються за значенням старшої цифри, потім отримані підмножини упорядковуються за значенням наступної цифри і так далі.

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

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

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

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

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

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

Для реалізації алгоритмів упорядкування командою File|New Application створимо новий проект. Присвоїмо формі заголовок Упорядкування даних (властивість Caption). Командою File|Save All запишемо програмний модуль у файл з іменем ULAB5_1.pas, а проект – PLAB5_1.dpr.

Розробимо форму для введення початкових даних і виведення результату Рис.5.1.

Для введення початкових даних і виведення результату розмістимо на формі по три компоненти Edit та Memo.

Крім цього, для вибору методу упорядкування розмістимо на формі і об’єднаємо у групу з заголовком Метод (компонент GroupBox) чотири керуючі кнопки (компонент RadioButton) з написами Вибір, Обмін, Вставка і Злиття. Для вибору впорядкування за зростанням чи спаданням використаємо компонент ComboBox. Встановимо йому такі значення властивостей Text=Зростання (початкове значення) і для Items список із двох значень Зростання та Спадання.

Обробники кнопок Вибір, Обмін, Вставка і Злиття містяться у програмному модулі ULAB5_1.

Рис.5.1 Форма Упорядкування даних

Unit ULAB5_1;

. . . . . . . . . . . . . . . . .

implementation

{$R *.DFM}

{Обробник кнопки Вибір}

procedure TForm1.RadioButton1Click(Sender: TObject);

Var a: array[1..300] of integer;

n, i, j, k, r: integer;

Begin

{Введення початкових даних}

if (Edit1.Text='') or (Memo1.Lines.Count=0) then

ShowMessage('Введіть початкові дані')

else begin

n:=StrToInt(Edit1.Text);

for i:=1 to n do

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

if ComboBox1.Text='Зростання' then

begin

{Впорядкування за зростанням}

for i:=1 to n-1 do

begin k:=i;

for j:=i+1 to n do

if a[j]<a[k] then k:=j;

r:=a[i]; a[i]:=a[k];a[k]:=r; end;

end

else begin

{Впорядкування за спаданням}

for i:=1 to n-1 do

begin k:=i;

for j:=i+1 to n do

if a[j]>a[k] then k:=j;

r:=a[i]; a[i]:=a[k]; a[k]:=r;

end;

end;

{Виведення результату}

Edit3.Text:='';

Memo3.Lines.Clear;

k:=n;

Edit3.Text:=IntToStr(k);

for i:=1 to n do

Memo3.Lines.Add(IntToStr(a[i]));

end;

RadioButton1.Checked:=false;

end;

{Обробник кнопки Обмін}

procedure TForm1.RadioButton2Click(Sender: TObject);

Var a: array[1..300] of integer;

n, i, k, r: integer;

f:boolean;

Begin

{Введення початкових даних}

if (Edit1.Text='') or (Memo1.Lines.Count=0) then

ShowMessage('Введіть початкові дані')

else begin

n:=StrToInt(Edit1.Text);

for i:=1 to n do

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

if ComboBox1.Text='Зростання' then

begin

{Впорядкування за зростанням}

f:=true;

while f do

begin f:=false;

for i:=n downto 2 do

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

begin r:=a[i];a[i]:=a[i-1];a[i-1]:=r; f:=true; end;

end;

end

else begin

{Впорядкування за спаданням}

f:=true;

while f do

begin f:=false;

for i:=n downto 2 do

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

begin r:=a[i];a[i]:=a[i-1];a[i-1]:=r; f:=true; end;

end;

end;

{Виведення результату}

Edit3.Text:='';

Memo3.Lines.Clear;

k:=n;

Edit3.Text:=IntToStr(k);

for i:=1 to n do

Memo3.Lines.Add(IntToStr(a[i]));

end;

RadioButton2.Checked:=false;

end;

{Обробник кнопки Вставка}

procedure TForm1.RadioButton3Click(Sender: TObject);

Var a: array[1..300] of integer;

n, m, i, j, k, r: integer;

Begin

{Введення початкових даних}

if (Edit1.Text='') or (Memo1.Lines.Count=0) then

ShowMessage('Введіть початкові дані')

else begin

n:=StrToInt(Edit1.Text);

for i:=1 to n do

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

if ComboBox1.Text='Зростання' then

begin

{Впорядкування за зростанням}

for i:=2 to n do

begin k:=i; r:=a[i];

for j:=1 to k-1 do

if r < a[j] then

begin

for m:=k downto j+1 do

a[m]:=a[m-1]; a[j]:=r; break;

end; end;

end

else

begin

{Впорядкування за спаданням}

for i:=2 to n do

begin k:=i; r:=a[i];

for j:=1 to k-1 do

if r > a[j] then begin

for m:=k downto j+1 do

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

a[j]:=r;

break;

end; end;

end;

{Виведення результату}

Edit3.Text:='';

Memo3.Lines.Clear;

k:=n;

Edit3.Text:=IntToStr(k);

for i:=1 to n do

Memo3.Lines.Add(IntToStr(a[i]));

end;

RadioButton3.Checked:=false;

end;

{Обробник кнопки Злиття}

procedure TForm1.RadioButton4Click(Sender: TObject);

Var a: array[1..300] of integer;

b: array[1..500] of integer;

c: array[1..800] of integer;

n, m, i, j, k, r: integer;

Begin

{Введення початкових даних}

if (Edit1.Text='') or (Memo1.Lines.Count=0) or

(Edit2.Text='') or (Memo1.Lines.Count=0) then

ShowMessage('Введіть початкові дані')

else begin

n:=StrToInt(Edit1.Text);

for i:=1 to n do

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

m:=StrToInt(Edit2.Text);

for i:=1 to m do

b[i]:=StrToInt(Memo2.Lines[i-1]);

{Впорядкування за зростанням масиву А}

for i:=1 to n-1 do

begin k:=i;

for j:=i+1 to n do

if a[j]<a[k] then k:=j;

r:=a[i]; a[i]:=a[k]; a[k]:=r;

end;

{Впорядкування за зростанням масиву В}

for i:=1 to m-1 do

begin k:=i;

for j:=i+1 to m do

if b[j]<b[k] then k:=j;

r:=b[i]; b[i]:=b[k]; b[k]:=r;

end;

if ComboBox1.Text='Зростання' then

begin

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

i:=1; j:=1; k:=0;

while (i <= n) and (j <= m) do

if a[i] < b[j] then

begin k:=k+1; c[k]:=a[i]; i:=i+1;end

else

begin k:=k+1; c[k]:=b[j]; j:=j+1;end;

if i > n then

for i:=j to m do

begin k:=k+1; c[k]:=b[i]; end

else

for j:=i to n do

begin k:=k+1; c[k]:=a[j]; end;

end

else begin

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

i:=n; j:=m; k:=0;

while (i >= 1) and (j >= 1) do

if a[i] >= b[j] then

begin k:=k+1; c[k]:=a[i]; i:=i-1;end

else

begin k:=k+1; c[k]:=b[j]; j:=j-1;end;

if i < 1 then

for i:=j downto 1 do

begin k:=k+1; c[k]:=b[i]; end

else

for j:=i downto 1 do

begin k:=k+1; c[k]:=a[j]; end;

end;

{Виведення результату}

Edit3.Text:='';

Memo3.Lines.Clear;

Edit3.Text:=IntToStr(k);

for i:=1 to k do

Memo3.Lines.Add(IntToStr(c[i]));

end;

RadioButton4.Checked:=false;

end;

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

Розглянемо один з таких алгоритмів пошуку даних поділом масиву навпіл.

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

Спочатку упорядкуємо масив Х за зростанням елементів методом вибору.

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

Для реалізації описаного алгоритму упорядкування командою File|New Application створимо новий проект. Присвоїмо формі заголовок Пошук даних (властивість Caption). Командою File|Save All запишемо програмний модуль у файл з іменем ULAB5_2.pas, а проект – PLAB5_2.dpr.

Розробимо форму для введення початкових даних і виведення результату Рис.5.2.

Для введення початкових даних і виведення результату розмістимо на формі три компоненти Edit та два Memo.

Крім цього, розмістимо на формі дві керуючі кнопки (компонент Button) з написами Знайти, Вихід.

Обробник кнопки Знайти містяться у програмному модулі ULAB5_2 і мають вигляд:

Рис. 5.2 Форма Пошук даних

Unit ULAB5_2;

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

{Обробник кнопки Знайти}

procedure TForm1.Button1Click(Sender: TObject);

Var x: array[1..300] of integer;

kl, a, b, n, i, j, k, r: integer;

f:boolean;

Begin

{Введення початкових даних}

if (Edit1.Text='')or (Edit2.Text='') or

(Memo1.Lines.Count=0) then

ShowMessage('Введіть початкові дані')

else begin

n:=StrToInt(Edit1.Text);

for i:=1 to n do

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

kl:=StrToInt(Edit2.Text);

{Впорядкування масиву методом вибору за зростанням}

for i:=1 to n-1 do

begin k:=i;

for j:=i+1 to n do

if x[j]<x[k] then k:=j;

r:=x[i];

x[i]:=x[k];

x[k]:=r;

end;

{Пошук заданого елемента kl в упорядкованому масиві}

a:=1; b:=n; f:=false;

while (a <= b) and (not f) do

begin i:=(a+b) div 2; {под³л масиву навп³л}

if x[i] = kl then f:=true

else if x[i] < kl then a:=i+1

else if x[i] > kl then b:=i-1;

end;

{Виведення результату}

Memo2.Lines.Clear;

for j:=1 to n do

Memo2.Lines.Add(IntToStr(x[j]));

if f then Edit3.Text:=IntToStr(i)

else Edit3.Text:='Немає';

end;

end;