Implementacija QuickSort algoritma

Implementacija QuickSort algoritma 18.06.2006. u 20:15 · pre 247 meseci #1

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.

Re: Implementacija QuickSort algoritma 19.06.2006. u 08:29 · pre 247 meseci #2

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.

Potpis

Play Store

Re: Implementacija QuickSort algoritma 19.06.2006. u 14:35 · pre 247 meseci #3

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?

Re: Implementacija QuickSort algoritma 19.06.2006. u 15:11 · pre 247 meseci #4

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

Re: Implementacija QuickSort algoritma 19.06.2006. u 16:00 · pre 247 meseci #5

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

Potpis

SERVIA NOSTRUM REGNUM!

Re: Implementacija QuickSort algoritma 19.06.2006. u 16:37 · pre 247 meseci #6

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

Re: Implementacija QuickSort algoritma 20.06.2006. u 03:17 · pre 247 meseci #7

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.

Potpis

Sendvic uvek pada na namazanu stranu!

Re: Implementacija QuickSort algoritma 20.06.2006. u 06:40 · pre 247 meseci #8

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.

Re: Implementacija QuickSort algoritma 24.06.2006. u 08:46 · pre 247 meseci #9

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

Rajko

Re: Implementacija QuickSort algoritma 27.06.2006. u 00:52 · pre 247 meseci #10

Hvala Rajko, pogledacu.

Forum kao aplikacija na telefonu

Srodne teme