-
February 10th, 2012, 01:37 AM
#1
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, 02:09 AM
#2
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 11th, 2012, 12:39 AM
#3
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
Best Regards,
BioPhysEngr
http://blog.biophysengr.net
--
All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|