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

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

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

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

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

На першому кроці визначимо значення найменшого елемента в усьому масиві (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;