Recent

Author Topic: Universal Sort in Lazarus / Freepascal  (Read 15277 times)

Mike.Cornflake

  • Hero Member
  • *****
  • Posts: 1260
Re: Universal Sort in Lazarus / Freepascal
« Reply #15 on: November 12, 2017, 05:29:46 pm »
Code: [Select]
  if Result = 0 then
  begin
     if ARecord1.String5 < ARecord2.string5 then
     begin
        Result := -1
     end else
     // FELD 2
     begin
        if ARecord1.Field2 > Arecord2.Field2 then
        begin
           Result := 1;
        end else
        begin
           if ARecord1.Field2 < ARecord2.Field2 then
           begin
              Result := -1
           end else

Looking at your code I see you're implementing a Quick Sort and an external compare function already.    So right from the start you're on the track that myself and several others have suggested.  Oops, apologies for missing that in your first post.

In order to use BeniBela's code you just to make small changes to your Compare function (change paramters etc).

But now I've looked at your code closely, I think there may be errors in your Compare function (which is why I highlighted it above).   Your compare function is going to result in a dataset that would not look sorted to me.  You're falling from one case to the next if one string is not less than the other.  For traditional sort implementations you usually only compare subsequent strings when the previous strings are identical.  You do this for Field2, but not for Field5

Have a look at @soerensen3's implementation for an example.

  Result:= CompareStringField( Field1, AObj.Field1 );
  if ( Result = 0 ) then
    Result:= CompareStringField( Field2, AObj.Field2 );
  if ( Result = 0 ) then
    Result:= CompareStringField( Field3, AObj.Field3 );
  if ( Result = 0 ) then
    Result:= CompareIntField( Field4, AObj.Field4 );
end;[/code]

I think if you refactor your Compare function so it's got same general shape as @soerensen3's, you'll find you've been on a good track all along. 

And I don't think you'll need the internal CompareStringField.  Freepascal already comes with string comparison routines.
https://www.freepascal.org/docs-html/rtl/sysutils/comparestr.html (see also the See Also's :-) )
« Last Edit: November 12, 2017, 05:34:58 pm by Mike.Cornflake »
Lazarus Trunk/FPC Trunk on Windows [7, 10]
  Have you tried searching this forum or the wiki?:   http://wiki.lazarus.freepascal.org/Alternative_Main_Page
  BOOKS! (Free and otherwise): http://wiki.lazarus.freepascal.org/Pascal_and_Lazarus_Books_and_Magazines

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: Universal Sort in Lazarus / Freepascal
« Reply #16 on: November 12, 2017, 09:54:27 pm »
data structures should not matter. "What does something need to define as function to be sorted ?"

Sorted how? And how about multi key sorting, like the OP hints on?

Quote
that's all that matters. Things that can be sorted should implement these functions and it works.

Oversimplification. 

lainz

  • Hero Member
  • *****
  • Posts: 4460
    • https://lainz.github.io/
Re: Universal Sort in Lazarus / Freepascal
« Reply #17 on: November 12, 2017, 11:08:32 pm »
data structures should not matter. "What does something need to define as function to be sorted ?"

Sorted how? And how about multi key sorting, like the OP hints on?

Quote
that's all that matters. Things that can be sorted should implement these functions and it works.

Oversimplification. 

Well, I don't want to reply in the name of the quoted user.

But...

Actually with something like JavaScript array sort or Java Comparable / Comparator the method decides how to sort.

You can sort by many fields you need. Like

if (a.field1 > b.field1)
return 1
if (a.field1 < b.field1)
return -1
if (a.field2 < b.field2)
return 1
if (a.field2 > b.field2)
return -1
return 0

that's by two fields, and one can be in one order and the other in another order. the order of "asc" or "desc" you define in the method.

You can have descending by name and ascending by a number, for example. So if you have 2 duplicate product names and want to sort by name also by higher price first, you can do that simply.

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • FPC developer.
Re: Universal Sort in Lazarus / Freepascal
« Reply #18 on: November 13, 2017, 10:17:19 am »
data structures should not matter. "What does something need to define as function to be sorted ?"

Sorted how? And how about multi key sorting, like the OP hints on?

Quote
that's all that matters. Things that can be sorted should implement these functions and it works.

Oversimplification. 

Well, I don't want to reply in the name of the quoted user.

But...

Actually with something like JavaScript array sort or Java Comparable / Comparator the method decides how to sort.

or with https://www.freepascal.org/docs-html/rtl/classes/tlist.sort.html

It is just that you need to define a method/comparator.  Tlist doesn't require a swap because the sizes are uniform (all pointers)

lainz

  • Hero Member
  • *****
  • Posts: 4460
    • https://lainz.github.io/
Re: Universal Sort in Lazarus / Freepascal
« Reply #19 on: November 13, 2017, 03:04:51 pm »
or with https://www.freepascal.org/docs-html/rtl/classes/tlist.sort.html

It is just that you need to define a method/comparator.  Tlist doesn't require a swap because the sizes are uniform (all pointers)

That's it. In fact the main problem here was how to implement the compare function, not a missing feature.

Pointers or Object is just OK. But we have generics also?, something like supply the type and implement a typed method, I know that only adds sugar to the code, it's just an idea. But having already working code in the rtl is enough.

So again, the way I do is returning the function when the first condition becomes true, instead of putting a lot of concatenated if like in the first post code. It is faster that way.

Edit: I mean returning like this
https://stackoverflow.com/questions/9641652/returning-a-value-in-pascal
« Last Edit: November 13, 2017, 03:10:13 pm by lainz »

 

TinyPortal © 2005-2018