A. Consideratii teoretice

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:

In continuare se va prezenta un algoritm derivat din insertsort numit shellsort.


B. Exemple

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 }

C. Teme

  1. 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.

  2. 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.

  3. * Sa se scrie o procedura Quicksort nerecursiva (folosind o stiva) si sa se compare performanta ei cu metoda recursiva.