Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!cbosgd!mandrill!hal!ncoast!btb
From: btb@ncoast.UUCP
Newsgroups: comp.misc,comp.lang.c
Subject: Re: Fast, stable, free, small sorts?
Message-ID: <4791@ncoast.UUCP>
Date: Sat, 3-Oct-87 11:19:46 EDT
Article-I.D.: ncoast.4791
Posted: Sat Oct  3 11:19:46 1987
Date-Received: Sun, 4-Oct-87 07:25:18 EDT
References: <460@naucse.UUCP> <3603@venera.isi.edu> <20029@cca.CCA.COM> <105@nusdhub.UUCP>
Reply-To: btb@ncoast.UUCP (Brad Banko)
Organization: Cleveland Public Access UN*X, Cleveland, Oh
Lines: 31
Xref: utgpu comp.misc:1220 comp.lang.c:4453

i happen to think that stability is a very useful property to have
(at least as an option) in a sorting algorithm... coming from a vms 
environment, which wasn't pretty, but at least was humungous enough to
provide "LOTS OF COMMAND OPTIONS" particularly with respect to its
directory function and sort function, the SORT utility under MSDOS is
a big let down... it may be fast, but it doesn't know about multiple
sort keys and it IS NOT STABLE which is a pain when you are trying to 
maintain directories containing 200+ files... the speed isn't so critical
(using the sort utility to sort directory listings (dir | sort /+n...),
but the lack of stability makes it impossible to chain sorts together to
get a stream sorted the way you need it...
	you might say that this is a mistake that microsoft made, and i
might agree with you, but since i am primarily a scientific applications
programmer, writing a do it all sort is not within the scope of my 
priorities or available time (plus, since i must work in fortran, it is
not something i would want to do in that language anyway).
	a few months back, i participated in a similar discussion, and one
guy said that he was able to make a small change to his quicksort routine
to allow it to sort with stability... anyone have any comments?
somebody else commented that shellsort is not necessarily stable, but i
don't understand why not, since essentially if you don't swap on equality
things should stay in order, shouldn't they?

-- 
			Brad Banko
			Columbus, Ohio
			(formerly ...!decvax!cwruecmp!ncoast!btb)
			btb%ncoast@mandrill.cwru.edu

"The only thing we have to fear on this planet is man."
			-- Carl Jung, 1875-1961