Solved

# Sort an array

Posted on 2004-11-12
450 Views
I have the following code

Type
Students = record
Name: String[255];
Level: 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
Question by:patera2

LVL 11

Accepted Solution

0

LVL 6

Assisted Solution

0

LVL 5

Assisted Solution

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

LVL 26

Assisted Solution

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

Author Comment

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

LVL 5

Expert Comment

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

LVL 5

Expert Comment

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

LVL 5

Expert Comment

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

LVL 26

Expert Comment

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;

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

Regards,
Russell

0

LVL 5

Expert Comment

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

Author Comment

thanks - trying it out.
0

Author Comment

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

LVL 26

Expert Comment

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

LVL 2

Assisted Solution

sort demo

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
end;
Store.Sort;
Store.free;
end;
0

## Featured Post

Introduction I have seen many questions in this Delphi topic area where queries in threads are needed or suggested. I know bumped into a similar need. This article will address some of the concepts when dealing with a multithreaded delphi database…
Introduction Raise your hands if you were as upset with FireMonkey as I was when I discovered that there was no TListview.  I use TListView in almost all of my applications I've written, and I was not going to compromise by resorting to TStringGrid…
In this sixth video of the Xpdf series, we discuss and demonstrate the PDFtoPNG utility, which converts a multi-page PDF file to separate color, grayscale, or monochrome PNG files, creating one PNG file for each page in the PDF. It does this via a c…
Illustrator's Shape Builder tool will let you combine shapes visually and interactively. This video shows the Mac version, but the tool works the same way in Windows. To follow along with this video, you can draw your own shapes or download the file…