how would you check if an array of integers is sorted
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3

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

  1. #1
    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. #2
    Join Date
    Oct 2006
    Location
    Sweden
    Posts
    3,639

    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
    http://www.codeguru.com/forum/announ...nouncementid=6
    and http://www.codeguru.com/forum/showthread.php?t=366302 before posting

    Refresh your memory on formatting tags here
    http://www.codeguru.com/forum/misc.php?do=bbcode

    Get your free MS compiler here
    http://www.microsoft.com/visualstudio/eng/downloads

  3. #3
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,006

    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center