Sorting a linked list?

[BackupUser]

Restored from previous forum. Originally posted by Fangbeast.

Does anyone know of a way to sort a linked list? Since Linked lists do have indexes, I imagine that this could be done with pointers somehow but I have no idea of the logic.

Once the linked list is sorted, I can echo it back to the visible ListIconGadget for the user.


Fangles

[BackupUser]

Restored from previous forum. Originally posted by tinman.

Does anyone know of a way to sort a linked list? Since Linked lists do have indexes, I imagine that this could be done with pointers somehow but I have no idea of the logic.

The simplest method to understand is the bubble sort. You basically go through each item in the list and compare it to the next item. If they are out of order, you swap them around (either their contents or their position in the list, depending on which you can most easily/quickly). You repeat this until there are no more items to be sorted. Note that the bubble sort is fairly slow, especially when you have a lot of items.

Some pseudo-code

Code: Select all

start=
end=
Repeat
  found=0 ; flag to show when a swap has taken place
  item=start
  While itemend
    If contents of item 
  Wend
  end= ; See below
Until found=0 Or start=end

By moving the end item back through the list, you can make the sort time shorter (the end item will always be correctly sorted after the end of the While loop). However, you might need to check that this works first (i.e. in case you move the end item past the start of the start item) or add some extra checks (it's a lot easier to do this with an array).

Obviously, changing the < symbol in the If statement changes the order in which the list is sorted.


--
It's not minimalist - I'm increasing efficiency by reducing input effort.
(Win98first ed. + SP1, PB3.10)

[BackupUser]

Restored from previous forum. Originally posted by horst.

I have written several DOS programs with linked list sort.

The idea is merging 2 lists that have already been sorted,
which is very simple. Each list, of course, is produced the
same way. When you follow this idea back to the beginning,
you'll have to start with pairs of records.

However, this requires full control over the linked list
structure, so you must know the internal construct.

Horst.

[BackupUser]

Restored from previous forum. Originally posted by Andre.

An included sort command for linked lists would be welcome ! (I mentioned this earlier...)

Something where you could specify:
1. Sort direction
2. Field name which should be used for sorting (Example: Name, Birthdate, Adress, ...)


Regards
André

*** German PureBasic Support ***

[BackupUser]

Restored from previous forum. Originally posted by horst.

An included sort command for linked lists ...
Something where you could specify:
1. Sort direction
2. Field name which should be used for sorting (Example: Name, Birthdate, Adress, ...)

This could be done by a callback procedure that the user defines:
You get two records, and you decide which one is first.
So the actual sort function would have nothing to do with this.

Horst.

[BackupUser]

Restored from previous forum. Originally posted by Fangbeast.

Thanks for the answer but it doesn't help. As you may be aware, linked lists are not directly addressable (*unlike arrays)so i would have to do an incredible amount of looping up and down through every element to use this.

Unless there is a way of directly referencing a linked list element via the API that someone might know about.

Fangles

[BackupUser]

Restored from previous forum. Originally posted by Fangbeast.

An included sort command for linked lists would be welcome ! (I mentioned this earlier...)

Something where you could specify:
1. Sort direction
2. Field name which should be used for sorting (Example: Name, Birthdate, Adress, ...)


Regards
André

*** German PureBasic Support ***

That's right, a sort command would be great. I always link a linked-list to a listicongadget for user display and if I could directly reference a linked list element to sort, I could then instantly echo the changes to the ListIconGadget where the list items ARE directly addressable and save so much time. Especially if there are thousands of objects.

Fangles