Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.org!de-l.enfer-du-nord.net!feeder1.enfer-du-nord.net!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Robert Klemme Newsgroups: comp.lang.java.programmer Subject: Re: Did the sort do anything? Date: Wed, 11 May 2011 20:40:43 +0200 Lines: 27 Message-ID: <9303hcFq0nU1@mid.individual.net> References: Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Trace: individual.net wYR39a8Vm2/J3LPE1pTXSwbSzo9thGz74X3+b3yjEwc2s8KHs= Cancel-Lock: sha1:q7fNs7ytkWE8yrEddFASKN1SXm4= User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.12) Gecko/20101027 Lightning/1.0b2 Thunderbird/3.1.6 In-Reply-To: Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:3984 On 05/10/2011 05:06 PM, Roedy Green wrote: > Often you sort things when they are already sorted. > > I am interested in simple algorithms to detect whether the sort > actually did anything. What would the benefit of this be? When you learn the fact the current sorting run has been done already. And the data tells you nothing about what future sorts will do. OK, you know, they won't do anything if you do not modify the collection / array. But you did know that before, didn't you? And if you insert in sort order then you also know that there is no additional sort necessary. If you pull the data from some external source you also do not know whether next time round you need to sort. So what is this information useful for? Btw, couldn't option 3 be tricky? Depending on the sorting algorithm things might be moved around but the final order might be the same as before. Not that this would be desirable but I am pretty sure there are sorting algorithms which have this property (probably quicksort). Now, how then do you interpret your boolean flag? Basically you only know sequences are identical if there was no movement whatsoever, but if there was movement then you do not know. Which means you would need to apply one of the other strategies additionally... Kind regards robert