Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!rutgers!uwvax!astroatc!johnw
From: johnw@astroatc.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc,sci.research
Subject: Re: Information on order(N) sort
Message-ID: <181@astroatc.UUCP>
Date: Wed, 11-Mar-87 22:17:28 EST
Article-I.D.: astroatc.181
Posted: Wed Mar 11 22:17:28 1987
Date-Received: Fri, 13-Mar-87 03:11:20 EST
References: <814@fmsrl7.UUCP> <25183@rochester.ARPA>
Reply-To: johnw@astroatc.UUCP (John F. Wardale)
Organization: Astronautics Technology Cntr, Madison, WI
Lines: 43
Keywords: sort, publish, papers, help
Xref: utgpu comp.edu:144 comp.lang.misc:333 comp.os.misc:52 sci.research:73

First:  In the discussions of "bubble" vs other sorts, I assume
(perhapes I'm brain-damaged) that "bubble-sort" referes to and
O(n^2) sort, not just the "REAL (or supper-cruddy O(n^2) style) BUBBLE"
sort.


In article <3178@gitpyr.gatech.EDU> jkg@gitpyr.UUCP (Jim Greenlee) writes:
>In article <2701@well.UUCP> physh@well.UUCP (Jon Foreman) writes:
>>Has anyone ever written a program which will unsort a dataset
>>to the worst case for various types of sorts? 
>
>This is easy for Quicksort (which seems to a favorite of netters) - 
> just sort the dataset!

Sorry, but the worst case for any decent(*) QuickSort is *NOT*
just reverse order!!

	(*) decent here means one that uses the median of three for
	the pivot!

-----------------
Someone made a comment about QuickSort *NOT* maintainig order.
I wrote a quick-sort package that *DID* do this.  It swapped
indexes, not the real data (unless requested -- this generality
was required [Fortran: tables in parrallel arrays...])  Anyway,
all I had to do was change the compare to check the original INDEX
for equal VALUEd elements!   It worked just fine!

In retrospect, I pro'ly should have started from scratch and
researched algorithms, but I was 1: young and foolish at the time,
2: given a very limited implementation as a model to work from.


			John W

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
Name:	John F. Wardale
UUCP:	... {seismo | harvard | ihnp4} !uwvax!astroatc!johnw
arpa:   astroatc!johnw@rsch.wisc.edu
snail:	5800 Cottage Gr. Rd. ;;; Madison WI 53716
audio:	608-221-9001 eXt 110

To err is human, to really foul up world news requires the net!