PureBasic Forums - English

Posted: **Mon Mar 03, 2003 7:22 pm**

Restored from previous forum. Originally posted by Kale.

Is it possible to add an easy to use, fast function for sorting linked lists? especially lists of a user defined structure?

Code: Select all

Structure person
    name.s
    starsign.s
    age.l
EndStructure
NewList people.person()
for x=1 to 5
  AddElement(people())
next x

now after this has been populated with all information about a familiy etc... can a function be added to sort this list by the relevant fields of the structure? say if i want to sort the list to display the eldest person, or the youngest, or in alphabetical order of their names? maybe something like:

#PB_SORTLIST_DOWN ; 0-9, a-z sorting
#PB_SORTLIST_UP ; 9-0, z-a sorting

SortList(list, direction [, field])

Code: Select all

SortList(people(), #PB_SORTLIST_DOWN , name)

I would be grateful if you (Fred) could have a think about this one as many seem to request it

Thanks,

--Kale

In love with PureBasic!

Posted: **Mon Mar 03, 2003 7:58 pm**

Restored from previous forum. Originally posted by tinman.

Originally posted by Kale

relevant fields of the structure? say if i want to sort the list to display the eldest person, or the youngest, or in alphabetical order of their names? maybe something like:

#PB_SORTLIST_DOWN ; 0-9, a-z sorting
#PB_SORTLIST_UP ; 9-0, z-a sorting

That's a fairly specific sorting request and does not really fit in with the alphabetical sorting of strings. Much better to have a sort system where you have some standard sorts and perhaps a way to extend it (yes, I can hear people crying about how "difficult" it would be to use).

In the meantime you would be much better to use my sort_extras code snippet from the Resources Site (plug plug plug

It would definately be better to have some proper commands for it though.

I would be grateful if you (Fred) could have a think about this one as many seem to request it

Fred is free to my code if he wants, although I wouldn't be able to convert it to ASM

--
I used to be a nihilist but I don't believe in that any more.
(Win98first ed. + all updates, PB3.51, Ed3.53)

Posted: **Mon Mar 03, 2003 8:55 pm**

Restored from previous forum. Originally posted by Kale.

That's a fairly specific sorting request and does not really fit in with the alphabetical sorting of strings. Much better to have a sort system where you have some standard sorts and perhaps a way to extend it (yes, I can hear people crying about how "difficult" it would be to use).

yeah your right, i want Fred/people to have a think about what could be done

--Kale

In love with PureBasic!

Posted: **Sat Mar 08, 2003 5:18 pm**

Restored from previous forum. Originally posted by SimpleMind.

Hi Kale,

There is something you can use. But you have to code it. An index file to your structure. But it can even better an index that is part of your structure. I've been interested in B+Trees since years but I myself find them to difficult to code. About ten years ago I saw some c code in Dr. Dobbs that could do the job even better and faster than B+Trees. They are called skipList. You can use the list of PureBasic added with the skiplist structure and added with your own data structure.
I've been bussy with this code some weeks ago and have some starter code which is born from the cookbook. It's incredibly fast and very easy to code

so now i'm in the debugging fase. With the information supplied hereafter you will get an impression of it.

;Skiplist are an invention of:
;William Pugh. Skip lists: A probabilistic alternative to balanced trees.
;Communications of the ACM, 33(6):668-676, June 1990.
;You can visit him at his site, http://www.cs.umd.edu/~pugh/
;Other information resources of interest about skiplists.
;[url]http://studhttp://www.rug.ac.be/~prdsutte/cookbook.pdf" target="_blank[/url]
;http://www.planetoid.org/technical/sort ... /booke.pdf

Succes!

SimpleMind,

Perfection is reached not when there is no longer anything to add,
but when there is no longer anything to take away. (A. Saint-Exupery)

- Registered PureBasic Coder. -

Posted: **Thu Mar 27, 2003 12:29 pm**

Restored from previous forum. Originally posted by Kale.

Fred, have you any thoughts on PB Commands for Linked List sorting???

--Kale

In love with PureBasic!

Posted: **Thu Mar 27, 2003 2:12 pm**

Restored from previous forum. Originally posted by fred.

On my TODO list, yes. But don't know when, it need some compiler changes.

Fred - AlphaSND

Posted: **Thu Mar 27, 2003 5:42 pm**

Restored from previous forum. Originally posted by Kale.

Ok thanks Fred

--Kale

In love with PureBasic!

Posted: **Thu Mar 27, 2003 5:46 pm**

Restored from previous forum. Originally posted by tinman.

Originally posted by fred

On my TODO list, yes. But don't know when, it need some compiler changes.

Just out of curiosity, what needs changed. Wouldn't new sorting commands just need commands added to the sort library?

--
I used to be a nihilist but I don't believe in that any more.
(Win98first ed. + all updates, PB3.62, external editor)

Posted: **Mon Mar 31, 2003 4:29 pm**

Restored from previous forum. Originally posted by horst.

I think a sort function can be very simple, if the actual compare
operation is an external function written by the programmer.
This means, the programmer can write any code he wants to decide
whether two given elements are in the right order or not.

The user defined function may handle any type of variable, and do
any kind of conversions. Since the original elements with the original
structure are passed as parameters, the procedure will be transparent,
and in most cases trivial, like this:

Code: Select all

Procedure ByNameAscending(*a.test,*b.test) 
  If *a\name <= *b\name : result = #true : EndIf 
ProcedureReturn result 
EndProcedure

Or sorting by Name AND City, for example:

Code: Select all

Procedure ByNameAndCity(*a.test,*b.test) 
  If *a\name < *b\name or (*a\name = *b\name and *a\city <= *b\city)
    ProcedureReturn #true 
  EndIf 
EndProcedure

The procedure to apply is passed to the sort by pointer, for example:
SortList(LinkedList(),@ByNameAscending())
No other parameters are necessary.

Demo (with bubble sort):
http://home.mnet-online.de/horst.muc/pb/llsort.zip

Horst

Posted: **Mon Mar 31, 2003 5:11 pm**

Restored from previous forum. Originally posted by tinman.

Originally posted by horst

I think a sort function can be very simple, if the actual compare
operation is an external function written by the programmer.
This means, the programmer can write any code he wants to decide
whether two given elements are in the right order or not.

That is basically what my sort routines on the resources site do. It is all set up for sorting arrays and lists using various algorithms and provides comparison functions for all the basic types. There are a few demos too.

--
I used to be a nihilist but I don't believe in that any more.
(Win98first ed. + all updates, PB3.62, external editor)

Posted: **Tue Apr 01, 2003 5:26 pm**

Restored from previous forum. Originally posted by horst.

> That is basically what my sort routines on the resources site do.

Yes, but I had a very simple solution im mind, that requires no
extra parameters, and where the complete elements are available in
the comparison function.

Just an experiment, maybe easier to implement for Fred.
However, the Quicksort will probably be a little more complicated..

Horst

Posted: **Tue Apr 01, 2003 10:00 pm**

Restored from previous forum. Originally posted by tinman.

Originally posted by horst

> That is basically what my sort routines on the resources site do.

Yes, but I had a very simple solution im mind, that requires no
extra parameters, and where the complete elements are available in
the comparison function.

The code I wrote gives full access to the complete elements. Hoever, I agree that the function calls could be simpler, especially since most parameters are e.g. size of arrays, size of structures, etc. Hopefulyl PB would be able to work this out for itself.

--
I used to be a nihilist but I don't believe in that any more.
(Win98first ed. + all updates, PB3.62, external editor)

Posted: **Thu Apr 03, 2003 5:07 pm**

Restored from previous forum. Originally posted by horst.

New experimental QuickSort for Linked Lists here:
http://home.mnet-online.de/horst.muc/pb/lqsort.zip

Maybe this will supply some new ideas to Fred for a
PB internal solution.

Horst

Posted: **Thu Apr 03, 2003 5:11 pm**

Restored from previous forum. Originally posted by horst.

Oops, correct link is:
http://home.mnet-online.de/horst.muc/pb/qlsort.zip

Horst

Posted: **Thu Apr 03, 2003 7:26 pm**

Restored from previous forum. Originally posted by fred.

Thanks for the tips

.

Fred - AlphaSND

PureBasic Forums - English

[Implemented] Sorting Function for Linked Lists

[Implemented] Sorting Function for Linked Lists