From: ressler@cs.cornell.edu (Gene Ressler)
Subject: Re: Multiple types of things in linked lists
Summary: quicksorting singly linked list in place
Keywords: sorting, lists
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Distribution: na
Date: Fri, 10 Apr 1992 01:59:41 GMT

In article <1992Apr9.031137.29927@bronze.ucs.indiana.edu> burleigh@bronze.ucs.indiana.edu (Frank Burleigh) writes:
> need ideas but must sketch out what I'm up to before I can ask...
>
>1. make sorting more difficult (how to sort linked lists);
				 ^^^^^^^^^^^^^^^^^^^^^^^^

Ah, this is a favorite of mine.  Here's a quicksort that is 
very fast on randomly ordered data, but O(n^2) on things
already sorted because it always partitions about the first
element.  Anyone see a way to randomize the partition
without traversing the list any more than is already done
(once per partition)?

Note this is `balanced' so stack space is always O(lg n).

Also, sorting long randomly ordered lists is dangerous because
the resulting list, when traversed, generates random memory
accesses, thrashing the cache and/or pages!

#include <stdio.h>

typedef struct node { struct node *next; } *NODE, NODE_REC;

static int (*Cmp)();

/* Quicksort list h, append t at the end, and
   deposit the result in *r.  (The append
   is done by induction.) */
static void q(NODE h, NODE t, NODE *r)
{
  NODE p, lo, hi, next;
  int nlo, nhi;

  while (h != NULL) {

    /* inductive case */
    nlo = nhi = 0; lo = hi = NULL;

    /* partition */
    for (p = h->next; p != NULL; p = next) {
      next = p->next;

      if ((*Cmp)(p, h) < 0) { 
	p->next = lo; lo = p; ++nlo;
      } 
      else {
        p->next = hi; hi = p; ++nhi;
      }
    }

    /* recur */
    if (nlo < nhi) {
      q(lo, h, r);
      r = &h->next; h = hi;	/* eliminated tail-recursive call */
    }
    else {
      q(hi, t, &h->next);
      t = h; h = lo;		/* eliminated tail recursive call */
    }
  }
  *r = t;			/* base case */
}

/* Sort any singly linked list where the `next' pointer is the first field 
   wrt predicate `cmp'.  Uses O(lg n) stack and no other temp space. */
void lqsort(void *lstp, int (*cmp)())
{
  NODE rtn;

  Cmp = cmp;
  q(*(void**)lstp, NULL, lstp);
}


/* Quick and dirty sort utility. */

typedef struct line {
  struct line *next;
  char text[1];
} *LINE, LINE_REC;

int cmp_lines(LINE l1, LINE l2)
{
  return strcmp(l1->text, l2->text);
}

void main(void)
{
  char buf[1000];
  LINE lst, p;
  void *malloc();

  lst = NULL;
  while (gets(buf) != NULL) {
    p = malloc(sizeof(LINE_REC) + strlen(buf));
    strcpy(p->text, buf);
    p->next = lst; lst = p;
  }
  lqsort(&lst, cmp_lines);
  for (p = lst; p != NULL; p = p->next)
    puts(p->text);
}

Finally, the technique used here to make the sort
independent of the record type can be used to solve
the more general problem Frank asked.  (I.e. the
records in the sort utility list have different
sizes in general).

This is essentially how C++ does inheritance --- if 
you define a list superclass e.g. as Stroustrup has 
it in _The C++ Programming Language_, then C++ puts
the list pointer(s) at the top of the compiled C structures
for all derived classes, so the list methods find them
with no effort at all, just as this sort does.
This is clue as to why multiple inheritance is not
part of C++ !

In fact, the best answer to Frank is for him to
`think OO' and use C++ or something better.

Gene
Newsgroups: comp.programming