How would you implement a simple code to check to see if the integers in the array are already sorted or not?
Printable View
How would you implement a simple code to check to see if the integers in the array are already sorted or not?
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.
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