Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!cbatt!cwruecmp!hal!ncoast!btb
From: btb@ncoast.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc,sci.research
Subject: Re: Information on order(N) sort
Message-ID: <2141@ncoast.UUCP>
Date: Mon, 2-Mar-87 09:30:15 EST
Article-I.D.: ncoast.2141
Posted: Mon Mar  2 09:30:15 1987
Date-Received: Wed, 4-Mar-87 20:46:44 EST
References: <814@fmsrl7.UUCP> <25183@rochester.ARPA> <561@aw.sei.cmu.edu.sei.cmu.edu> <1080@hounx.UUCP> <25329@rochester.ARPA>
Reply-To: btb@ncoast.UUCP (Brad Banko)
Distribution: world
Organization: Cleveland Public Access UNIX, Cleveland, OH
Lines: 27
Keywords: sort, publish, papers, help
Xref: utgpu comp.edu:135 comp.lang.misc:316 comp.os.misc:48 sci.research:66

In article <25329@rochester.ARPA> crowl@rochester.UUCP (Lawrence Crowl) writes:
>In article <1080@hounx.UUCP> kort@hounx.UUCP (B.KORT) writes:
>>If you're short on memory, the bubble sort, slow and humble as it is,
>>will get the job done.  It uses lots of pair-wise comparisons.
>
>The quicksort is an inplace O(n log n) sort while the bubble sort is O(n^2).
>The quicksort will provide much better performance for the same space.  That
>is unless you are worried about program space.
>-- 
>  Lawrence Crowl		716-275-5766	University of Rochester

the one problem with quicksort that has always bothered me is that it is
not stable (right?), it doesn't preserve any order that already exists in
what you are trying to sort, so that you can't easily use it to sort on
multiple keys sequentially... i am certainly no expert on sorts, but for
the small kinds of sorts that i have a need for, selection sort is the
most practical... yes, it is an O(n^2) sort, but it is much faster than
bubble sort because it doesn't do O(n^2) exchanges, only O(n).
selection sort is also as easy to remember as bubble sort.

-- 
			Brad Banko
			...!decvax!cwruecmp!ncoast!btb
			Cleveland, Ohio

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