Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #9727 > unrolled thread

Did the sort do anything?

Back to article view | Back to comp.lang.java.programmer

Contents

  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

#9727 — Did the sort do anything?

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

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.

-- 
Roedy Green Canadian Mind Products
http://mindprod.com
Capitalism has spurred the competition that makes CPUs faster and 
faster each year, but the focus on money makes software manufacturers 
do some peculiar things like deliberately leaving bugs and deficiencies
in the software so they can soak the customers for upgrades later.
Whether software is easy to use, or never loses data, when the company
has a near monopoly, is almost irrelevant to profits, and therefore 
ignored. The manufacturer focuses on cheap gimicks like dancing paper 
clips to dazzle naive first-time buyers. The needs of existing 
experienced users are almost irrelevant. I see software rental as the 
best remedy.

[toc] | [next] | [standalone]

#9729

On Mon, 07 Nov 2011 01:27:44 -0800, Roedy Green
<see_website@mindprod.com.invalid> wrote, quoted or indirectly quoted
someone who said :

>What is the easiest way to determine if a sort actually changed the
>order?
I decided to write an inOrder class with four methods, to handle
arrays/Lists Comparables/Comparators.

As usual the Generics befuddled me. So I decide to have a look at
Arrays.sort and Collections.sort to cannibalise.

To my astonishment, the signature of Arrays.sort looks like this:

 public static void sort(Object[] a) {

Surely they mean Comparable?  But when you do that, you get a mess of
unchecked errors. What gives?

Oddly the three more complex methods compile fine.

Did Sun just throw in the towel on doing the generics?
-- 
Roedy Green Canadian Mind Products
http://mindprod.com
Capitalism has spurred the competition that makes CPUs faster and 
faster each year, but the focus on money makes software manufacturers 
do some peculiar things like deliberately leaving bugs and deficiencies
in the software so they can soak the customers for upgrades later.
Whether software is easy to use, or never loses data, when the company
has a near monopoly, is almost irrelevant to profits, and therefore 
ignored. The manufacturer focuses on cheap gimicks like dancing paper 
clips to dazzle naive first-time buyers. The needs of existing 
experienced users are almost irrelevant. I see software rental as the 
best remedy.

[toc] | [prev] | [next] | [standalone]

#9738

Roedy Green <see_website@mindprod.com.invalid> wrote:
>  public static void sort(Object[] a) {
> Surely they mean Comparable?

Were it
  public static void sort(Comparable[] a) { ... }
you couldn't pass anything to it than an exact Comparable[],
but not e.g. an Integer[].

Have a look into the JLS for allowed implicit casts among arrays.

[toc] | [prev] | [next] | [standalone]

#9733

Roedy Green <see_website@mindprod.com.invalid> wrote:
> What is the easiest way to determine if a sort actually changed the
> order?

I'm feeling a deja vu.  You asked that question a while ago:

http://groups.google.com/group/comp.lang.java.programmer/browse_thread/thread/2c27b268c4450399/c86c12e0be28917b?

Did I miss any subtle but relevant change of the question?
Or did you re-ask it in the hope of getting new answers this
time?

PS: I found the old thread, because I remembered that "timsort" was
  mentioned among the answers, and within this group that was a rare
  enough thing...

[toc] | [prev] | [next] | [standalone]

#9736

On 07 Nov 2011 10:49:05 GMT, Andreas Leitgeb
<avl@gamma.logic.tuwien.ac.at> wrote, quoted or indirectly quoted
someone who said :

>Did I miss any subtle but relevant change of the question?
>Or did you re-ask it in the hope of getting new answers this
>time?

My memory is failing.  I have to check a 24-hour clock to find out if
it as AM or PM.   HIV, chemotherapy  and age take their toll.  When I
was younger it was exceptional. It is not something I can voluntarily
control.  It is damn nuisance.

I examine my code. I see the problem  but with no solution. If I did
ask earlier, I did not write an essay on it for the Java Glossary.  I
did not get a solution that could be easily turned into code.  Maybe I
thought about asking but did not get around to it.  Maybe I asked and
the solutions were too much work or not applicable to my situation. So
I ask again.  Somebody with better memory will find the old
discussion.  Maybe someone new will have a new idea.  Maybe someone
will have had some time after percolating on the problem in the
subconscious for a few months.

-- 
Roedy Green Canadian Mind Products
http://mindprod.com
Capitalism has spurred the competition that makes CPUs faster and 
faster each year, but the focus on money makes software manufacturers 
do some peculiar things like deliberately leaving bugs and deficiencies
in the software so they can soak the customers for upgrades later.
Whether software is easy to use, or never loses data, when the company
has a near monopoly, is almost irrelevant to profits, and therefore 
ignored. The manufacturer focuses on cheap gimicks like dancing paper 
clips to dazzle naive first-time buyers. The needs of existing 
experienced users are almost irrelevant. I see software rental as the 
best remedy.

[toc] | [prev] | [next] | [standalone]

#9739

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

[toc] | [prev] | [next] | [standalone]

#9741

On 11/7/2011 6:11 AM, Eric Sosman wrote:
> Post-sort order check won't do: The sort might have interchanged
> two different objects with equal keys.

If we're talking about Java's built-in sort methods, they are stable.

-- 
Beware of bugs in the above code; I have only proved it correct, not 
tried it. -- Donald E. Knuth

[toc] | [prev] | [next] | [standalone]

#9760

On 11/7/2011 9:30 AM, Joshua Cranmer wrote:
> On 11/7/2011 6:11 AM, Eric Sosman wrote:
>> Post-sort order check won't do: The sort might have interchanged
>> two different objects with equal keys.
>
> If we're talking about Java's built-in sort methods, they are stable.

     Um. Er. Yes, good point.  (Well, the Arrays.sort() methods for
primitives have no stability guarantees -- but with primitives you
couldn't tell anyhow, so ...)

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

[toc] | [prev] | [next] | [standalone]

#9742

On 11/7/2011 1:27 AM, Roedy Green wrote:
> What is the easiest way to determine if a sort actually changed the
> order?


The best and most correct would be to scan the new array for changes. 
If you're willing to relax your definition of "change" (and maybe 
"best"), you could just test if any element was out of order while the 
list was sorted.  If so, you can assume the list was changed, and if 
not, you might assume it was not.

Here's my attempt:


package quicktest;

import java.util.Arrays;
import java.util.Comparator;


/**
  *
  * @author Brenden
  */
public class LatchOutOfOrderComparator<T> implements Comparator<T> {

    private Comparator delegate;
    private boolean wasOutOfOrder;

    public LatchOutOfOrderComparator( Comparator delegate ) {
       this.delegate = delegate;
    }

    public boolean getWasOutOfOrder() {
       return wasOutOfOrder;
    }

    @Override
    public int compare(T o1, T o2) {
       int compare = delegate.compare( o1, o2 );
       if( compare < 0 ) wasOutOfOrder = true;
       return compare;
    }

}


class LatchOutOfOrderComparableTest {

    public static void main(String[] args) {
       String[] reversed = {"c", "b", "a" };
       System.out.println( Arrays.toString( reversed ) +
       " out of order:" );
       LatchOutOfOrderComparator l1 = new LatchOutOfOrderComparator(
               new StringComapartor() );
       Arrays.sort( reversed, l1 );
       System.out.println( l1.getWasOutOfOrder() );

       String[] ordered = {"a", "b", "c" };
       System.out.println( Arrays.toString( ordered ) +
       " out of order:" );
       LatchOutOfOrderComparator l2 = new LatchOutOfOrderComparator(
               new StringComapartor() );
       Arrays.sort( ordered, l2 );
       System.out.println( l2.getWasOutOfOrder() );
    }

    private static class StringComapartor implements Comparator<String> {

       public int compare(String o1, String o2) {
          return o1.compareTo(o2);
       }
    }
}

[toc] | [prev] | [next] | [standalone]

#9750

Roedy Green  <see_website@mindprod.com.invalid> wrote:
>What is the easiest way to determine if a sort actually changed the
>order?

Easiest?  Copy it, run the sort, do a compare.  Alternately, instrument your
collection to note when elements are changed (though the simplest version of
this won't detect when the sort changes order and then puts it back).  Or
instrument your sorting routing to note when it hits a state that indicates a
change is needed / was made.

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

Note that #1 is a different question than you asked.  "would a sort
change the order" is not the same as "did a sort change the order".  Many
implementations can be used for both, of course.

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

Instrumenting the collection or the sort method beats both of these in terms
of performance, though perhaps not in terms of simplicity.  
--
Mark Rafn    dagon@dagon.net    <http://www.dagon.net/>  

[toc] | [prev] | [next] | [standalone]

#9766

On 07/11/2011 3:50 PM, Dagon wrote:
> Note that #1 is a different question than you asked.  "would a sort
> change the order" is not the same as "did a sort change the order".

Isn't the simplest method (assuming a stable sort algorithm is/would be 
used) just to grovel over the input checking that thing[n] < thing[n+1] 
and returning true immediately if not, and false if the end of the input 
is reached? I.e., "is it already sorted?" seems equivalent to "would a 
sort change the order?" when the sort would be a stable sort. For "did 
the sort change the order?" just copy the input, sort, and then check 
the unsorted copy in like fashion; or check the input, store the result, 
and sort (or check the input, store the result, and sort iff the result 
says the input's not sorted).

[toc] | [prev] | [next] | [standalone]

#9770

On 07/11/2011 10:02 PM, Cindy wrote:
> On 07/11/2011 3:50 PM, Dagon wrote:
>> Note that #1 is a different question than you asked. "would a sort
>> change the order" is not the same as "did a sort change the order".
>
> Isn't the simplest method (assuming a stable sort algorithm is/would be
> used) just to grovel over the input checking that thing[n] < thing[n+1]
> and returning true immediately if not, and false if the end of the input
> is reached? I.e., "is it already sorted?" seems equivalent to "would a
> sort change the order?" when the sort would be a stable sort.

Clarification: "equivalent" in the sense that knowing the answer to 
either immediately tells you the answer to the other. However, the 
answers, of course, have opposite signs here so you'd have to negate one 
to get the other.

[toc] | [prev] | [next] | [standalone]

#9754

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).
>
> Can you do better than that?

For Q1: no - I don't think so.

For Q2: yes(*) - use your own sort that returns a boolean
indication whether it changed or not.

* = assuming that you context justifies doing something special - that
is not a given.

Arne

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web