Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!usc!ucsd!ucbvax!pasteur!cordelia!c164-bd
From: c164-bd@cordelia.uucp (John D. Mitchell)
Newsgroups: comp.lang.c
Subject: Re: Sorting Double Linked List in place
Message-ID: <8872@pasteur.Berkeley.EDU>
Date: 14 Nov 90 01:30:13 GMT
References: <1990Nov7.160701.5838@bkj386.uucp> <1930@necisa.ho.necisa.oz>
Sender: news@pasteur.Berkeley.EDU
Reply-To: c164-bd@cordelia.UUCP (John D. Mitchell)
Followup-To: comp.lang.c
Organization: University of California, Berkeley
Lines: 63

In article <1930@necisa.ho.necisa.oz> boyd@necisa.ho.necisa.oz (Boyd Roberts) writes:
>In article <1990Nov7.160701.5838@bkj386.uucp> anton@analsyn.UUCP (PUT YOUR NAME HERE) writes:
>>I'm looking for a routine to sort a double linked list in place, 
>>given the head of the list and a compare function for the elements 
>>(sort of like qsort).
>
>What about a bubble sort?
>
Call this whatever you want:

Assumptions:
	Linked list

typedef struct LList_
  {
  struct LList_ *prev;
  struct LList_ *next;
  void *data;			/* Whatever...	*/
  }  LList;

LList LLSort (LList *head)
  {
  LList *lessList,		/* List containing all those < pivot.	*/
	*morequalList;		/*  "     "         "   "   >=   "  .	*/
  LList *tmpList;

  /* Stopping case checks....	*/
  ....

  /* Partition the list.	*/
  /* Basically the trick is to find a good pivot.  Just run down the
   * current list placing any node < pivot into one list and everthing
   * else into the other list.
   */
  partitionList (&lessList, &morequalList);

  /* Sort each sub-list.	*/
  LLSort (lessList);
  LLSort (morequalList);

  /* Hook the sorted sub-lists together.	*/
  tmpList = lessList;
  while (tmpList->next)
    tmpList = tmpList->next;
  tmpList->next = morequalList;

  return (lessList);
  }


PLEASE note that the above is just for illustrative puposes.  I have
actual working code that does this somewhere :-).  There are all sorts
of things that you can "optimize" for many typical cases.  Pivot
selection is the toughest (personally I use circular doubly-linked
lists, so I use the mean of the first and last elements).  If you
might have many duplicates then adding an equal list can save
re-processing all of them needlessly. ....  This should get you
started :-)...

Good luck,
	John Mitchell
	johnm@cory.Berkeley.EDU