Check if arraylist is sorted

Question

Possible Duplicate:
How to determine if a List is sorted in Java?

In java I have array list with names, how do I check if it sorted? I don't want it to be sorted. I just want it to return true if it is and false if it isn't.

So far I have this:

public boolean isSorted()
{
    boolean check = false;

    if (Collection.sort(bank, Bank.getOwner()).equals(bank))
    {
        check = true;
    }
    else
    {
        check = false;
    }      
    return check;
}

Where getOwner returns the owner name. Obviously I'm doing it wrong.

score 5 · Accepted Answer · answered Jan 08 '12 at 15:39

5

The obvious solution:

boolean ascending = true, descending = true;
for (int i = 1; i < arr.length && (ascending || descending); i++) {
    ascending = ascending && arr[i] >= arr[i-1];
    descending = descending && arr[i] <= arr[i-1];
}

answered Jan 08 '12 at 15:39

Voo

29,040
11
82
156

4

That could be more complicated than the most obvious solution. ;) – Peter Lawrey Jan 08 '12 at 15:44
@Peter The temptation to add the little shortcut in the loop was just too strong for me.. I'm weak :( – Voo Jan 08 '12 at 15:51

score 2 · Answer 2 · answered Jan 08 '12 at 15:53

Certainly not the most efficient option - but possibly the simplest:

public boolean isCollectionSorted(List list) {
    List copy = new ArrayList(list);
    Collections.sort(copy);
    return copy.equals(list);
}

This performs a shallow copy, sorts it and then compares the lists.

score 1 · Answer 3 · answered Jan 08 '12 at 15:39

You want just to check if the list is sorted. This is o(n) operation. Instead you are sorting the list n*log(n) and then comparing 2 lists o(n). So, total cost of your algorithm is n*log(n) + o(n).

Instead just iterate over the list and check that the current element is greater or equal than the previous. If your list should be sorted in descending order check that the current element is less or equal than previous.

Obviously the comparison of elements may be done using custom Comparator.

Fabian Barney · Answer 4 · 2012-01-08T22:19:35.747

With Google Guava this can look like this:

public class Bank {
    public static final Ordering<Bank> OWNER_ORDERING = new Ordering<Bank>() {

        @Override
        public int compare(Bank left, Bank right) {
            return left.getOwner().compareTo(right.getOwner());
        }
    };


    private String owner;

    public Bank(String owner) {
        this.owner = owner;
    }

    public String getOwner() {
        return owner;
    }
}

Usage is then:

List<Bank> banks = ImmutableList.of(new Bank("C"), new Bank("B"));
boolean ownerOrdered = Bank.OWNER_ORDERING.isOrdered(banks);

... or directly retrieving a sorted copy:

List<Bank> sortedCopyBanks = Bank.OWNER_ORDERING.sortedCopy(banks);

score 0 · Answer 5 · answered Jan 08 '12 at 15:38

0

Your solution is Ω(n log n) worst case.

You'd be better off iterating through the ArrayList and checking if each element is lesser/greater than the next one.

answered Jan 08 '12 at 15:38

soulcheck

36,297
6
91
90

score 0 · Answer 6 · answered Jan 08 '12 at 15:39

0

There is no JDK call that can tell you if a Collection is sorted, you have to implement your own logic to do that. There might be third party libraries that already implement this.

answered Jan 08 '12 at 15:39

Perception

79,279
19
185
195

SHiRKiT · Answer 7 · 2012-01-08T16:19:07.157

0

You can create a flag in your collection, and when you sort() your collection, you turn that flag to true. If any modification is made in your collection, like add() move(), you can set the flag to false. That's the optmizied solution you can find, but requires a flag and a modified collection.

edited Jan 08 '12 at 16:19

answered Jan 08 '12 at 16:01

SHiRKiT

1,024
3
11
30

How exactly would a sorted collection turn unsorted by removing an element? ;) – Voo Jan 08 '12 at 16:11

Check if arraylist is sorted

7 Answers7