Did the sort do anything?

[Roedy Green]

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.

 

[Roedy Green]

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.

 

[Andreas Leitgeb]

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...ead/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...

 

[Roedy Green]

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.

 

[Andreas Leitgeb]

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.

 

[Eric Sosman]

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

 

[Joshua Cranmer]

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.

 

[markspace]

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);
}
}
}

 

[Dagon]

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.

 

[Arne Vajhøj]

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

 

[Eric Sosman]

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

 

[Cindy]

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

 

[Cindy]

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.