Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!necntc!ames!lll-tis!ptsfa!ihnp4!cuae2!ltuxa!ttrdc!levy
From: levy@ttrdc.UUCP (Daniel R. Levy)
Newsgroups: comp.misc,comp.lang.c
Subject: Re: Fast, stable, free, small sorts?
Message-ID: <1923@ttrdc.UUCP>
Date: Tue, 6-Oct-87 02:06:14 EDT
Article-I.D.: ttrdc.1923
Posted: Tue Oct  6 02:06:14 1987
Date-Received: Sun, 11-Oct-87 14:13:09 EDT
References: <460@naucse.UUCP> <3603@venera.isi.edu> <20029@cca.CCA.COM> <463@naucse.UUCP>
Organization: AT&T, Skokie, IL
Lines: 50
Xref: mnetor comp.misc:1439 comp.lang.c:4790

In article <463@naucse.UUCP>, sbw@naucse.UUCP (Steve Wampler) writes:
> If it's to be be
> more general purpose, then so far as I can tell, it must be stable.  I would
> love to be shown wrong on this, as I seem to be incapable of writing a minimal
> storage stable sort that is fast on large data sets.

I'm a hacker, not a CS guru, so I might be full of hooey on this.  But, how
about using the standard UNIX qsort(3) routine with a compare() function which,
when all else is equal, ranks the items according to their original position
in the list?  Something like

struct datum {
	TYPE item;
	int position;
} ITEMS[NITEMS];

	...  /* fill the array with data */

int i;
for (i=0; i<NITEMS; i++)
	ITEMS[i].position = i;

int compare();

qsort((char *)ITEMS, NITEMS, sizeof(struct datum), compare);

...

compare(a,b)
char *a, *b;
{
	int i;
	i = DIFFERENCE(((struct datum *)a) -> item,
		((struct datum *)b) -> item);
	if (i)	/* <0 or >0 */
		return i;
	else
		return ((struct datum *)a) -> position -
			((struct datum *)b) -> position;	/* stable */
}

The catch of course is that you need to store NITEMS int values, as well
as slowing down the swap operations since the datum size is larger than
if it comprised only the data of interest.  But the order of time and
storage in terms of NITEMS does not change.
-- 
|------------Dan Levy------------|  Path: ..!{akgua,homxb,ihnp4,ltuxa,mvuxa,
|         an Engihacker @        |		vax135}!ttrdc!ttrda!levy
| AT&T Computer Systems Division |  Disclaimer?  Huh?  What disclaimer???
|--------Skokie, Illinois--------|