Groups > comp.lang.java.programmer > #9739

Re: Did the sort do anything?

Path	csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail
From	Eric Sosman <esosman@ieee-dot-org.invalid>
Newsgroups	comp.lang.java.programmer
Subject	Re: Did the sort do anything?
Date	Mon, 07 Nov 2011 07:11:09 -0500
Organization	A noiseless patient Spider
Lines	37
Message-ID	<j98hu1$aj8$1@dont-email.me> (permalink)
References	<4d8fb7l8qb1g820cphr4fh447a9uitlddj@4ax.com>
Mime-Version	1.0
Content-Type	text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding	7bit
Injection-Date	Mon, 7 Nov 2011 12:11:45 +0000 (UTC)
Injection-Info	mx04.eternal-september.org; posting-host="HSlJAUb3pGXi3i7ZL/HoAw"; logging-data="10856"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+QldUUoyGJCAgg7Tx01kdU"
User-Agent	Mozilla/5.0 (Windows NT 5.1; rv:7.0.1) Gecko/20110929 Thunderbird/7.0.1
In-Reply-To	<4d8fb7l8qb1g820cphr4fh447a9uitlddj@4ax.com>
Cancel-Lock	sha1:sbvrxc0+aiHhZvCjvYSKIX+9BSg=
Xref	x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:9739

Show key headers only | View raw

On 11/7/2011 4:27 AM, Roedy Green wrote:
> What is the easiest way to determine if a sort actually changed the
> order?
>
> I run into this in two situations.
>
> 1. do I really need to sort in cases when  the data are most likely
> already in order? (perhaps just sorting is as fast as trying to bypass
> it most of the time).
>
> 2. did the sort change anything. Do I have to commit the changed order
> to disk?
>
> The obvious solution to (1) is to pairwise compare array exported from
> the collection before the sort.
>
> The obvious solution to (2) is compare corresponding elements in
> arrays exported before and after the sort with the comparator, or use
> (1).

     Post-sort order check won't do: The sort might have interchanged
two different objects with equal keys.

> Can you do better than that?
>
> Oracle might add a method isInOrder and/or didOrderChange. The various
> sort methods are static, so their is no natural place to put them.

     The sort method itself could return a value to indicate that it
changed the order, didn't change the order, or is unable to say for
sure whether it did or didn't.  (Some algorithms -- Heapsort, for
example, or a straight merge -- don't offer an easy way to tell whether
something happened.)

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

Thread

Did the sort do anything? Roedy Green <see_website@mindprod.com.invalid> - 2011-11-07 01:27 -0800
  Re: Did the sort do anything? Roedy Green <see_website@mindprod.com.invalid> - 2011-11-07 02:20 -0800
    Re: Did the sort do anything? Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-11-07 11:21 +0000
  Re: Did the sort do anything? Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-11-07 10:49 +0000
    Re: Did the sort do anything? Roedy Green <see_website@mindprod.com.invalid> - 2011-11-07 02:58 -0800
  Re: Did the sort do anything? Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-11-07 07:11 -0500
    Re: Did the sort do anything? Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-11-07 08:30 -0600
      Re: Did the sort do anything? Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-11-07 21:03 -0500
  Re: Did the sort do anything? markspace <-@.> - 2011-11-07 07:48 -0800
  Re: Did the sort do anything? dagon@dagon.net (Dagon) - 2011-11-07 12:50 -0800
    Re: Did the sort do anything? Cindy <c.thurston@frell.okb.uwa.edu> - 2011-11-07 22:02 -0500
      Re: Did the sort do anything? Cindy <c.thurston@frell.okb.uwa.edu> - 2011-11-07 22:22 -0500
  Re: Did the sort do anything? Arne Vajhøj <arne@vajhoej.dk> - 2011-11-07 17:42 -0500

csiph-web