Re: fast stable sort

On Sat, 15 Nov 2008 18:42:01 -0500, CBFalconer
<cbfalconer@xxxxxxxxx> wrote:

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.


char *ptrs[N];

for (i=0;i<N;i++) ptrs[i] = fgetstring(fptr);
mergesort_in_place(ptrs,compare_strings);

I'm not confused; you simply haven't bothered to understand the
text on which you are commenting.


Richard Harter, cri@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
.

Relevant Pages

  • 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
    ... an example program on the use of hashlib. ... How do you load a herd of strings into your ... pointers, not the strings. ...
    (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 ... diddles the pointers, not the strings. ...
    (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 ... diddles the pointers, not the strings. ...
    (comp.programming)
  • Re: fast stable sort
    ... an example program on the use of hashlib. ... How do you load a herd of strings into your ... pointers, not the strings. ...
    (comp.programming)