Author Message

Hello,
does anybody have an algorithm to sort a doubly linked list
without having to allocate a temporary array ?

Thanks.
--
___   ___  ___  ___  ___  ___  ___
/    /__   /__/ /__/ /__  /__/ /__
/__  /__   / \  /__/ /___ / \  /___
To understand recursion you
Pierre Girard, Groupe d'Etude et de    need to understand recursion.
Recherche en Analyse des Decisions     --Andrew Koenig, 2nd Usenix C++ conf.

(514-340-6047) (514-340-6038)

Sat, 05 Aug 1995 05:40:37 GMT

Quote:
>Hello,
>    does anybody have an algorithm to sort a doubly linked list
>without having to allocate a temporary array ?
>Thanks.

The short answer is "yes" ..... (but I suspect that you were hoping
for something more detailed than that ....)

Without knowing a little more about the problem it is hard to give
a much more helpful answer, though .... The kind of things that one
would typically want to consider when choosing a sort algorithm are:

a) how many items have to be sorted?
b) what kind of key is the data being sorted on?
c) is the data in truly random order or does it typically have some order?
d) how fast do you want it to go?
e) how much time do you want to spend debugging your sort algorithm?

Not knowing the answer to any of these questions I would tend to suggest
using an insertion sort - it has OK performance for sorting moderate
amounts of data, is pretty quick and easy to implement correctly and
has the property of being a stable sort (ie items with duplicate keys
remain in the same order) which can sometimes be useful.

Now, what you really wanted .....

#include        <stdlib.h>

struct list
{
struct list *next;
struct list *prev;
char        *name;

Quote:
};

/*
* InsertionSort()      - simple insertion sort
*/
struct list *
InsertionSort(
struct list *l
)
{
struct list *p;
struct list first;

/*
* set up sentinel element at start of list
*/
first.prev  = NULL;
first.next  = l;
first.name  = "";
l->prev  = &first;

/*
* sort
*/
for (l = l->next; l != NULL; l = l->next)
{
p = l->prev;
while (strcmp(l->name, p->name) < 0)
p = p->prev;

if (p != l->prev)
{
/*
* remove l from current place in list
*/
if (l->next)
l->next->prev     = l->prev;
l->prev->next = l->next;

/*
* insert l into list following p
*/
l->next          = p->next;
l->next->prev = l;
p->next          = l;
l->prev          = p;
}
}

/*
* return pointer to list element following the sentinel
*/
l           = first.next;
l->prev  = NULL;

return      l;

Quote:
}

Sun, 06 Aug 1995 03:33:50 GMT

Quote:
>    does anybody have an algorithm to sort a doubly linked list
>without having to allocate a temporary array ?

M> The short answer is "yes" ..... (but I suspect that you were hoping
M> for something more detailed than that ....)

I should have been more specific when I asked the question.  I was
actually thinking about quicksort or mergesort algorithms for lists
instead of arrays.  The temporary array I was refering to was an array
in which I would have placed the pointers from my list and I would
have applied qsort on it.

M> Without knowing a little more about the problem it is hard to give
M> a much more helpful answer, though .... The kind of things that one
M> would typically want to consider when choosing a sort algorithm
M> are:
M> a) how many items have to be sorted?  b) what kind of key is the
M> data being sorted on?  c) is the data in truly random order or does
M> it typically have some order?  d) how fast do you want it to go?
M> e) how much time do you want to spend debugging your sort
M> algorithm?

a) 5 lists with an unknown proportion of  ~100000 elements.
b) short term : integers, long term : anything you can imagine.
c) I think it will be mostly in order but it is difficult to tell.
d) as fast as it can because I will have to re-sort it many times.
e) the least possible (of course).  I think a couple of days should be
quite enough.

I also wanted to implement a sorting routine usable for any structure
possible without assumption of where might be the forward and backward
pointers.  That would allow me to have one element in two different
lists and sort each list independently but that is a different problem.

M> Not knowing the answer to any of these questions I would tend to
M> suggest using an insertion sort - it has OK performance for sorting
M> moderate amounts of data, is pretty quick and easy to implement
M> correctly and has the property of being a stable sort (ie items
M> with duplicate keys remain in the same order) which can sometimes
M> be useful.

I dont't think the amount of data I have is moderate and I do not need
the stability.

I am currently transforming the mergesort algorithm from Knuth sorting
and searching so I can use instructions like push, pop, pull and merge
instead of array indexes and an array.  I am also looking at how to
rewrite the thing without gotos all over the place.  Someone sent me
some Pascal code for a merge sort so I am looking at that too.  If I
do not manage to get my code to work, I will probably implement an insertion
sort and continue debugging the mergesort later.

Bye.
--
___   ___  ___  ___  ___  ___  ___
/    /__   /__/ /__/ /__  /__/ /__
/__  /__   / \  /__/ /___ / \  /___
To understand recursion you
Pierre Girard, Groupe d'Etude et de    need to understand recursion.
Recherche en Analyse des Decisions     --Andrew Koenig, 2nd Usenix C++ conf.

(514-340-6047) (514-340-6038)

Sun, 06 Aug 1995 21:54:56 GMT

Quote:
> does anybody have an algorithm to sort a doubly linked list without
> having to allocate a temporary array ?

You forgot the ritual incantation "in C" that justifies dropping an
algorithms question in a language-specific group. :-)

I can do it easily enough if you permit me a stack (eg, singly linked
list) of depth O(lg n).  I treat the input list as a singly-linked list
and make one O(n) pass to patch up the backlinks when done.  The
algorithm, treating input and output lists as singly linked, is

state:
stack: push-down stack holding lists of input objects
initialize:
stack = empty
begin:
while (input list is not exhausted)
get next item from input list
create a one-element list holding just this item
push this one-element list on the stack
while ( the stack contains at least two lists
and the top two are the same length )
merge the top two using the algorithm below,
pushing the merged list back on the stack
while (the stack contains at least two lists)
merge the top two, pushing the result back on the stack
if (there is a list on the stack)
pop it; this is the result
else
result is an empty list

Merging two lists is done as follows.  For the sake of simplicity, I
assume the result is to be in increasing order; switch "smaller" for
"greater" if not.

begin:
while (neither input list is exhausted)
compare the first items from each; remove the smaller
from its input list and append it to the output list.
while (input list 1 is not exhausted)
remove its first element and append it to the output.
while (input list 2 is not exhausted)
remove its first element and append it to the output.

Now, was that so hard?

der Mouse

Mon, 07 Aug 1995 03:27:54 GMT

Thanks to all the people who offered suggestions and
references.  I now have an insertion sort function and a mergesort
function for double link lists.  I am currently running many tests on
those functions to verify that they function properly.

Bye.
--
___   ___  ___  ___  ___  ___  ___
/    /__   /__/ /__/ /__  /__/ /__
/__  /__   / \  /__/ /___ / \  /___
To understand recursion you
Pierre Girard, Groupe d'Etude et de    need to understand recursion.
Recherche en Analyse des Decisions     --Andrew Koenig, 2nd Usenix C++ conf.

(514-340-6047) (514-340-6038)

Tue, 08 Aug 1995 00:57:59 GMT

Quote:
>I should have been more specific when I asked the question.  I was
>actually thinking about quicksort or mergesort algorithms for lists
>I also wanted to implement a sorting routine usable for any structure
>possible without assumption of where might be the forward and backward
>pointers.  That would allow me to have one element in two different
>lists and sort each list independently but that is a different problem.

I think this will fit:

----cut here----msort.h----
#ifndef IUW_MSORT_H
#define IUW_MSORT_H

#undef ARGS
#ifdef __STDC__
#  include <stddef.h>
#  define ARGS(x)   x
#else
#  define ARGS(x)   ()
#  define void      char
#endif

#ifndef NULL
#  define NULL      ((void *)0)
#endif

#ifndef offsetof
#  define offsetof(str_t, item)     ((long)&((str_t *)0)->item)
#endif /* offsetof */

/* Prototypes */
extern void *msort ARGS(( void *list, int offset, int (*cmp)(void *, void *) ));
extern void *msort2 ARGS(( void *list, int next_off, int prev_off, int (*cmp)(void *, void *) ));

#endif /* IUW_MSORT_H */

----cut here----msort.c----

/* generic sort-routine for linked lists (=^= qsort for arrays)
*

* Permission to use, copy, modify, and distribute this software for any
* purpose and without fee is hereby granted, provided that the above
* copyright notice appears in all copies and that both that copyright
* notice and this permission notice appear in supporting documentation.
* This software is provided "as is" without expressed or implied warranty.
*
* Usage (example):
*
*     #include "msort.h"
*     typedef struct mylist { ...
*                             struct mylist *next;
*                             ...
*                           } MYLIST;
*     MYLIST *list;
*
*     list = msort(list, offsetof(MYLIST, next), cmp);
* or  list = msort(list, offsetof(struct mylist, next), cmp);
*
*
* cmp(struct mylist *a, struct mylist *b) is similar to the compare-functions
* used in qsort() and bsearch(). It compares two list-structs and returns
*      0  if both are equal,
*     <0  if a->something < b->something
*     >0  otherwise.
*
*
*
*      #include "msort.h"
*      struct foolist { ...
*                       struct foolist *next, *prev;
*                       ...
*                     };
*
*      #define FOO_NEXT_OFFSET     offsetof(struct foolist, next);
*      #define FOO_PREV_OFFSET     offsetof(struct foolist, prev);
*
*      struct foolist *thislist;
*
*      thislist = msort2(thislist, FOO_NEXT_OFFSET, FOO_PREV_OFFSET, cmp);
*
* This sorts the list along the next-pointers and then re-adjusts the
* prev-pointers.  msort2() calls msort() to do the sorting, thus the prev-
* pointers are not needed for the sorting.  In fact, you can build an un-
* the prev-pointers, then call msort2() to get a sorted list with valid
* link pointers for both directions.
*/

#include "msort.h"
#define PRIVATE static
#define PUBLIC

/* internal prototypes */
PRIVATE void *ms_split ARGS((void *, int, int (*)(void *, void *)));
PRIVATE void *ms_merge ARGS((void *, void *, int ,int (*)(void *, void *)));

#define NEXT(p, x)       (*(void **)((char *)(p)+(x)))

PUBLIC void *msort(list, offset, cmp)
void *list;
int offset;
int (*cmp) ARGS((void *, void *));
{
void *ptr;

ptr  = ms_split(list, offset, cmp);
list = ms_merge(list, ptr, offset, cmp);

return(list);

Quote:
}

PUBLIC void *msort2(list, next_off, prev_off, cmp)
void *list;
int next_off, prev_off;
int (*cmp) ARGS((void *, void *));
{
if( list ) {
void *pp, *p;

pp = list = msort(list, next_off, cmp);

NEXT(pp, prev_off) = NULL;
while( (p = NEXT(pp, next_off)) != NULL ) {
NEXT(p, prev_off) = pp;
pp = p;
}
}
return( list );

Quote:
}

PRIVATE void *ms_split(list, offset, cmp)
void *list;
int offset;
int (*cmp) ARGS((void *, void *));
{
void *next, *newlist = NULL;

while( (next = NEXT(list, offset)) != NULL ) {
if( cmp(list, next) > 0 ) {
NEXT(list, offset) = NEXT(next, offset);
NEXT(next, offset) = newlist;
newlist = next;
} else {
list = next;
}
}

if( newlist != NULL ) {     /* msort() on newlist */
next    = ms_split(newlist, offset, cmp);
newlist = ms_merge(newlist, next, offset, cmp);
}

return(newlist);

Quote:
}

PRIVATE void *ms_merge(a, b, offset, cmp)
void *a, *b;
int offset;
int (*cmp) ARGS((void *, void *));
{
void *newlist = NULL;
void **p = &newlist;

while( a != NULL && b != NULL ) {
if( cmp(a, b) < 0 ) {
*p = a;
a  = NEXT(a, offset);
} else {
*p = b;
b  = NEXT(b, offset);
}
p = &NEXT(*p, offset);
}

if( a == NULL )
*p = b;
else
*p = a;

return(newlist);

Quote:
}

----cut here----

Regards,
Ingo
--
Ingo Wilken, CS Student, Univ.of Oldenburg, FRG | You mean I really did all of

Tue, 08 Aug 1995 06:54:20 GMT

 Page 1 of 1 [ 6 post ]

Relevant Pages