[ Alchemi5t @ 11.03.2005. 17:50 ] @
Jel mi možete reci kako da najbrze sortiram podatke u Pascalu? Tj. kako se to radi sa quick sort????
A može i jos nesto ako se može i brže sortirati jer je vremensko ograničenje 2s.
[ vlaiv @ 11.03.2005. 18:06 ] @
quick sort radi po sledecem principu:


podelis niz u dva pod niza (po nekom kriterijumu, moze recimo sredina niza, a obicno se i to koristi)

sve "vece" elemente prebacis u "gornji" niz a sve "manje" u donji niz i onda rekurzivno sortiras svaki od ova dva pod niza na isti nacin ...

Evo nekog primera koji sam iscupao na netu:

Code:

const  maxN = 50;

var a  : array[1..maxN] of integer;
    N  : integer;

procedure quicksort(L,R :integer);
var i,j       : integer;
    t,v,v1,v2,v3  : integer;
begin
if L<R then
 begin
   v:=a[R];
   i:=L-1;
   j:=R;
   repeat
     repeat  i:=i+1  until ( a[i] >= v );
     repeat  j:=j-1  until ( a[j] <= v );
     t:=a[i];  a[i]:=a[j];  a[j]:=t;
   until j<=i;
   a[j]:=a[i];
   a[i]:=a[R];
   a[R]:=t;
   quicksort(L,i-1);
   quicksort(i+1,R);
 end;
end;

// poziva se sa

quicksort(1,maxN);


Zavisi od potreba sortiranja, quick sort nije uvek najbolje resenje ...

Ako su u pitanju vrednosti koje se lako porede registarski, postoje i brze metode -radix sort i slicno ... koji na primer sortira bilo cele brojeve, bilo stringove (on se zapravo oslanja na neki drugi sort) ali prvo proverava i smesta u istu grupu sve stringove koji pocinju istim slovom odnosno brojeve koji na odredjenoj poziciji imaju istu cifru ... pa onda svaku od grupa rekurzivno ponavlja gledajuci sledece slovo/cifru u pozicionom zapisu ...