Сортиране и търсене

Сортиране.

Много обработки на масиви от данни стават по-лесно и по-бързо, ако елементите им са подредени във нарастващ (възходящ) или в намаляващ (низходящ) ред на стойностите им.
Например търсенето на елемент с определена стойност е много по-лесно в подреден масив, отколкото в неподреден.

Процесът на подреждане на елементите на масив се нарича сортиране.

Създаването на втори масив, съдържащ същите стойности като началния, но сортирани, е по-лесно, но не представлява практически интерес. За икономия на оперативна памет се предпочита пренареждане на стойностите “на място”, т.е. вътре в масива.
Ясно е, че при сортиране на масив многократно се извършват две основни операции – сравняване стойностите на два елемента и размяна на стойностите на два елемента.
Всеки конкретен метод за сортировка определя стратегията на сравняване и размяна на елементите на масива. Броят на необходимите основни операции за сортирането на масив с N елемента определя ефективността (бързодействието) на метода.

Разработени са много методи за сортиране, притежаващи отделни предимства.
Те са:

Сортиране по метода на прякото вмъкване
Сортиране по метода на пряката селекция
Сортиране по метода на пряката размяна (метод на мехурчето)
Сортиране чрез вмъкване с намаляваща стъпка.
Пирамидално сортиране.

Сортиране по дялове(бързо сортиране)
Ще разгледаме само две от тях:.

Търсене

Често срещана в практиката задача е намирането в масив от данни мястото (индексът) на елемент със зададена стойност. В общия случай единственият начин е последователното сравняване на елементите на масива със зададената стойност, което е много бавен процес. Търсенето може значително да се ускори, ако масивът предварително е сортиран (за определеност - във възходящ ред на стойностите), защото може да се използва по-ефективен метод, например, така нареченото двоично (дихотомно) търсене.

Двоично търсене на елемент, равен на зададена стойност

Идеята на двоичното търсене се състои в последователното стесняване на половина на участъка от масива, в който се намира търсеният елемент.
Започва се с целия масив. Сравнява се търсената стойност с елемента, който е по средата на масива. Възможни са следните три случая:

стойностите са равни - търсеният елемент е намерен;
търсената стойност е по-малка - търсенето продължава в левия подмасив;
търсената стойност е по-голяма - търсенето продължава в десния подмасив.

След това по същия начин се търси в подмасива, после в негов подмасив и т.н. Процесът продължава до намиране на търсения елемент или до подмасив от нито един елемент (масивът не съдържа търсената стойност).

Алгоритъм, основаващ се на тази идея, е реализиран като функция от логически тип, която връща стойност True или False, в зависимост от това дали в масива е намерен или не е намерен елемент, равен на зададения.
При обръщане към функцията фиктивните параметри m и A се заместват съответно с броя на елементите и името на масива, в който става търсенето; B - със стойността, която търсим в масива, или името на променливата,чиято стойност търсим в масива; NomEl с променливата, на която искаме да се присвои индексът на намерения елемент. Локалните променливи N, K и S са индекси съответно на началния, крайния и средния елемент на подмасива, в който предстои търсене. Средният индекс се определя като цялата част на полусумата на началния и крайния индекс на подмасива.

Програма 1. Двоично търсене на стойност в подреден едномерен масив
Type
Danni=integer;
Msv=array[1..15] of danni;
Var
i,NomNamEl,BrEl:integer; B:Msv; X:danni;
Function DvTrsR(Br:integer;A:Msv;T:Danni;Var NomEl:integer):boolean;
Var
N,K,S:integer;
Begin
N:=1;K:=Br; DvTrsR:=false;
Repeat
S:=(N+K) div 2;
If T=A[s]
then begin
NomEl:=s; DvTrsR:=true; Exit
end;
If T>A[S]
then N:=S+1
else K:=S-1;
until N>K;
End;
Begin
Write(’Брой на елементите: ‘); Readln(BrEl);
Writeln(’Стойности на елементите:’);
For i:=1 to BrEl do begin Write(’ ‘,i,’ ‘); Readln(B[i]) end;
Writeln;Write(’Задайте търсена стойност X= ‘); Readln(X);
If DvTrsR(BrEl,B,X,NomNamEl)
then writeln(’Зададената стойност съвпада с ‘,NomNamEl,’-ия елемент’)
else writeln(’Няма такава стойност в масива.’);
Readln
End.

2.2. Двоично търсене на елемент, равен или по-голям от зададена стойност
В някои задачи се търси равен или най-близък по-голям елемент в масив. Алгоритъмът за намиране на такъв елемент чрез двоично търсене не се различава много от предходния. Функцията DvTrsPGR е от логически тип и връща стойност False, само когато търсената стойност е по-малка от първата или по-голяма от последната стойност на масива. При обръщане към функцията NamSt се замества с променливата, която трябва да върне намерената равна или най-близката по-голяма стойност в масива.
Програма 2. Двоично търсене в подреден масив на елемент, които е най-близък по-голям или равен на зададена стойност.
Type
Danni=integer;
Msv1=array[0..15] of danni;
Var
i,M:integer; B,C:Msv1; X,Y:danni;
Function DvTrsPGR(m:integer;Var A:Msv1;B:Danni;Var NamSt:Danni):boolean;
Var
N,K,S:integer;
Begin
If B>A[m]
then DvTrsPGR:=false
else begin if B<=A[1]
then S:=1
else begin
N:=1;K:=m;
Repeat
S:=(N+K) div 2;
If B>A[S]
then N:=S
else K:=S;
until (B=A[S]) or (K-N=1);
If B<>A[S] then S:=K
end;
NamSt:=A[S]; DvTrsPGR:=true
end
End;
Begin
Write(’Брой на елементите: ‘); Read(M);
Writeln(’Стойности на елементите:’);
For i:=1 to M do begin Write(’ ‘,i,’ ‘); Readln(B[i]) end;
Writeln;Write(’Задайте търсена стойност X= ‘); readln(X);
If DvTrsPGR(M,B,X,Y)
then Writeln(’Намеренaта най-близка по-голямa или равнa стойност е ‘,Y)
else Writeln(’Няма по-голяма или равна стойност.’);
Readln
End.

автор: Гьонюл Хакъева Мехмедова

No related posts.

Web design and SEO topics: база данни, данни, масиви, сортиране, търсене, функции

Web site categories: Компютри

Web Design Optimization