Path: csiph.com!x330-a1.tempe.blueboxinc.net!aioe.org!texta.sil.at!newscore.univie.ac.at!aconews-feed.univie.ac.at!aconews.univie.ac.at!not-for-mail Newsgroups: comp.lang.java.programmer From: Andreas Leitgeb Subject: Re: Did the sort do anything? References: Reply-To: avl@logic.at User-Agent: slrn/pre0.9.9-111 (Linux) Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: Date: 10 May 2011 16:11:19 GMT Lines: 19 NNTP-Posting-Host: gamma.logic.tuwien.ac.at X-Trace: 1305043879 tunews.univie.ac.at 60386 128.130.175.3 X-Complaints-To: abuse@tuwien.ac.at Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:3924 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. > 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. 5. wrap the Collection such, that certain modifications set an "unsorted"- flag, e.g. if an element is inserted/replaced/appended that doesn't compare in the intended way with its neighbours. Then shortcut the sort, if the said flag is clear.