CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums
Results 1 to 3 of 3

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

  1. #1
    Join Date
    Feb 2012

    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. #2
    Join Date
    Oct 2006

    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.
    Debugging is twice as hard as writing the code in the first place.
    Therefore, if you write the code as cleverly as possible, you are, by
    definition, not smart enough to debug it.
    - Brian W. Kernighan

    To enhance your chance's of getting an answer be sure to read
    and before posting

    Refresh your memory on formatting tags here

    Get your free MS compiler here

  3. #3
    Join Date
    Feb 2011
    United States

    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:

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

    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

Windows Mobile Development Center

Click Here to Expand Forum to Full Width

On-Demand Webinars (sponsored)