При роботі з масивами найчастіше доводиться виконувати операції
сортування та пошуку даних. Від ефективності реалізації цих операцій часто
залежить ефективність всієї програми, тому розглянемо ці операції докладніше.
Сортування – це процес перегрупування даних у деякому заданому
порядку. Основна мета сортування – полегшити пошук потрібної інформації у
заданій послідовності даних.
Методи сортування масивів можна розбити на три категорії:
1. Сортування за допомогою включення.
2. Сортування за допомогою вибору.
3. Сортування за допомогою обміну.
Розглянемо вказані методи. Для визначеності будемо вважати, що
необхідно виконати сортування у порядку зростання елементів масиву, і всі
приклади, що будуть розглянуті відповідатимуть саме такому порядку
сортування.
При сортуванні за допомогою включення елементи умовно ділять на вже
відсортовану послідовність a1…ai-1 і вихідну послідовність ai…an. На кожному
кроці починаючи з i=2 та збільшуючи кожен раз i на одиницю, із вихідної
(початкової) послідовності видобувається i-тий елемент і перекладається в уже
готову послідовність. При цьому він вставляється в потрібне місце готової
послідовності. В процесі пошуку потрібного місця чергуються операція
порівняння даного елемента з елементами послідовності та операція
переміщення по послідовності, тобто вибраний елемент порівнюється з
черговим елементом aj , а тоді ai або вставляється на місце елемента aj (якщо виконано критерій сортування), тоді відповідно aj зміщується на одну позицію
вправо або ai порівнюється з наступним елементом aj-1 (якщо критерій
сортування не виконано), при цьому aj знову ж таки зміщується на одну
позицію вправо.
Приклад сортування методом включення
масиву восьми цілих чисел .
Для демонстрації на екран виводяться вихідний
масив, масив після кожного етапу вставки чергового елемента на потрібне
місце та результуючий масив.
Приклад:
uses crt;
const
n=8;
var
i,j,k:integer;
x:integer;
a:array[1..n] of integer;
begin
clrscr;
randomize;
for i:= 1 to n do
begin
a[i]:=random(256);
write (' ',a[i]);
end;
writeln;
writeln;
for i:=2 to n do
begin
x:=a[i];
j:=i;
while x < a[j-1] do
begin
a[j]:=a[j-1];
j:=j-1;
end;
a[j]:=x;
for k:=1 to n do
write(' ',a[k]);
writeln;
end;
writeln;
for i:=1 to n do
write(' ',a[i]);
readkey;
end.
Сортування за допомогою прямого вибору базується на нижчеперелічених
операціях:
1. Обирається елемент з найменшим значенням.
2. Цей елемент обмінюється місцями з першим елементом.
3. Потім п.1-2 повторюються з елементами від 2-го до n-го, потім від 3-го
до n-го і т. д.
Приклад сортування методом прямого вибору масиву восьми
цілих чисел .
Як і в попередньому прикладі для демонстрації на екран
виводяться вихідний масив, масив після кожного етапу вибору і обміну та
результуючий масив.
Приклад:
uses crt;
const n=8;
var
i,j,k,z:integer;
x:integer;
a:array[1..n]of integer;
begin
clrscr;
randomize;
for i:= 1 to n do
begin
a[i]:=random(256);
write (' ',a[i]);
end;
writeln;
writeln;
for i:=1 to n-1 do
begin
k:=i;
x:=a[i];
for j:= i+1 to n do
begin
if a[j] < x then
begin
k:=j;
x:=a[k];
end;
end;
a[k]:=a[i];
a[i]:=x;
for z:=1 to n do
write(' ',a[z]);
writeln;
end;
writeln;
for i:=1 to n do
write(' ',a[i]);
readkey;
end.
Сортування за допомогою обміну базується на процесі порівняння і при
необхідності обміну місцями двох сусідніх елементів масиву. Ці операції
повторюються доти, доки не буде упорядковано весь масив. Треба відмітити,
що після першого проходу по всьому масиву максимальний елемент
переміщається в крайнє праве положення, і на наступному етапі немає сенсу
перевіряти весь масив. Тому на практиці при першому проході перевіряють
елементи з номерами від 1 до n (останньго), на другому від 1 до (n-1) і т.д.
Приклад сортування методом обміну масиву восьми цілих чисел .
Як і в попередньому прикладі для демонстрації на екран виводяться вихідний
масив, масив після кожного проходу та результуючий масив.
Приклад:
uses crt;
const
n=8;
var i,j,k,d:integer;
tmp:integer;
a : array [1..n] of integer;
begin
ClrScr;
randomize;
for i:= 1 to n do
begin
a[i]:=random(256);
write (' ',a[i]);
end;
writeln;
writeln;
d:=n-1;
for j:=1 to n-1 do
begin
for i:=1 to d do
if ( a[i]>a[i+1]) then
begin
tmp:=a[i];
a[i]:=a[i+1];
a[i+1]:=tmp;
end;
d:=d-1;
for k:=1 to n do
write(' ',a[k]);
writeln;
end;
writeln;
for i:=1 to n do
write(' ',a[i]);
readkey;
end.
Пошук – це процес знаходження серед елементів даного типу елемента з
заданими властивостями.
Задане значення критерію пошуку називається ключем
пошуку.
Це може бути умова рівності елемента заданій величині або інша
умова.
При подальшому розгляді методів пошуку будемо вважати, що кількість
елементів даного типу, в якій провадиться пошук – відома і фіксована, тобто не
змінюється в процесі пошуку.
Найпростішим, але не самим оптимальним методом пошуку е прямий
лінійний пошук. Цей метод використовується тоді, коли немає ніякої
додаткової інформації про групу елементів серед якої провадиться пошук.
Метод полягає в послідовному перегляді всіх елементів і перевірці їх на
відповідність ключу пошуку. Умовою закінчення пошуку може бути або факт
знаходження даного елемента, або той факт, що дану сукупність елементів
перевірено повністю і не знайдено елементів, що відповідають критерію
пошуку.
Приклад:
uses crt;
const
arraysize=10;
type
massiv=array [1..arraysize] of integer;
var
searchkey,element,x:integer;
a:massiv;
{функція лінійного пошуку}
function linesearch(a:massiv ;key,sizeofarray:integer):integer;
var n:integer;
begin
for n:=1 to sizeofarray do
begin
if (a[n]=key) then
begin
linesearch:=n;
exit;
end;
end;
linesearch:=-1;
end;
{основна програма}
begin
clrscr;
{сформуємо випадковим чином масив з кількістю елементів, що
дорівнює величині arraysize і виведемо його на екран}
randomize;
for x:=1 to arraysize do
begin
a[x]:=random(256);
write(a[x],' ');
end;
writeln;
{отримаємо з клавіатури ключ пошуку}
writeln('input searchkey');
readln(searchkey);
{виконаємо пошук елемента масиву, що відповідає заданому ключу}
element:=linesearch(a,searchkey,arraysize);
{виведемо на екран результат пошуку}
if (element<>(-1)) then
writeln('found in a[',element,']') {елемент знайдено}
else
writeln('not found'); {елемент не знайдено}
readkey;
end.
Такий спосіб пошуку вимагає великих затрат машинного часу.
А чи можна
якось прискорити пошук потрібного елемента? Очевидно, що без додаткової
інформації про задану сукупність елементів, це неможливо. Проте пошук
можна зробити значно ефективнішим, якщо відомо, що задана послідовність
елементів є впорядкованою за критерієм пошуку.
Прикладом такої
впорядкованої послідовності може бути телефонний довідник, всі записи якого
впорядковано відповідно до абетки. Основною ідеєю пошуку у такій
послідовності є вибір деякого випадкового елемента і порівняння його з
критерієм пошуку.
При цьому може виникнути три випадки:
• елемент відповідає критерію пошуку. Тоді шуканий елемент знайдено і
пошук можна завершити;
• елемент має значення більше за величину ключа пошуку. Тоді треба
продовжити пошук у тій частині сукупності де значення менші за
значення обраного елемента;
• елемент має значення менше за величину ключа пошуку. Тоді треба
продовжити пошук у тій частині сукупності де значення більші за
значення обраного елемента.
При такій організації пошуку критерієм зупинки може бути або факт
знаходження даного елемента, або той факт, що дану сукупність елементів
перевірено повністю і не знайдено елементів, що відповідають критерію
пошуку.
Найпростішим способом реалізації такого алгоритму є метод поділу
пополам. При такому методі розглядувану послідовність ділять пополам і
порівнюють критерій пошуку з центральним елементом послідовності. Якщо
критерій співпадає, то елемент знайдено, якщо значення елементу менше за заданий критерій, то ділять пополам ту частину послідовності, де значення
елементів більше за значення обраного елемента, якщо ж воно більше, то ділять
ту половину де значення елементів менше за значення обраного елемента. Ці дії
виконують доти, доки не буде знайдено потрібний елемент, або поки у
досліджуваній частині сукупності не залишиться лише один елемент.
Оскільки
при цьому кожен раз кількість досліджуваних елементів зменшується вдвічі, то
швидкість пошуку значно зростає порівняно з лінійним пошуком.
Приклад:
uses crt;
const
arraysize=15;
type massiv=array[1..arraysize] of integer;
var
i,key,result:integer;
a:massiv;
{функція бінарного пошуку}
function binarysearch(b:massiv;searchkey,low,high,size:integer):integer;
var
middle:integer;
begin
while(low<=high) do
begin
{обираємо середній елемент}
middle:=round((low+high)/2);
if (searchkey=b[middle]) then
begin
binarysearch:=middle;{елемент знайдено}
exit;
end
else
begin
if(searchkey(-1)) then
writeln('found in a[',result,']'){елемент знайдено}
else
writeln('not found');{елемент не знайдено}
readkey;
end.
Немає коментарів:
Дописати коментар