Using a link list over an array.

[Ben Bacarisse]

A node*, which gives the compare function access to the next field,
and also means the compare function needs to know the definition of
a node. It doesn't need any of this, it just needs a pointer to
the const data. Mergesort doesn't need to know the form of the
data, and thus uses const void* pointers. That way errors in
writing the compare won't foul things up.

Think about it. The compare function should compare two
thingummies. It doesn't need to be a special function for the
sort. It doesn't need to know about nodes. It certainly doesn't
care where the next node is. For all you know the data may be
encoded names, needing decoding, translation, etc.

It is never quite that simple. Your interface restricts mergesort to
those lists that use indirect data. It is possible to remove this
restriction -- the simplest way is (in part) to pass node pointers to
the compare function. Passing a void * (stored in the node) is not
100% general.

 

[CBFalconer]

It is never quite that simple. Your interface restricts mergesort to
those lists that use indirect data. It is possible to remove this
restriction -- the simplest way is (in part) to pass node pointers to
the compare function. Passing a void * (stored in the node) is not
100% general.

It's not really worth arguing over. To me, the fact that the
construction of a node allows any list and data to be expressed,
and that the system doesn't pass about unneeded data or access, is
more than sufficient. I can concede that others have different
objectives.

 

[pereges]

btw since i saw it pete's code, isn't the static return type of a
function supposed to make it private ? What is the advantage of using
it ? Will it restrict the amount of code that is included in other
files ?

 

[pereges]

btw since i saw it pete's code, isn't the static return type of a
function supposed to make it private ? What is the advantage of using
it ? Will it restrict the amount of code that is included in other
files ?

 

[pereges]

btw since i saw it pete's code, isn't the static declaration of a
function supposed to make it private ? What is the advantage of using
it ? Will it restrict the amount of code that is included in other
files ?

 

[CBFalconer]

btw since i saw it pete's code, isn't the static return type of a
function supposed to make it private ? What is the advantage of
using it ? Will it restrict the amount of code that is included
in other files ?

That 'static' applies to the function, not the returned type. It
hides the function from any other source file, although it can be
passed out as a function pointer.

 

[Richard Tobin]

btw since i saw it pete's code, isn't the static return type of a
function supposed to make it private ? What is the advantage of
using it ? Will it restrict the amount of code that is included
in other files ?

[/QUOTE]

That 'static' applies to the function, not the returned type.

More precisely, it refers to the *name* of the function. That's
why:

... it can be passed out as a function pointer.

-- Richard

 

[Herbert Rosenau]

Is it easier to sort link lists as opposed to arrays ?? In one
implementation of quick sort applied on link lists, I saw that even
accessing a single Nth node required n-1 passes.

When you have to sort an array you have to move complete array members
around. This is time intensive at all.

Sorting lists - whenever this can not done easy while sort while
inserting - is nothing than moving pointers to elements around. Lots
of less work.

Exchanging 2 array members needs
- copy one array member out of its place
- copy the other member on its new place
- copy the other member on the place the other was

Exchanging 2 list elements is is easy done by moving pointers to them
around. Not a single list member has to be moved at all.

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2R Deutsch ist da!

 

[Barry Schwarz]

When you have to sort an array you have to move complete array members
around. This is time intensive at all.

Sorting lists - whenever this can not done easy while sort while
inserting - is nothing than moving pointers to elements around. Lots
of less work.

Exchanging 2 array members needs
- copy one array member out of its place
- copy the other member on its new place
- copy the other member on the place the other was

Exchanging 2 list elements is is easy done by moving pointers to them
around. Not a single list member has to be moved at all.

Let node a point to node b point to node c point to node d. Let's
swap b and c. Let's make it easy and assume we know it is a that
points to b (otherwise we have to spend time finding it).
Copy a.next to a temp.
Copy b.next to a.next
Copy c.next to b.next
Copy the temp to c.next

Unless the array elements are aggregates, arrays look faster.



Remove del for email