Sortarea (ordonarea dupa un anumit criteriu) este o operatiune des
executata in timpul procesarii datelor, indiferent de tipul aplicatiilor
(stiintifice, economice sau de sistem). S-a observat ca este o operatie foarte
costisitoare ca timp de calcul, in timpul executarii ei fiind necesare multe
comparatii si interschimbari.
De aceea s-a cautat inventarea unor algoritmi cat mai performanti care sa
dureze cat mai putin.
La curs s-au prezentat algoritmii:
-
bubblesort - sortare cu interschimbare;
-
shakersort - sortare cu interschimbare si parcurgere in ambele directii;
-
quicksort - sortare prin partitionareprintr-un algoritm recursiv de
divide and conquer.
In continuare se va prezenta un algoritm derivat din insertsort numit
shellsort.
Pentru aceasta sortare se foloseste un tablou auxiliar (H) de lungime T
care contine o serie de incrementi. Nu exista o metoda matematica pentru
calcularea acestora, dar Knuth sugereaza ca cele mai potrivite seriile: (in
ordine descrescatoare) ht=1 si seria 1, 4, 13, 40, 121, hk-1=3*hk+1,
t=log3n - 1 sau ht=1 si seria 1, 3, 7, 15, 31, hk-1=2*hk+1,
t=log2n - 1.
Se observa ca (***) tabloul de ordonat trebuie sa fie mai lung la stanga cu
h1. Deci se declara cu:
var
A: array [-40..N] of integer;
procedure shellsort;
const T=4;
var
i,j,k,s: integer; { indici }
x: integer: { element de interschimbare }
M: 1..T;
H: array [1..4] of integer;
begin
H[1] :=40;
H[2] :=13;
H[3] :=4;
H[4] :=1;
for M:=1 to T do
begin
k:=H[M];
s:=-H[M]; { *** }
for i:=k+1 to N do
begin
x:=A[i];
j:=i-k;
if s=0 then s:=-k;
s:=s+1;
A[s]:=x;
while x<A[j] do
begin
A[j+k]:=A[k];
j:=j-k;
end;
A[j+k]:=x
end
end
end; { shellsort }
|
-
Sa se scrie un program care genereaza un sir de numere intregi n<i>,
i=1..500, in mod aleator, astfel incat n<i>=0..32767 (MaxInt=32767 -
constanta predefinita Pascal). Acest sir va fi ordonat de mai multe ori,
folosind toti algoritmii de sortare cunoscuti si pentru fiecare metoda se va
masura timpul de executie.
Se vor afisa metodele in ordinea performantelor obtinute (prima afisata -
cea mai buna metoda) impreuna cu timpii de executie (in sutimi de secunda).
Se vor folosi urmatoarele proceduri si functii predefinite:
-
Randomize - initializeaza generatorul de numere aleatoare;
-
Random (valoare) - functie care returneaza un numar n, generat
aleator, cuprins intre 0 si valoare;
-
GetTime(var h,m,s,cs:word) - returneaza timpul curent.
-
Sa se ruleze acest program pentru i=1..5000 si sa i se determine
raportul:
k=(timp_executie5000/lungime_sir5000)/(timp_executie500/lungime_sir500)
pentru fiecare metoda.
-
* Sa se scrie o procedura Quicksort nerecursiva (folosind o stiva) si sa
se compare performanta ei cu metoda recursiva.