[es] - Implementacija QuickSort algoritma

reiser

Član broj: 7895
Poruke: 2314

+102 Profil

^{18.06.2006. u 19:15 - pre 217 meseci}

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.

Odgovor na temu

Srki_82
Srdjan Tot
Me @ My Home
Ljubljana

Član broj: 28226
Poruke: 1403
82.208.201.*

ICQ: 246436949

+10 Profil

Re: Implementacija QuickSort algoritma

^{19.06.2006. u 07:29 - pre 217 meseci}

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.

Play Store

Odgovor na temu

delalt

Član broj: 68360
Poruke: 198
*.teol.net.

Profil

Re: Implementacija QuickSort algoritma

^{19.06.2006. u 13:35 - pre 217 meseci}

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?

Odgovor na temu

reiser

Član broj: 7895
Poruke: 2314

+102 Profil

Re: Implementacija QuickSort algoritma

^{19.06.2006. u 14:11 - pre 217 meseci}

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

Odgovor na temu

IvanBeograd
Kladza
Beograd

Član broj: 83376
Poruke: 379
*.smin.sezampro.yu.

Sajt: www.dza-bu-drz-ne-daj.com

Profil

Re: Implementacija QuickSort algoritma

^{19.06.2006. u 15:00 - pre 217 meseci}

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

SERVIA NOSTRUM REGNUM!

Odgovor na temu

reiser

Član broj: 7895
Poruke: 2314

+102 Profil

Re: Implementacija QuickSort algoritma

^{19.06.2006. u 15:37 - pre 217 meseci}

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.. :)

Odgovor na temu

PeraKojotSuperGenije
Sasa Popovic
Beograd

Član broj: 44507
Poruke: 126
*.34.eunet.yu.

Profil

Re: Implementacija QuickSort algoritma

^{20.06.2006. u 02:17 - pre 217 meseci}

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.

Sendvic uvek pada na namazanu stranu!

Odgovor na temu

broker

Član broj: 2415
Poruke: 8514
212.62.59.*

+11 Profil

Re: Implementacija QuickSort algoritma

^{20.06.2006. u 05:40 - pre 217 meseci}

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.

Odgovor na temu