Path: csiph.com!x330-a1.tempe.blueboxinc.net!aioe.org!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail From: Daniele Futtorovic Newsgroups: comp.lang.java.programmer Subject: Re: Did the sort do anything? Date: Tue, 10 May 2011 21:26:57 +0200 Organization: A noiseless patient Spider Lines: 33 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Tue, 10 May 2011 19:26:58 +0000 (UTC) Injection-Info: mx03.eternal-september.org; posting-host="3ontdQOwqTpoXYF7H7NQoA"; logging-data="9112"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+VZ8dbufvig27cAGAa5NB0" User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-GB; rv:1.9.2.17) Gecko/20110414 Thunderbird/3.1.10 In-Reply-To: Cancel-Lock: sha1:nlcAcBhBnnJl0aAJVtPPyfmIOoQ= Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:3934 On 10/05/2011 17:06, Roedy Green allegedly wrote: > Often you sort things when they are already sorted. > > I am interested in simple algorithms to detect whether the sort > actually did anything. > > Some suggestions: > > 1. do a pairwise compare of the times before the sort, and if all is > in order, bypass the sort. > > 2. back a copy of the unsorted list of items. After the sort, do a > pairwise compare for identity. If all are identical, the sort did not > do anything. > > 3. write your own sort that has a boolean function you can ask if it > moved anything. > > 4. do some sort of checksum before and after. > I find the checksum idea quite intriguing, actually. It would have to do more operations than some kind of perhaps binary seep through, (although just as many if the list actually /is/ sorted). But the average greater efficiency of e.g. #hashCode() vs. #compare() might well offset that, meponders. Is there any existing research on this? -- DF. An escaped convict once said to me: "Alcatraz is the place to be"