PureBasic Forumhttps://www.purebasic.fr/english/ Simple sorting of arrays with your own sort functionhttps://www.purebasic.fr/english/viewtopic.php?f=12&t=49484 Page 1 of 1

 Author: wilbert [ Sat Mar 17, 2012 7:30 am ] Post subject: Simple sorting of arrays with your own sort function Tested on Windows (XP, 7), OS X (Lion), Linux.Code:ImportC ""  qsort(*base, num, size, *comparator)EndImport Dim values.i(5)values(0) = 40values(1) = 10values(2) = 100values(3) = 90values(4) = 20values(5) = 25ProcedureC.i Compare(*a.Integer, *b.Integer)  ProcedureReturn *a\i - *b\iEndProcedureqsort(@values(), ArraySize(values()) + 1, SizeOf(Integer), @Compare())For n = 0 To 5  Debug values(n)Next

 Author: Demivec [ Sat Mar 17, 2012 7:45 am ] Post subject: Re: Simple sorting of arrays with your own sort function Tested on Windows XP.

 Author: wilbert [ Sat Mar 17, 2012 7:47 am ] Post subject: Re: Simple sorting of arrays with your own sort function Great that it works on XP also.Here's a multi field example, first sorted on age, second on name when age is equal.Code:EnableExplicitImportC ""  qsort(*base, num, size, *comparator)EndImport Structure Person  name.s  age.iEndStructureDefine nDim people.Person(5)people(0)\name = "John"people(0)\age = 40people(1)\name = "Charles"people(1)\age = 10people(2)\name = "Bart"people(2)\age = 10people(3)\name = "Richard"people(3)\age = 90people(4)\name = "Bob"people(4)\age = 20people(5)\name = "John Jr."people(5)\age = 25ProcedureC.i Compare(*a.Person, *b.Person)    Protected Result.i    Result = *a\age - *b\age    If Result = 0; same age ? => compare name    Result = CompareMemoryString(@*a\name, @*b\name)  EndIf    ProcedureReturn ResultEndProcedureqsort(@people(), ArraySize(people()) + 1, SizeOf(Person), @Compare())For n = 0 To 5  Debug people(n)\name  Debug people(n)\age  Debug ""NextTo prevent undefined results when compare results are equal, you probably could do a second comparison between the two pointers of the structures likeIf Result = 0Result = *a - *bEndIfThat probably should keep items in the original order.Unfortunately comparing the two pointers doesn't work

 Author: Little John [ Sat Mar 17, 2012 9:07 am ] Post subject: Re: Simple sorting of arrays with your own sort function Very cool. Thanks a lot!

 Author: rsts [ Sat Mar 17, 2012 5:55 pm ] Post subject: Re: Simple sorting of arrays with your own sort function Nice. And potentially very useful. Thanks for sharing.

 Author: wilbert [ Sun Mar 18, 2012 7:11 am ] Post subject: Re: Simple sorting of arrays with your own sort function skywalk wrote:Unfortunately, the qsort() function rearranges the indexes prior to calling the compare function so this won't work. After some more checking, you are right On OS X the behavior seems to be a bit different.

 Author: skywalk [ Sun Mar 18, 2012 8:12 am ] Post subject: Re: Simple sorting of arrays with your own sort function Hi wilbert,I edited my previous post to show the error.Look at the order of myABC\a before and after the different sorts.Thanks for posting this solution!This beats my mergesort approach by 100%! I retrieved each structure element as an array to mergesort() and then stuck them back in according to a sorted pointer array.Demivec's Multi-sort lib also beat my mergesort by ~70%, but requires more code and globals.This only requires:qsort(@myArr(), nPts, SizeOf(myABC), @cmp_myABC())And the code in cmp_myABC()Very nice and clean.Of course, we still have to code for specific structures...and that's a drag.

 Author: wilbert [ Sun Mar 18, 2012 8:21 am ] Post subject: Re: Simple sorting of arrays with your own sort function I also just updated my previous post You are right. My first tests were on OS X and the behavior is a bit different there when compare results are identical.I would love to hear if it works on Linux also. I think it should but I'm not sure.It is a clean solution but you are right about the structures.If an item could be used as an index for a map or something like that so you can add a field virtually, that might also work but I guess that's also not possible.

 Author: skywalk [ Sun Mar 18, 2012 8:35 am ] Post subject: Re: Simple sorting of arrays with your own sort function From what I read, qsort() is standard deployment in c libs.Side note.To do the speed test, I had to back out the CopyArray(myL1(),myL()) calls.The qsort() is notoriously bad with presorted arrays.So I didn't want to loop using the same sorted structured array.What shocked me was the qsort() completed 5 times faster than the copyarray() Not sure how can that be?

 Author: idle [ Sun Mar 18, 2012 7:16 pm ] Post subject: Re: Simple sorting of arrays with your own sort function wilbert wrote:I would love to hear if it works on Linux also. I think it should but I'm not sure.Yes it works on Linux!

 Author: wilbert [ Sun Mar 18, 2012 7:24 pm ] Post subject: Re: Simple sorting of arrays with your own sort function Thanks for checking Idle; nice to know it is fully cross platform.Since I upgraded Ubuntu, PB doesn't compile anymore for some reason so I couldn't check for myself.

 Page 1 of 1 All times are UTC + 1 hour Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Grouphttp://www.phpbb.com/