Forum > Beginners

QuickSort Problem

<< < (3/3)

Zoran:

--- Quote from: Handoko on June 15, 2022, 06:26:39 am ---Actually the problem was you're trying to provide non-zero-based array as an open array. Open array always count from 0 but your array (SouthHandArray) start from 1.

--- End quote ---

No! You got it quite wrong. The whole idea about open arrays is that you can safely pass static non-zero based arrays to a procedure which accepts open array parameter, as well as dynamic arrays.

But, inside that procedure, where it is accessed as an open array, you have to treat it as a zero-based array.

So, this works perfectly:


--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---program Project1; {$mode objfpc}{$H+} // You can safely call this procedure with any dynamic or static array whose index need not be zero-based.procedure PrintArray(A: Array of Int32);var  I: Integer;begin  for I := Low(A) to High(A) do begin    Write(A[I], ', ');  end;  WriteLn;end; procedure QuickSortInt32(var A: array of Int32);var  Pivot, N: Int32;   procedure InternalQSort(PFirst, PLast: PInt32);  var    PLeft, PRight: PInt32;  begin    PLeft := PFirst;    PRight := PLast;     Pivot := (PLeft + (PRight - PLeft) div 2)^;     repeat      while PLeft^ < Pivot do        Inc(PLeft);      while PRight^ > Pivot do        Dec(PRight);      if PLeft <= PRight then begin        N := PLeft^;        PLeft^ := PRight^;        PRight^ := N;         Inc(PLeft);        Dec(PRight);      end;    until PLeft > PRight;     if PRight > PFirst then      InternalQSort(PFirst, PRight);    if PLeft < PLast then      InternalQSort(PLeft, PLast);  end; var  P: PInt32;begin  if Length(A) >= 2 then begin // if array has less then two elements it's surely sorted already :)    P := PInt32(A);    InternalQSort(P, P + Length(A) - 1);  end;end; var  X: Array[1..20] of Int32;  I: Integer; begin  Randomize;  for I := Low(X) to High(X) do    X[I] := Random(200);   WriteLn('Array before sort:');  PrintArray(X); // send X as open array here!  QuickSortInt32(X); // again, send X as open array!  WriteLn('Array after sort:');  PrintArray(X); // and again!  ReadLn;end. 

JLWest:
Hi All
This is a lot to go through. I think Zoran is close to understanding the problem I have.
Writing a bridge simulator. Need to sort bridge hands of 13 cards which are held in 1 to 13 arrays. The first card in the deck is the 2 clubs and is 1 and the last is the Ace of spades is 52.
.

JLWest:
@Handoko

Works great.

BobDog:

Here is a general quicksort by pointer.

--- Code: Pascal  [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---// {$rangeChecks on}usessysutils;type direction =(up,down);   generic procedure quicksort<Z>(lp:pointer;rp:pointer;dr:direction);  var  p,i,l,r:^Z;  t:Z;  begin  l:=lp;  r:=rp;  if (r - l < 1) then exit;  p:=l+1;  i:=p;  while (p <= r) do  begin  if (dr=up) then      if (p^ < Z(l^)) then     begin     t:=p^;p^:=i^; i^:=t; i:=i+1;     end;   if (dr=down) then        if (p^ > Z(l^)) then     begin     t:=p^;p^:=i^; i^:=t; i:=i+1;     end;      p:=p+1;  end;  p:=i-1;  t:=Z(l^);Z(l^):=p^; p^:=t; specialize quicksort<Z>(l, p,dr); specialize quicksort<Z>(i, r,dr);end;  vara:array [3..23] of double;b:array of int32=nil;c:array [1..6] of ansistring=('abc','zxe','work','freepascal','zzq','aba');i:int32;t,t2:int64;beginfor i:=low(a) to high(a) do a[i]:=random*20; specialize quicksort<double>(@a[low(a)],@a[high(a)],down);writeln('Double [3..23] of random*20 sorted down');for i:=low(a) to high(a) do writeln(i,'   ',a[i]);writeln(); setlength (b,1000000); for i:=low(b) to high(b) do b[i]:=random(10000000); t:=gettickcount64; specialize quicksort<int32>(@b[low(b)],@b[high(b)],down); t2:=gettickcount64; writeln('Dynamic array of length 1000 Int32 of random(1000000) sorted down');for i:=low(b) to low(b) +10 do writeln(i,'   ',b[i]);writeln('...');writeln('...');for i:=high(b) -10 to high(b) do writeln(i,'   ',b[i]);writeln();writeln('Time taken for 1000000 int32 ',t2-t);writeln; specialize quicksort<ansistring>(@c[low(c)],@c[high(c)],up);writeln('ansistring [1..6] of preset values sorted up');for i:=low(c) to high(c) do writeln(i,'   ',c[i]);writeln;writeln('Press return to finish . . .'); readln;end.  

Navigation

[0] Message Index

[*] Previous page

Go to full version