Implementacija QuickSort algoritma

[ reiser @ 18.06.2006. 19:15 ] @

Treba mi implementacija quicksort algoritma koja moze da sortira nizove bilo kog tipa i duzine. (integer, char, string itd..)
Pokusavao sam nesto da napravim, ali nisam daleko odmakao..

Code:

procedure QuickSort(const AArray : pointer; const AElementSize : Byte; const AElementsCount : Integer);
var
  VLeft, VRight : pointer;
  pivot         : pointer;
  tmp           : pointer;
begin
  VLeft := AArray;  VRight := pointer(LongInt(AArray) + AElementSize * (AElementsCount - 1));
  GetMem(pivot, AElementSize);
  CopyMemory(pivot, pointer(LongInt(VLeft) + AElementSize * (AElementsCount div 2)), AElementSize);
  GetMem(tmp, AElementSize);

  repeat
    CopyMemory(tmp, VLeft, AElementSize);
    While Variant(tmp^) < Variant(pivot^) Do
      VLeft := pointer(LongInt(VLeft) + AElementSize);
    CopyMemory(tmp, VRight, AElementSize);
    While Variant(tmp^) > Variant(pivot^) Do
      VRight := pointer(LongInt(VRight) - AElementSize);

    If LongInt(VLeft) <= LongInt(VRight) Then
    Begin
      CopyMemory(tmp, VLeft, AElementSize);
      CopyMemory(VLeft, VRight, AElementSize);
      CopyMemory(VRight, tmp, AElementSize);
      VLeft := pointer(LongInt(VLeft) + AElementSize);
      VRight := pointer(LongInt(VRight) - AElementSize);
    End;
  until LongInt(VLeft) > LongInt(VRight);

  If LongInt(AArray) < LongInt(VRight) Then QuickSort(AArray, AElementSize, (LongInt(VRight) - LongInt(AArray)) div AElementSize);
  If LongInt(VLeft) < LongInt(AArray) + AElementSize * AElementsCount Then QuickSort(VLeft, AElementSize, LongInt(AArray) + AElementSize * AElementsCount);
end;

var
  arr : Array[1..10] of Integer;
  C1  : Integer;

begin
  Randomize;
  For C1 := 1 to 10 Do
    arr[C1] := Random(10);

  QuickSort(@arr[1], SizeOf(Integer), 10);
end.

[ Srki_82 @ 19.06.2006. 07:29 ] @

Tesko da ces moci da napises jednu funkciju koja ce da sortira sve nizove... zamisli da imas niz klasa... cistim uporedjivanjem dve vrednosti neces dobiti nikakav prihvatljiv rezultat. Verovatno ce trebati da ih sortiras po nekom property-u. Moguce je da sortiras i record-e... opet ces verovatno hteti da ih sortiras po nekom polju. Zatim mozes zeleti da neki text sortiras po azbucnom, a neki po abecednom redu.

Ja sam taj problem resio na sledeci nacin. Napravio sam QuickSort funkciju koja uzima niz bilo kojih elemenata. Od ulaznih podataka joj se prosledjuju niz podataka i funkcija koja kaze da li su dva podatka razlicita (prvi veci od drugog, ili drugi veci od prvog) ili jednaka i na osnovu te funkcije vrsi sortiranje.

[ delalt @ 19.06.2006. 13:35 ] @

Citat:

Srki_82: Ja sam taj problem resio na sledeci nacin. Napravio sam QuickSort funkciju koja uzima niz bilo kojih elemenata. Od ulaznih podataka joj se prosledjuju niz podataka i funkcija koja kaze da li su dva podatka razlicita (prvi veci od drugog, ili drugi veci od prvog) ili jednaka i na osnovu te funkcije vrsi sortiranje.

Može li se vidjeti taj tvoj način?

[ reiser @ 19.06.2006. 14:11 ] @

Recimo da mi nije potrebno sortiranje klasa, recorda itd.. Dakle samo 1D nizovi tipa String, Integer, Char itd.. Moze li se to odraditi ?

[ IvanBeograd @ 19.06.2006. 15:00 ] @

http://theorie.informatik.uni-.../Lehre/PI/Programme/quick.html

Mi smo na fax-u pricali o tome sta qsort moze da sortira.
Sa qsort-om moze da se sortira bukvalno sve,jer imamo genercki pokazivac koji moze da se kastuje u bilo koji tip,najbitnije od svega je f-ja za poredenje.Meni je fino posao odradila f-ja iz linka,ali ona nije pravi quick sort,nisam nasao isti qsort u pascalu kao sto postoji u c-u nego neke izvedene f-je.
Sta zelisi tacno sortirati?Ako znas sta tacno sortiras,qsort je dobar jer sortira sve,ali ako znas sta zelis sortirati,npr brojeve radex sort ti je najmocniji i najbrzi(sto se tice sortiranja velikih brojeva),...
Pozzz

[ reiser @ 19.06.2006. 15:37 ] @

Ma jednostavno mi treba neka fja koja moze da sortira nizove bilo kog tipa.. String, char, integer, cardinal..., ne mora da podrzava "egzoticne" tipove - recorde, klase itd.. :)

[ PeraKojotSuperGenije @ 20.06.2006. 02:17 ] @

U C++ postoji jedna fenomenalna stvar, koja ObjectPascalu/Delphiju veoma nedostaje - TEMPLATE FUNCTION. Druga je preklapanje operatora. Bez te dve stvari tvoj problem je neresiv (bar ne elegantno).

Srki_82 je dao dobar predlog.

Ako neces tako da radis preostaje ti samo da napravis onoliko primeraka preopterecene proc/func QuickSort za koliko razlicitih tipova ti je potrebno sortiranje.

[ broker @ 20.06.2006. 05:40 ] @

reiser ne citas st ati kazu. Komplikovano je da pravis funkciju koja ce da poredi bilo sta, a i tesk da to moze a bude efikasno kao funkcije koje porede konkretne tipove.

Napravi posebne funkcijez aporedjenje zavisno od tipa podataka i onda koristi onu koja odgovara tipu koji sortiras.

[ Rapaic Rajko @ 24.06.2006. 07:46 ] @

Pogledati u VCL-u klasu TList i njenu metodu TList.Sort(). Resenje problema se vec samo nudi, uz malo dovijanja.

Rajko

[ reiser @ 26.06.2006. 23:52 ] @

Hvala Rajko, pogledacu.