Re: fast stable sort

Ben Bacarisse wrote:
CBFalconer <cbfalconer@xxxxxxxxx> writes:
Ben Bacarisse wrote:
CBFalconer <cbfalconer@xxxxxxxxx> writes:
Richard Harter wrote:
CBFalconer <cbfalconer@xxxxxxxxx> wrote:
Richard Harter wrote:
CBFalconer <cbfalconer@xxxxxxxxx> wrote:
pete wrote:
Richard Harter wrote:

There are in place stable versions of mergesort.

Can you post C code for a stable in place mergesort function?

Such exists in wdfreq.c, an example program on the use of
hashlib. wdfreq has been put in public domain, hashlib is
released under GPC. See:

<http://cbfalconer.home.att.net/download/hashlib.zip>

The context is in-place with O(1) extra storage; use of an
auxilliary linked list is not on the table.

How do you load a herd of (variable length) strings into your
system without at least an auxiliary table of pointers to the
individual strings? Once you recognize this, the obvious way
to load the strings is with a singly linked list. The total
memory usage will normally be less. Note that the sort only
diddles the pointers, not the strings.

In this case the requirement is to sort the pointers in place
without using an auxilliary linked list. IOW, load the pointers
in an array. That is the requirement; you can't use a linked
list.

I think you are confused. Post some code that organizes this,
omitting the actual sort code (just a call to a mergesort
function will do), starting from a file full of strings.

I think the confusion is yours. I don't see how the code around
the sort call has any effect on the specified requirement but, if
it helps, image the organising code is:

That's C++ code. The original asked for C code,

Yes, but you didn't. You responded to the OP with a reference to your
C code that does not meet the required specification. Later, you
asked for "code that organizes this". I hoped that supplying some
would clarify the context for you, but it seems that it would not. (I
also note from another reply it would not have mattered if I'd replied
with C code.)

which is what hashlib and its demonstrations are written in.

The point is that the strings have to be defined, read, and loaded
into memory before they can be sorted. A linked list is an
efficient and quick means of so doing. That can be sorted with
mergesort, and output with simple code.

...as if that was ever in doubt.

You can't claim to have an in-place merge sort simply because you have
already wasted lots of space by using a space inefficient method of
input. This is the second time I have made this point but you clipped
it without comment last time. If you have no comment about this
central issue, at least leave it un-clipped this time.

It is NOT inefficient. It simply lumps the pointer in with the
string, rather than isolating it in a separate array. The result
takes the same space, and automatically handles any size of input,
up to the failure point of malloc. See my response to Richard
Harter about 2 hours ago.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
.

Relevant Pages

  • Re: fast stable sort
    ... Can you post C code for a stable in place mergesort function? ... wdfreq has been put in public domain, hashlib is ... How do you load a herd of strings into your ... In this case the requirement is to sort the pointers in place ...
    (comp.programming)
  • Re: sorting algorithms
    ... Mergesort must be yours. ... Primarily it was to rebut your statement "No sort does both on all ... The distributed space for the list pointers will be ... but only if you're sorting linked lists. ...
    (comp.programming)
  • Re: fast stable sort
    ... Can you post C code for a stable in place mergesort function? ... How do you load a herd of strings into your ... diddles the pointers, not the strings. ... In this case the requirement is to sort the pointers in place ...
    (comp.programming)
  • Re: fast stable sort
    ... Can you post C code for a stable in place mergesort function? ... wdfreq has been put in public domain, hashlib is ... How do you load a herd of strings into your ... In this case the requirement is to sort the pointers in place ...
    (comp.programming)
  • OK, Im stumped, couldnt free string pointer list...
    ... some fairly big lists of strings. ... I wanted to sort a buffer full of these null-terminated strings ... the list of string pointers! ...
    (comp.lang.c)