How to check if array is already sorted

Question

so how to make such logic

int[] arr = {2, 5, 3};

if (/* arr is sorted */)
    ....
else 
    ...

Its bad that method Array.sort is void

You have to write your own logic. Iterate over the array, and test each element with the next element. — Rohit Jain
– Rohit Jain, Commented Aug 7, 2013 at 18:41
Arrays.sort sorts the array. It doesn't check whether an array is sorted or not. — Code Enthusiastic
– Code Enthusiastic, Commented Aug 7, 2013 at 18:55

arshajii · Accepted Answer · 2013-08-07 18:41:01Z

50

You don't need to sort your array to check if it's sorted. Loop over each consecutive pair of elements and check if the first is less than the second; if you find a pair for which this isn't true, the array is not sorted.

boolean sorted = true;

for (int i = 0; i < arr.length - 1; i++) {
    if (arr[i] > arr[i+1]) {
        sorted = false;
        break;
    }
}

answered Aug 7, 2013 at 18:41

arshajii

130k26 gold badges246 silver badges293 bronze badges

Sign up to request clarification or add additional context in comments.

13 Comments

Kon Over a year ago

It's impossible to be faster. You have to look at all the elements at least once, obviously. How else can you be share if you don't look at them all?

arshajii Over a year ago

@OxomHuK You can put all of this in a function and just call that. Less code doesn't always mean better.

arshajii Over a year ago

@Elist Why would you use that? You would lose the short-circuiting ability.

BlackHatSamurai Over a year ago

Whoever down voted was probably jealous. Great answer. Simple and efficient.

arshajii Over a year ago

@Elist That only allows you to access one element of the array per iteration, we need to access two.

|

Mike Samuel · Accepted Answer · 2013-08-07 19:52:30Z

13

public static <T>
boolean isArraySorted(T[] elements, Comparator<? super T> cmp) {
  int n = elements.length;
  for (int i = 1; i < n; ++i) {
    if (cmp.compare(elements[i-1], elements[i]) > 0) { return false; }
  }
  return true;
}

edited Aug 7, 2013 at 19:52

answered Aug 7, 2013 at 18:42

Mike Samuel

121k30 gold badges230 silver badges255 bronze badges

5 Comments

Paul Vargas Over a year ago

+1 Use the generics... Very good toy, but, I believe, I have never needed to ask if an array is already sorted.

William Morrison Over a year ago

This is great, you come up with it on the fly or have it stashed away somewhere lol? I hope the latter for my fragile ego, good job. +1

Marko Topolnik Over a year ago

Extracting length is really unnecessary, though, unless interpreting.

arshajii Over a year ago

Note that this will not work with the OP's example, since he wants to check an array of primitives. In an ideal world, one would have an analogous method for each primitive array type.

Mike Samuel Over a year ago

@arshajii, Good point. I assumed that was a throwaway example, but to make it truly generic I'd have to use java.lang.reflect.Array along with @SuppressWarnings("unchecked") which would defeat all the generic safety checks you get from the compiler. I think overloading for primitive types is a good idea.

Anshul · Accepted Answer · 2013-08-07 18:43:38Z

3

Well you can check it in O(n) worst case linear time. A non-sorted array (assuming you mean sorting in ascending order) will have a trip point. That is at some point arr[i] > arr[i+1]

All you need to do is

boolean is_array_sorted(int arr[]) {
  for(int i=0; i < arr.len-1; i++) {
    if(arr[i] > arr[i+1]) {
       return false;
    }
  }
  return true;
}

Just change the > to < if your array sort is supposed to be descending order

answered Aug 7, 2013 at 18:43

Anshul

7201 gold badge5 silver badges19 bronze badges

Comments

flavian · Accepted Answer · 2013-08-07 19:02:48Z

2

public static boolean isSorted(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        if (a[i + 1] < a[i]) {
            return false;
        };
    }
    return true;
}

edited Aug 7, 2013 at 19:02

answered Aug 7, 2013 at 18:42

flavian

28.6k11 gold badges68 silver badges107 bronze badges

1 Comment

ajb Over a year ago

should be arr.length, not arr.length()

user2276686 · Accepted Answer · 2018-03-28 00:54:07Z

1

A shorter version:

[0,1,2,3,4].reduce((a,v) => (a!==false) && (a <= v) ? v : false, -Infinity)
[4,3,1,2,0].reduce((a,v) => (a!==false) && (a >= v) ? v : false, +Infinity)

Be careful, as in some cases it isn't effective because it will loop through entire array without breaking prematurely.

Array.prototype.reduce()

edited Mar 28, 2018 at 0:54

user1143634

answered May 19, 2017 at 3:42

user2276686

2,0962 gold badges16 silver badges8 bronze badges

2 Comments

Jack G Over a year ago

Very helpful answer, HOWEVER, wrong programming language. Java is not the same as javascript.

vdj4y Over a year ago

@JackGiffin, Java got stream right, you can use reduce() just fine

xhg · Accepted Answer · 2019-02-14 02:51:02Z

1

You can use .every

let isSorted = array.every((v, i) => (i === 0 || v <= array[i - 1]))
  || array.every((v, i) => (i === 0 || v >= array[i - 1]))

answered Feb 14, 2019 at 2:51

xhg

1,9033 gold badges22 silver badges36 bronze badges

Comments

Armine · Accepted Answer · 2021-11-01 13:54:59Z

0

function isArraySorted(arr) {
    for (let i=0;i<arr.length;i++) {
        if (arr[i+1] && (arr[i+1] > arr[i])) {
            continue;
        } else if(arr[i+1] && (arr[i+1] < arr[i])) {
            return false;
        }
    }

    return true;
}

This worked for me.

edited Nov 1, 2021 at 13:54

Armine

1,6953 gold badges26 silver badges45 bronze badges

answered Sep 20, 2019 at 5:46

Nilanjan Banerjee

91 bronze badge

Comments

Dexter Legaspi · Accepted Answer · 2021-11-29 04:03:56Z

0

A slight variation of the generics version by Mike Samuel but using Comparable<T> instead of Comparator<T>:

public static <T extends Comparable<? super T>> boolean isSorted(T[] elements) {
    int n = elements.length;
    for (int i = 1; i < n; ++i) {
        if (elements[i - 1].compareTo(elements[i]) > 0) {
            return false;
        }
    }
    return true;
}

answered Nov 29, 2021 at 4:03

Dexter Legaspi

3,3321 gold badge37 silver badges29 bronze badges

Comments

Mir-Ismaili · Accepted Answer · 2025-02-06 13:52:28Z

Use .some() (or .every()) to return the result as soon as possible:

const isArraySortedAscending = (array) => array.length < 2 || !array.slice(1).some((v, i) => (v < array[i]))

const isArraySortedDescending = (array) => array.length < 2 || !array.slice(1).some((v, i) => (v > array[i]))

Test:

const isArraySortedAscending = (array) => array.length < 2 || !array.slice(1).some((v, i) => (v < array[i]))

const isArraySortedDescending = (array) => array.length < 2 || !array.slice(1).some((v, i) => (v > array[i]))

console.log(isArraySortedAscending([1, 2, 3])) // true
console.log(isArraySortedDescending([1, 2, 3])) // false

console.log(isArraySortedAscending([3, 2, 1])) // false
console.log(isArraySortedDescending([3, 2, 1])) // true

console.log(isArraySortedAscending([1, 3, 2])) // false
console.log(isArraySortedDescending([1, 3, 2])) // false

console.log(isArraySortedAscending([1])) // true
console.log(isArraySortedDescending([1])) // true

Collectives™ on Stack Overflow

How to check if array is already sorted

9 Answers 9

13 Comments

5 Comments

Comments

1 Comment

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

9 Answers 9

13 Comments

5 Comments

Comments

1 Comment

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related