sorting a double link list 
Author Message
 sorting a double link list

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.  
(G.E.R.A.D.), Montreal, Quebec, Canada.  

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



Sat, 05 Aug 1995 05:40:37 GMT  
 sorting a double link list


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  
 sorting a double link list


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.

Thanks for your help.

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.  
(G.E.R.A.D.), Montreal, Quebec, Canada.  

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



Sun, 06 Aug 1995 21:54:56 GMT  
 sorting a double link list

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  
 sorting a double link list

        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.  
(G.E.R.A.D.), Montreal, Quebec, Canada.  

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



Tue, 08 Aug 1995 00:57:59 GMT  
 sorting a double link list


Quote:
>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.
>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.
 *
 *
 * For double-linked lists, msort2() sorts along one link-pointer and then
 * re-adjusts the second link-pointers:
 *
 *      #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-
 * sorted double-linked list like a single-linked list without careing about
 * 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  
 
 [ 6 post ] 

 Relevant Pages 

1. Sorting a double linked list

2. Sorting Double Linked List in place

3. link list of a linked list (chained links?)

4. Link-list sort algorithm question

5. basic sort for singly linked list...

6. deleting and sorting items in a linked list

7. sorting of a linked list

8. Linked List Sort/Search/delete code ??Help????

9. Linked list sorting...

10. quick-sorting a linked list?

11. Please Help: Sorting a linked list

12. Sorting on a doubly linked list

 

 
Powered by phpBB® Forum Software