On (27 Nov 94) Edwin Groothuis wrote to Ken Kavanagh...

11-25-94 02:30, Ken Kavanagh wrote to Someone:
 KK> can someone suggest a place to look for a sort function to be
 KK> used to sort a already created linked list?

A merge sort is usually favourite:

/* list merge/sort. Public domain, Mark Stephen 11/94 */
#include 
#include 

typedef struct node {
            int data;
            struct node *next;
        } Node;

void writelist(Node *r)
{
    while (r) { printf("%8d", r->data); r = r->next; }
    putchar('\n');
}

Node *randomlist(int n) // create random list with n elements
{
    int i;
    Node *t, *r;
    r = t = (Node *)malloc(sizeof(Node));
    for (i = 0; i < n; i++) {
        t = (t->next = (Node *)malloc(sizeof(Node)));
        t->data = rand();
    }
    t->next = NULL;
    return r->next;
}

Node *merge(Node *a, Node *b)   // merge two sorted lists
{
    Node *c, *r;
    r = c = (Node *)malloc(sizeof(Node));
    do {
    // '<=' should be replaced with a comparison function which is
    // supplied as a parameter
        if (a->data data) {
            c->next = a;  c = a; a = a->next;
        }
        else {
            c->next = b;  c = b; b = b->next;
        }
    } while (a && b);
    c->next = a ? a : b;
    return r->next;
}

// recursive merge sort routine
Node *msort(Node *c, int n)
{
    Node *a, *b;
    int i;
    // quit when only one element to sort
    if (c->next == NULL)
        return c;
    else {
        a = c;
        // find the middle of the list
        for (i = 2; i next;
        // split the list into two parts
        b = c->next;  c->next = NULL;
        // repeat recursively until lists have only one element,
        // merge the lists, and then unwind the recursion merging
        // progressively longer lists
        return merge(msort(a, n/2), msort(b, n-n/2));
    }
}

// this stub was originally intended to show the advantage of adding a short
// unordered list to a long sorted list by sorting the short one and then
// merging the two together.
main()
{
    int m, n;
    Node *M, *N;
    M = randomlist(m = 10);
    N = randomlist(n = 160);
    writelist(M = msort(M, m));
    getchar();
    writelist(N = msort(N, n));
    getchar();
    writelist(merge(M,N));
    return 0;
}


... Time flies like an arrow, fruit flies like a banana.

--- PPoint 1.82