Re: fast stable sort

On Sun, 16 Nov 2008 17:36:25 -0500, CBFalconer
<cbfalconer@xxxxxxxxx> wrote:

Richard Harter wrote:
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.

CBF responded with the following which is a peculiar mixture of
irrelevance and outright error. I will comment one last time.

No, you have created something less efficient and more restricted
than the linked list.

It may or not may not be less efficient; you will, I hope,
forgive me if I don't take your unsupported word on the matter.

"More restricted" is a peculiar observation. In many respects a
linked list is a more restrictive data representation than an
array because it only provides sequential access (try doing a
binary search on a list). Whether a list or an array is the
better choice depends on external circumstances

You have formed the array of pointers.

Excellent, you got this right.

(That can easily be sorted with mergesort, you just have to change
some things around)

This is problematic. By "mergesort" you may mean a list based
mergesort in which case your comment is irrelevant. If you
actually are talking about an array based mergesort then there is
nothing to change; given the requirement of an in-place merge
either the mergesort routine at hand can do it or it can't.

Obviously your fgetstring routine mallocs
space for a string, and reads the string from FILE *fptr.

Good read.

You need
to specify the value of N ahead of operation, and exceeding that
count of strings will cause an error.

Now this is the silliest of quibbles. This was sample code, not
a full blown implementation. In a real implementation one
provides for an expanding buffer using malloc and counts the
number of strings. I didn't bother with putting together the
usual boiler plate.

You also have to initialize
the array ptrs[i], which you omitted.

I would have supposed that you could read three lines of code
correctly; I see that I was wrong. In line 2 of three the value
of ptrs[i] is initialized to a pointer to a string.

Oddly enough, there is a real error for you to find; I didn't
pass the size of the array into mergesort_inplace.

The system shown in the code I referenced uses no more memory,
probably less, works, and is efficient.

Actually the code your referenced uses more memory; the links in
your linked list require O(n) space. You seem to be under the
happy illusion that link pointers do not use memory.

I dare say it works and is reasonably efficient. A linked list
mergesort is a fairly simple thing to write.

It doesn't care about the
value of N, provided the malloc system keeps working.

That's nice.

That, I think, is enough of responding to CBF for the moment.

There is, however, a question of terminology to settle, to wit,
what does one mean by an "in place" sort or merge. Surely it
must mean that the sort or merge algorithm requires O(1)
auxilliary space. Sorting a linked list is naturally in place,
barring perverse implementations; whether sorting an array is in
place depends on the algorithm. When one is talking about in
place sorting/merging linked lists are irrelevent because they
are not, so to speak, part of the picture.



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
    ... 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: 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: Dominance Tree Sorts
    ... Performance problems with heapsort are often blamed on cache effects. ... This kind of information loss does not occur either quicksort or mergesort. ... Using a simplified analysis of the mergesort cost function we get ... catch is that the references in the linked lists are scattered. ...
    (comp.programming)
  • Re: Dominance Tree Sorts
    ... Performance problems with heapsort are often blamed on cache effects. ... This kind of information loss does not occur either quicksort or mergesort. ... Using a simplified analysis of the mergesort cost function we get ... catch is that the references in the linked lists are scattered. ...
    (comp.theory)