Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!cbatt!ihnp4!ptsfa!lll-lcc!ames!ucbcad!ucbvax!decvax!tektronix!sequent!mntgfx!franka
From: franka@mntgfx.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc,sci.research
Subject: Re: Information on order(N) sort
Message-ID: <546@mntgfx.MENTOR.COM>
Date: Fri, 27-Feb-87 14:29:57 EST
Article-I.D.: mntgfx.546
Posted: Fri Feb 27 14:29:57 1987
Date-Received: Sun, 1-Mar-87 14:38:33 EST
References: <814@fmsrl7.UUCP> <25183@rochester.ARPA> <561@aw.sei.cmu.edu.sei.cmu.edu> <1080@hounx.UUCP> <25329@rochester.ARPA>
Reply-To: franka@mntgfx.UUCP (Frank A. Adrian)
Distribution: world
Organization: Mentor Graphics, Beaverton, OR
Lines: 25
Keywords: sort, publish, papers, help
Xref: utgpu comp.edu:125 comp.lang.misc:299 comp.os.misc:40 sci.research:60

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.
>-- 

However, quicksort still uses O(log n) space for the stack of unsorted sub-arrays.
Bubble sort only uses O(1) (the variable for the swap).  In addition, quicksort
does not achieve better performance than bubble sort until about 15 elements are to
be sorted.  It takes an even larger array (~500 elements) to outdo heapsort.
Quicksort's performance on almost sorted arrays is even worse.  Remember, quicksort
is O(n log n) average case.  Worst case it degenerates to O(n**2).  The moral of
this story is not to make blind statements.  When choosing a sorting algorithm you
need to

	1) take into account the amount of data to be sorted...
    2) take into account the distribution of the data to be sorted...
    3) have very good luck in predicting the two previous conditions.

Frank Adrian
Mentor Graphics, Inc.