sorting an array of types

Previous topic - Next topic

Kitty Hello

Hi all,

in the next version, GLBasic will get functions to sort arrays. However, when you sort an array of TYPEs, there's a problem. What decides if something is bigger or smaller?
So, there's 2 ways:
- only compare the first member of the type
   + easy to understand
   + not to be mistaken
   + fast
   - might not suffice in some cases. e.g. sort via 'y', but on same y, sort via x
- compare then in ascending order, if the previous members are equal
   - slow!
   + better for complex sorting
- have the user define a "less than" function for that type
   - very complex for users
   - hard to implement :P

So, what are your thoughts on this?

Quentin

#1
good question. I think for the first step the simple form of sorting TYPE arrays will be sufficient.
what's about offering different sorting commands? One for simple, one for the complex way?

Here I found something interesting (perhaps) about sorting classes: (the 3rd reply is most interesting I think)

http://www.csharphelp.com/board2/read.html?f=1&i=47828&t=47828

it's in C#, but perhaps it could give you some ideas?

AndyH

I'm afraid for types to be sorted in arrays you might as not bother unless it can be completely defined by the user.  Too many assumptions and limitations with the others to be practical.

So the last option would be the only useful method from my point of view - eg: a function that takes two parameters of the types being sorted, the code in the function would determine if something is bigger or smaller, so I can use what ever simple or complex comparison of data in the type, and return True or false as the result.


bigsofty

Code (glbasic) Select
SortArray(MyArray[].typex, -1)

Sort array 'MyArray', using '.typex' as the comparison field, '-1' = decending?
Cheers,

Ian.

"It is practically impossible to teach good programming style to students that have had prior exposure to BASIC.  As potential programmers, they are mentally mutilated beyond hope of regeneration."
(E. W. Dijkstra)

bigsofty

Not really arrays but... I would prefer a insertion sort, say a binary tree with a 'key'...
Cheers,

Ian.

"It is practically impossible to teach good programming style to students that have had prior exposure to BASIC.  As potential programmers, they are mentally mutilated beyond hope of regeneration."
(E. W. Dijkstra)

MrTAToad

The best way would be to call a user-defined function (with a pointer two types) so they can work out which is greater (or not).  The problem with this is your going to pass two generic pointers (so it can deal with any type).

Sorting types is, unfortunately, better than just allowing sorting of arrays...

Kitty Hello

OK, how would you pass a pointer to that function?
Or make it fix like:

TYPE Tfoo
   x;y;number
ENDTYPE

// Hardcoded name: <Typename>Compare
FUNCTION TfooCompare: a AS Tfoo, b AS Tfoo
   IF a.x < b.x THEN RETURN -1
   IF a.x > b.x THEN RETURN 1
   // y is equal
   IF a.y < b.y THEN RETURN -1
   IF a.y > b.y THEN RETURN 1
   RETURN 0
ENDFUNCTION

MrTAToad

#7
Hard coding a function name would be the easiest way around it of course

Getting the function to the sort routine should theoretically work like working out where the jumpmark used by GOTO command (actually FUNCTION would be a better comparison) - it would also, of course, need the usual syntax checking too.

You would probably need some new datatype (probably equivilent to C's void function) that allows any type of type to be passed to it.

At each iteration two current records would be passed to this function, and the result returned from this is used to indicate how it should be sorted.  I presume you'll want to use Quicksort.


AndyH

Quote from: Kitty Hello on 2008-Sep-24
OK, how would you pass a pointer to that function?
Or make it fix like:

TYPE Tfoo
   x;y;number
ENDTYPE

// Hardcoded name: <Typename>Compare
FUNCTION TfooCompare: a AS Tfoo, b AS Tfoo
   IF a.x < b.x THEN RETURN -1
   IF a.x > b.x THEN RETURN 1
   // y is equal
   IF a.y < b.y THEN RETURN -1
   IF a.y > b.y THEN RETURN 1
   RETURN 0
ENDFUNCTION

That's looks good to me.  Alternatively couldn't you pass the function name as a parameter in the new sort command you'd implement?

Kitty Hello

Code (glbasic) Select

TYPE Tfoo
ENDTYPE

FUNCTION bar: a AS Tfoo, b AS Tfoo
RETURN -1
ENDFUNCTION

LOCAL arr[] AS Tfoo

SORTARRAY arr[], bar() // , bar ?, @bar ?, ADDRESSOF(bar) ?

It's not easy to do

Kitty Hello

Here's how I'm doing it. And it works. And it's easy for those who do not want to mess with it.
Code (glbasic) Select

LOCAL arr[]


// default sort
Fill(arr[])
SORTARRAY arr[], 0
FOR i=0 TO LEN(arr[])-1
PRINT arr[i], 0, i*16
NEXT

// sort by function
Fill(arr[])
SORTARRAY arr[], ADDRESSOF(compare)
FOR i=0 TO LEN(arr[])-1
PRINT arr[i], 100, i*16
NEXT

// inverse sort by function
Fill(arr[])
SORTARRAY arr[], ADDRESSOF(inverse_compare)
FOR i=0 TO LEN(arr[])-1
PRINT arr[i], 200, i*16
NEXT


SHOWSCREEN
MOUSEWAIT

FUNCTION Fill: arr[]
DIM arr[0]
FOR i=0 TO 10
DIMPUSH arr[], RND(100)
NEXT
ENDFUNCTION


FUNCTION compare: BYREF a, BYREF b
IF a<b THEN RETURN -1
IF a>b THEN RETURN 1
RETURN 0
ENDFUNCTION


FUNCTION inverse_compare: BYREF a, BYREF b
IF a<b THEN RETURN 1
IF a>b THEN RETURN -1
RETURN 0
ENDFUNCTION


Kitty Hello

the return value of ADDRESSOF is a DGNat natrual (an integer). Thus: ptr% = ADDRESSOF(foo) is OK.

You will have to provide a function for each field, because, you can sort backwards that way or sort texts as numbers first or whatever.