how would you check if an array of integers is sorted

• February 10th, 2012, 12:37 AM
dlee32695
how would you check if an array of integers is sorted
How would you implement a simple code to check to see if the integers in the array are already sorted or not?
• February 10th, 2012, 01:09 AM
S_M_A
Re: how would you check if an array of integers is sorted
I don't think I would. The check probably consumes about the same time as sort do so I would keep track of if changes has been made since last sort or not instead.
• February 10th, 2012, 11:39 PM
BioPhysEngr
Re: how would you check if an array of integers is sorted
Hrm. Well you can check in O(n) time and sort in [usually] O(n log n) time. So if we checked first we'd get total complexity of:

n*log[n] + n = (n+1)*log[n] which is O(n*log[n]) except that we now handle the degenerate case of an array already being sorted, which completes in O(n).

So, for some overhead, we could get better best-case complexity and equivalent worst-case complexity.

In reality, I suspect SMA is correct; unless n is both quite large AND you're likely to get passed already-sorted arrays often.

The general algorithm to check if an array is already sorted (in ascending order) is something like:

Code:

```foreach element in the array     if element > nextElement         return false immediately //If the whole loop completes without detecting failure return true```