• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 454
  • Last Modified:

Sort an array

I have the following code

Type
   Students = record
   Name: String[255];
   Link: Array [0..3999] of cardinal;
   Level: Byte;
   Grade: Byte;
End;

What i want to do is to sort the array "Link" in ascending or descending order.

Anyone got a fast way to do that?

0
patera2
Asked:
patera2
  • 5
  • 3
  • 3
  • +3
5 Solutions
 
calinutzCommented:
0
 
gwalkeriqCommented:
0
 
HypoviaxCommented:
Here is an example of the fastest (i mean super fast) sort solutions in an EE competition held recently:

http://www.experts-exchange.com/Programming/Programming_Languages/Delphi/Q_21192509.html

Regards,

Hypoviax
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
Russell LibbySoftware Engineer, Advisory Commented:

It does not get any faster than what Hypoviax's q will provide for you ;-) ... that I can promise

But, just make sure you understand your data so you can apply the fastest sort. (data ranges, min / max if applicable, etc) Obviously the data size you provided above is fixed, so that eliminates some of the questions. (It will most likely be a counting sort that works best for you) . Just follow the q through and you will gain a WEALTH of knowledge regarding sorting in Delphi.

If you have further questions, just ask
--- do not accept this comment as an answer though ---

Regards,
Russell


0
 
patera2Author Commented:
BANG! - that was the sound my brain made when i read that post Hypoviax.

i am going to assume that the first one posted is the best one to use?

//SORT
Y:=-1;
X:=arraylength+1  ;
repeat
  dec(x) ;
   y:=-1;
   repeat
    inc(y) ;
       if item[y]>item[x] then
        begin
          temp:=item[y];
            item[y]:=item[x];
          item[x]:=temp;
        end;
   until y>=x ;
until X<=0;
//End SORT

The numbers to be sorted range from 0 to the maximum file size (4Gb) - still a good choice?
0
 
HypoviaxCommented:
Nono,

that is not the fastest by far, scroll down and have a look a russel's and alex's, they are the fastest.

Regards,

Hypoviax
0
 
HypoviaxCommented:
This is Alex's solution ( i do not claim credit) but it is very,very fast. You can configure this to sort an array of integers instead of a variant easily:

procedure SortingStuffWA2( var Items: Variant; MaxLength, MaxValue: Integer );
var
  I, J, K: Integer;
  Ticks: Int64;
  lpArray: PIntArray;
  lpList: PIntArray;
  ListSize: Integer;
begin
  Ticks := RDTSC;
  lpArray := VarArrayLock( Items );
  ListSize := ( MaxValue + 1 ) * SizeOf( Integer );
  GetMem( lpList, ListSize );
  for I := 0 to MaxValue do
    lpList^[ I ] := 0;
  for I := 0 to MaxLength do
    inc( lpList^[ lpArray^[ I ] ] );
  K := MaxLength;
  for I := MaxValue downto 0 do begin
    for J := 1 to lpList^[ I ] do begin
      lpArray^[ K ] := I;
      Dec( K );
    end;
  end;
  VarArrayUnlock( Items );
  FreeMem( lpList, ListSize );
  Ticks := RDTSC - Ticks;
  WriteLn( Ticks: 18, ' processor ticks required for Alex''s second solution.' ); //just to show speed
end;

Regards,

Hypoviax
0
 
HypoviaxCommented:
I must note that Russel's solutions (in the link i provided) are probably faster since you have a fixed data range

Regards,

Hypoviax
0
 
Russell LibbySoftware Engineer, Advisory Commented:

Sorry, but the couting sort is **probably** not the best one to use here (questioner replied with):

--
The numbers to be sorted range from 0 to the maximum file size (4Gb) - still a good choice?
--

This range is WAY to much to handle with a normal counting sort, and even a modifed couting sort (getting min and max from the data itself) may not be able to handle it. With only 4K items to sort, its also a little too much for the insertion/shell/bubble/linear type sorts to work very well either. Their quadratic nature makes them very ineffecient after about 100 items or so.

In my opinion, it would be best to pick a merge/heap/quick/sedge sort. In fact, the last posting in the referenced q has a nice example of SedgeSort, done iteratively as well (no recursion). All you would have to pass is the address of the data, and the count of items to sort.

//
// Get the defines for PIntArray in the referenced q.
//
// SedgeSortNR(Data: PIntArray; ArrayLength: Integer);
//

example usage:

var
  MyStudent: Students;

SedgeSort(@MyStudent.Link, 4000);

-------------

Regards,
Russell

0
 
HypoviaxCommented:
I support Russel's opinion. Have a look at his sedge sort, it is VERY fast comparitively to other sorts and would be suitable in your situation. The sort is towards the bottom of the referenced question so scroll right down

Regards,

Hypoviax
0
 
patera2Author Commented:
thanks - trying it out.
0
 
patera2Author Commented:
I couldn't get the SedgeSortNR routine to compile - maybe its because i'm using delphi 4.

I tried out some of the others though and took note of their timings - strange thing is i compared them to using the sort at http://www.swissdelphicenter.ch/torry/showcode.php?id=1616 that calinutz suggested - it was faster than any of the others i tested from the EE Competition.

Still testing though to make sure i got it right.
0
 
Russell LibbySoftware Engineer, Advisory Commented:
READ ** ALL *** the notes from the competition to get the big picture please.

It may be that a Shell sort works well for your situation, as the number of elements is fairly low. The lower end sorts do work well to a point, and shell sort is one of the faster quadratic routines, but make no mistake... it is quadratic in nature. If you tried to use Shell sort on 1 million items you would be waiting long after the quick/merge/sedge sort were done.

As I tried to state in the referenced q, you must be familiar with the type/size/quantity of data you wish to sort. Only then can you determine what  sort routine will work best for you. If you are unable to quantify this, then you are forced to choose a generic sort routine: in those cases, quick/sedge sort are usually the preferred choices.

If you find that the shell sort works best for you situation, then go with it. It was only my intention to make you aware of the wide variety of sorts that exists out there, and to provide working examples of them. Also, if you would care to share your compiler error with the sedge sort routine, then I am sure I could help

Russell




0
 
SaLzCommented:
sort demo

function RandomPassword(PLen: Integer): string;
var
  str: string;
begin
  Randomize;
  str    := '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
  Result := '';
  repeat
    Result := Result + str[Random(Length(str)) + 1];
  until (Length(Result) = PLen)
end;

procedure TForm1.FormCreate(Sender: TObject);
var
  Store: TStringList;
  i:integer;
begin
Store := TStringList.Create;
for i:= 1 to 50 do begin
Store.Add(RandomPassword(20));
end;
Store.Sort;
memo2.Lines.Add(Store.Text);
Store.free;
end;
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

  • 5
  • 3
  • 3
  • +3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now