Can someone point me to example code on heapsort of doubly-linked
lists using the C (or a C-like, such as Pascal) language?
Thanks in advance.

-- 
Quidquid latine dictum sit altum viditur

José de Paula <jose_de_paula@ig.com.br> writes:

> Can someone point me to example code on heapsort of doubly-linked
> lists using the C (or a C-like, such as Pascal) language?

Are you sure you want to use a heapsort?  Merge sorts are easy to
write for doubly linked lists and they can be very efficient
besides.
-- 
Be suspicious of anyone whose background isn't varied and somewhat odd.
He's probably incompetent.
--trhurler

Em Wed, 31 Mar 2004 18:15:00 -0800, Ben Pfaff escreveu:

> Jos� de Paula <jose_de_paula@ig.com.br> writes:
> 
>> Can someone point me to example code on heapsort of doubly-linked
>> lists using the C (or a C-like, such as Pascal) language?
> 
> Are you sure you want to use a heapsort?  Merge sorts are easy to
> write for doubly linked lists and they can be very efficient
> besides.

Nah, I'm not really sure I want to use heapsort; currently I am studying
(by myself) various sorting algorithms and data structures, I want to have
an overview of the thing. I stumbled on heapsort while browsing Wikipedia
(http://en.wikipedia.org/wiki/Sort_algorithm), where it is said that
heapsort behaves as O(n log n), and I became interested. However, after I
posted this, I read the earlier discussion about quicksort in this group
("Quicksort pathological behavior?") and someone said that heapsort is
more adequate to arrays, whereas mergesort (also O(n log n) according to
Wikipedia) goes well with linked lists.

I will study the subject more deeply and eventually post my results (I'm
writing, for myself only, a "libdoublylinkedlist", sort of, it's very
amateur, but its helping me greatly with this; if you want to see it, feel
free to mail me).

Thank you for the reply.

-- 
Quidquid latine dictum sit altum viditur

José de Paula <jose_de_paula@ig.com.br> writes:

> Nah, I'm not really sure I want to use heapsort; currently I am studying
> (by myself) various sorting algorithms and data structures, I want to have
> an overview of the thing. I stumbled on heapsort while browsing Wikipedia
> (http://en.wikipedia.org/wiki/Sort_algorithm), where it is said that
> heapsort behaves as O(n log n), and I became interested. However, after I
> posted this, I read the earlier discussion about quicksort in this group
> ("Quicksort pathological behavior?") and someone said that heapsort is
> more adequate to arrays, whereas mergesort (also O(n log n) according to
> Wikipedia) goes well with linked lists.

Here's a simple (singly) linked list merge sort that I recently
wrote.  A better implementation would make use of existing runs
in the data.  Comments are welcome.

/* Merges lists A and B into a single list, which is returned.  Cases are
   compared according to comparison function COMPARE, which receives auxiliary
   data AUX. */
static struct case_list *
merge (struct case_list *a, struct case_list *b,
       int (*compare) (const struct ccase *,
                       const struct ccase *, void *aux),
       void *aux) 
{
  struct case_list head;
  struct case_list *tail = &head;

  while (a != NULL && b != NULL)
    if (compare (&a->c, &b->c, aux) < 0) 
      {
        tail->next = a;
        tail = a;
        a = a->next;
      }
    else 
      {
        tail->next = b;
        tail = b;
        b = b->next;
      }

  tail->next = a == NULL ? b : a;

  return head.next;
}

/* Sorts the list beginning at FIRST, returning the new first case.  Cases are
   compared according to comparison function COMPARE, which receives auxiliary
   data AUX. */
static struct case_list *
merge_sort (struct case_list *first,
            int (*compare) (const struct ccase *,
                            const struct ccase *, void *aux),
            void *aux) 
{
  /* FIXME: we should use a "natural" merge sort to take
     advantage of the natural order of the data. */
  struct case_list *middle, *last, *tmp;

  /* A list of zero or one elements is already sorted. */
  if (first == NULL || first->next == NULL)
    return first;

  middle = first;
  last = first->next;
  while (last != NULL && last->next != NULL) 
    {
      middle = middle->next;
      last = last->next->next;
    }
  tmp = middle;
  middle = middle->next;
  tmp->next = NULL;
  return merge (merge_sort (first, compare, aux),
                merge_sort (middle, compare, aux),
                compare, aux);
}


-- 
"Note that nobody reads every post in linux-kernel.   In fact, nobody who
 expects to have time left over to  actually do any real kernel work will
 read even half.  Except Alan Cox, but he's actually not human, but about
 a thousand gnomes working in under-ground caves in Swansea." --Linus

Jos� de Paula wrote:
> 
> Can someone point me to example code on heapsort of doubly-linked
> lists using the C (or a C-like, such as Pascal) language?

Here's some mergesort.

/* BEGIN l_sort.c */
/*  
** l_sort() is a nonstable sorting function for doubley linked lists.
** sl_sort() is a stable sorting function for doubley linked lists.
** ls_sort() is a stable sorting function for singley linked lists.
** list_rev() reverses doubley linked lists.
** slist_rev() reverses singley linked lists.
*/
#include <stdio.h>
#include <stdlib.h>

#define FUNCTION        l_sort
#define NODES           17
/*
** These next 4 macros, are the ones that you would change, 
** to use any of the above sorting functions on a linked list of
** any type node.   
** l_init() and l_print(), as written, will only work with a node
** which has a member named y, of type double.
** The single link sorters will also sort a double linked list,
** but then it will become a singley linked list.
*/
/* BEGIN next 4 macros */
#define N_TYPE          \
struct node {           \
    struct node *next;  \
    struct node *prev;  \
    double y;           \
}
#define GT(A, B)        ((A) -> y >  (B) -> y)
#define NEXT            next
#define PREV            prev
/* END next 4 macros */

#define LU_RAND_SEED    123456789LU
#define LU_RAND(S)      ((S) * 69069 + 362437 & 0xffffffff)
#define str(s)          # s
#define xstr(s)         str(s)

typedef N_TYPE      n_type;

void l_free(n_type *);
n_type *l_make(size_t);
long unsigned l_init(n_type *, long unsigned);
void l_print(n_type *);
n_type *l_sort(n_type *, size_t);
n_type *ls_sort(n_type *, size_t);
n_type *sl_sort(n_type *, size_t);
n_type *list_sort(n_type *);
n_type *slist_rev(n_type *);
n_type *list_rev(n_type *);

int main(void) 
{    
    n_type *list;
    const n_type* (*function)() = FUNCTION;
    
    list = l_make(NODES);
    if (list == NULL) {
        fputs("The list was not allocated.\n", stderr);
        exit(EXIT_FAILURE);
    }    
    puts("Output from l_sort.c\n\nRandom order");
    l_init(list, LU_RAND_SEED);
    l_print(list);    
    puts("Sorted order, " xstr(FUNCTION));
    if (function == ls_sort || function == sl_sort) {
        puts(xstr(FUNCTION) " is stable");
    } else {
        puts(xstr(FUNCTION) " is NOT stable");
    }
    list = list_sort(list);
    l_print(list);    
    puts("Reversed order");
    list = FUNCTION == l_sort ||  FUNCTION == sl_sort
        ? list_rev(list) : slist_rev(list);
    l_print(list);    
    l_free(list);
    return 0;
}

void l_free(n_type *node)
{
    n_type *next;

    while (node != NULL) {
        next = node -> NEXT;
        free(node);
        node = next;
    }
}

n_type *l_make(size_t count)
{
    n_type *node, *list;

    list = count ? malloc(sizeof *list) : NULL;
    if (list != NULL) {
        node = list;
        node -> PREV = NULL;
        while (--count != 0) {
            node -> NEXT = malloc(sizeof *node -> NEXT);
            if (node -> NEXT == NULL) {
                l_free(list);
                return NULL;
            } else {
                node -> NEXT -> PREV = node;
                node = node -> NEXT;
            }
        }
        node -> NEXT = NULL;
    }
    return list;
}

long unsigned l_init(n_type *node, long unsigned seed)
{    
    do {
        seed = LU_RAND(seed);
        node -> y = 3.14159265 * seed;
        node = node -> NEXT;
    } while (node != NULL);
    return seed;
}

void l_print(n_type *node)
{
    do {
        printf("node -> y is %f\n", node -> y);
        node = node -> NEXT;
    } while (node != NULL);
    putchar('\n');
}

n_type *list_rev(n_type *temp)
{    
    n_type *head;
        
    do {
        head = temp;
        temp = head -> NEXT;
        head -> NEXT = head -> PREV;
        head -> PREV = temp;
    } while (temp != NULL);
    return head;
}

n_type *slist_rev(n_type *head)
{    
    n_type *previous, *next;
    
    next = NULL;
    while (head -> NEXT != NULL) {
        previous = head;
        head = previous -> NEXT;
        previous -> NEXT = next;
        next = previous;
    } 
    head -> NEXT = next;    
    return head;
}

n_type *list_sort(n_type *list)
{
    n_type *node;    
    size_t count;
    
    count = 1;
    node = list -> NEXT;  
    while (node != NULL) {
        ++count;
        node = node -> NEXT;
    }
    return FUNCTION(list, count);
}

n_type *l_sort(n_type *list, size_t count)
{
    size_t  half, other_half;
    n_type *head, *tail, *swap;

    if (count > 1) {
        tail = list -> NEXT;
        other_half = half = count / 2;
        while (--other_half != 0) {
            tail = tail -> NEXT;
        }
        tail -> PREV -> NEXT = NULL;
        tail -> PREV = NULL;
        tail = l_sort(tail, count - half);
        head = l_sort(list, half);
        if (GT(head, tail)) {
            swap = head;
            head = tail;
            tail = swap;
        }
        list = head;
        while (head -> NEXT != NULL) {
            head = head -> NEXT;  
            if (GT(head, tail)) {
                head -> PREV -> NEXT = tail;
                tail -> PREV = head -> PREV;
                swap = head;
                head = tail;
                tail = swap;
            }
        }    
        head -> NEXT = tail;
        tail -> PREV = head;
    }
    return list;
}

n_type *sl_sort(n_type *list, size_t count)
{            
    size_t  half, other_half;
    n_type *head, *tail, *sorted;

    if (count > 1) {
        tail = list -> NEXT;
        other_half = half = count / 2;
        while (--other_half != 0) {
            tail = tail -> NEXT;
        }
        tail -> PREV -> NEXT = NULL;
        tail -> PREV = NULL;
        tail = sl_sort(tail, count - half);
        head = sl_sort(list, half);
        if (GT(head, tail)) {
            sorted = list = tail;
            tail = sorted -> NEXT;
        } else {                
            sorted = list = head;
            head = sorted -> NEXT;
        } 
        while (sorted -> NEXT != NULL) { 
            if (GT(head, tail)) {
                tail -> PREV = sorted;
                sorted = sorted -> NEXT = tail;
                tail = sorted -> NEXT;
            } else {
                head -> PREV = sorted;
                sorted = sorted -> NEXT = head;
                head = sorted -> NEXT;
            }
        }
        if (head != NULL) {
            head -> PREV = sorted;
            sorted -> NEXT = head;
        } else {
            tail -> PREV = sorted;
            sorted -> NEXT = tail;
        }
    }
    return list;
}

n_type *ls_sort(n_type *list, size_t count)
{
    size_t half, other_half;
    n_type *head, *tail, *sorted;

    if (count > 1) {
        head = list;
        other_half = half = count / 2;
        while (--other_half != 0) {
            head = head -> NEXT;
        }
        tail = head -> NEXT;
        head -> NEXT = NULL;
        tail = ls_sort(tail, count - half);
        head = ls_sort(list, half);  
        if (GT(head, tail)) {
            sorted = list = tail;
            tail = sorted -> NEXT;
        } else {
            sorted = list = head;
            head = sorted -> NEXT;
        } 
        while (sorted -> NEXT != NULL) {
            if (GT(head, tail)) {
                sorted = sorted -> NEXT = tail;
                tail = sorted -> NEXT;
            } else {
                sorted = sorted -> NEXT = head;
                head = sorted -> NEXT;
            }
        }
        sorted -> NEXT = head ? head : tail;
    }
    return list;
}

/* END l_sort.c */

-- 
pete

Ben Pfaff wrote:
 
> Here's a simple (singly) linked list merge sort that I recently
> wrote.  A better implementation would make use of existing runs
> in the data.  Comments are welcome.

I posted l_sort in this thread. 
l_sort makes use of existing runs, but it isn't stable.

A list in this order {1,1,0,1} would split into {1,1}{0,1}
The node with the zero value,
would be designated as the head of the newly sorted list 
and the node which was originally last, would become second, 
moving ahead of the other two nodes with equal keys.

-- 
pete

Jos� de Paula <jose_de_paula@ig.com.br> wrote in
news:pan.2004.04.01.03.27.12.54186@ig.com.br: 

> Nah, I'm not really sure I want to use heapsort; currently I am
> studying (by myself) various sorting algorithms and data structures, I
> want to have an overview of the thing. I stumbled on heapsort while
> browsing Wikipedia (http://en.wikipedia.org/wiki/Sort_algorithm),
> where it is said that heapsort behaves as O(n log n), and I became
> interested. However, after I posted this, I read the earlier
> discussion about quicksort in this group ("Quicksort pathological
> behavior?") and someone said that heapsort is more adequate to arrays,
> whereas mergesort (also O(n log n) according to Wikipedia) goes well
> with linked lists. 

Well, with a *doubly* linked list, you could use the prev and next pointers 
in the list nodes as the left and right pointers for a binary tree, which 
would let you do heap sort fairly nicely as well.

-josh

     

josh <smileyfaceswillruletheworld@yahoo.com.NOSPAM> writes:

> Well, with a *doubly* linked list, you could use the prev and next pointers 
> in the list nodes as the left and right pointers for a binary tree, which 
> would let you do heap sort fairly nicely as well.

Here's an algorithm that might do the job pretty well:
        http://adtinfo.org/libavl.html/Transforming-a-Vine-into-a-Balanced-BST.html
-- 
Ben Pfaff 
email: blp@cs.stanford.edu
web: http://benpfaff.org

Ben Pfaff <blp@cs.stanford.edu> wrote in
news:87d66p52nu.fsf@blp.benpfaff.org: 

> josh <smileyfaceswillruletheworld@yahoo.com.NOSPAM> writes:
> 
>> Well, with a *doubly* linked list, you could use the prev and next
>> pointers in the list nodes as the left and right pointers for a
>> binary tree, which would let you do heap sort fairly nicely as well.
> 
> Here's an algorithm that might do the job pretty well:
>         http://adtinfo.org/libavl.html/Transforming-a-Vine-into-a-Balan
>         ced-BST.html 

That seems to be for converting a sorted linked list into a BST, but you 
don't have a sorted list to begin with, and you don't want a BST.  (well, 
that might work, but it wouldn't be heap sort)

The algorithm would be basically the same as for an array heap sort 
(sufficiently unoptimized), except you'd use a linked binary tree instead 
of the almost universal array form of a heap.

-josh

     

josh <smileyfaceswillruletheworld@yahoo.com.NOSPAM> writes:

> Ben Pfaff <blp@cs.stanford.edu> wrote in
> news:87d66p52nu.fsf@blp.benpfaff.org: 
>
>> josh <smileyfaceswillruletheworld@yahoo.com.NOSPAM> writes:
>> 
>>> Well, with a *doubly* linked list, you could use the prev and next
>>> pointers in the list nodes as the left and right pointers for a
>>> binary tree, which would let you do heap sort fairly nicely as well.
>> 
>> Here's an algorithm that might do the job pretty well:
>>         http://adtinfo.org/libavl.html/Transforming-a-Vine-into-a-Balan
>>         ced-BST.html 
>
> That seems to be for converting a sorted linked list into a BST, but you 
> don't have a sorted list to begin with, and you don't want a BST.  (well, 
> that might work, but it wouldn't be heap sort)

You weren't suggesting arranging the heap as a binary tree?  You
can easily arrange the doubly linked list into a binary tree
using the algorithm described in the link, then you can apply the
"make heap" and "heap sort" algorithms to the binary tree.  Then
the binary tree is a binary *search* tree which you can convert
back to a doubly linked list.

> The algorithm would be basically the same as for an array heap sort 
> (sufficiently unoptimized), except you'd use a linked binary tree instead 
> of the almost universal array form of a heap.

Right.  That's exactly what I was suggesting.  The result is a
heap sort on a doubly linked list that requires only O(1) extra
storage, not the O(n) that an auxiliary array would require.
-- 
"The sound of peacocks being shredded can't possibly be
 any worse than the sound of peacocks not being shredded."
Tanuki the Raccoon-dog in the Monastery

Ben Pfaff <blp@cs.stanford.edu> wrote in
news:87ptaksei0.fsf@blp.benpfaff.org: 

> josh <smileyfaceswillruletheworld@yahoo.com.NOSPAM> writes:
> 
>> Ben Pfaff <blp@cs.stanford.edu> wrote in
>> news:87d66p52nu.fsf@blp.benpfaff.org: 
>>
>>> josh <smileyfaceswillruletheworld@yahoo.com.NOSPAM> writes:
>>> 
>>>> Well, with a *doubly* linked list, you could use the prev and next
>>>> pointers in the list nodes as the left and right pointers for a
>>>> binary tree, which would let you do heap sort fairly nicely as
>>>> well. 
>>> 
>>> Here's an algorithm that might do the job pretty well:
>>>         http://adtinfo.org/libavl.html/Transforming-a-Vine-into-a-Bal
>>>         an ced-BST.html 
>>
>> That seems to be for converting a sorted linked list into a BST, but
>> you don't have a sorted list to begin with, and you don't want a BST.
>>  (well, that might work, but it wouldn't be heap sort)
> 
> You weren't suggesting arranging the heap as a binary tree?

not a binary *search* tree.

> You can easily arrange the doubly linked list into a binary tree
> using the algorithm described in the link, then you can apply the
> "make heap" and "heap sort" algorithms to the binary tree.  Then
> the binary tree is a binary *search* tree which you can convert
> back to a doubly linked list.

But why bother using a tree outside of the heap at all?  You're inserting 
elements into the heap one at a time and removing them one at a time, in 
(possible reverse) order.  A list is already a natural place to get/put 
elements one at a time.

-josh