CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: how would you check if an array of integers is sorted

#### Hybrid View

1. Junior Member
Join Date
Feb 2012
Posts
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?

2. Elite Member
Join Date
Oct 2006
Location
Sweden
Posts
3,649

## 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.

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```

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Click Here to Expand Forum to Full Width

On-Demand Webinars (sponsored)

×
We have made updates to our Privacy Policy to reflect the implementation of the General Data Protection Regulation.