Like Tree3Likes
  • 1 Post By laserlight
  • 1 Post By laserlight
  • 1 Post By whiteflags

How to detect if a array is sorted.

This is a discussion on How to detect if a array is sorted. within the C++ Programming forums, part of the General Programming Boards category; Hi,all! Is there a way to detect if a array is sorted or not?...

  1. #1
    Registered User
    Join Date
    Aug 2012
    Posts
    11

    Question How to detect if a array is sorted.

    Hi,all!
    Is there a way to detect if a array is sorted or not?

  2. #2
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,666
    Loop through the array with the same comparison(s) as a sort. For example, integers stored in ascending order means that the smaller integers will be encountered first. If you find an integer somewhere that is out of order then you know it isn't sorted.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,632
    Quote Originally Posted by just_rookie
    Is there a way to detect if a array is sorted or not?
    whiteflags' suggestion is good for a novice to practice, but once you have that practice, it would be simpler to #include <algorithm> then use the is_sorted generic algorithm.
    rodrigorules likes this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Aug 2005
    Posts
    266
    Great suggestion laserlight.

    just_rookie if you would like to 'roll your own', just iterate over the array and check if the current element is 'less than' the next element. If you receive true over the entire array, it is sorted.
    Last edited by rodrigorules; 09-09-2012 at 12:13 AM. Reason: clarification

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,300
    I thought that the definition of "sorted" implied an obvious simple algorithm for checking it.

    You might benefit from learning how to write that.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User
    Join Date
    Aug 2012
    Posts
    11
    Quote Originally Posted by whiteflags View Post
    Loop through the array with the same comparison(s) as a sort. For example, integers stored in ascending order means that the smaller integers will be encountered first. If you find an integer somewhere that is out of order then you know it isn't sorted.
    my code as follows.I used your method,but it cannot solve this problem:
    Code:
    :
    #include <iostream>
    #include <ctime>
    #include <cstdlib>
    
    using namespace std;
    
    void displayarr( int arr[],int size )
    {
        for ( int i = 0;i < size;i++ )
        {
            cout << arr[i] << "  ";
            }
        }
    
    int main()
    {
        int arr[10];
        srand(time(NULL));
        for ( int i = 0;i < 10;i++ )
        {
            arr[i] = rand() % 100;
        }
        for ( int i = 0 ;i < 9;i++ )
        {
        if ( arr[ i ] < arr[ i+1 ] )
            {
           cout << "Sorted!" << endl;
        displayarr(arr,10);
            }
        }
    }

  7. #7
    Registered User
    Join Date
    Aug 2012
    Posts
    11
    Quote Originally Posted by laserlight View Post
    whiteflags' suggestion is good for a novice to practice, but once you have that practice, it would be simpler to #include <algorithm> then use the is_sorted generic algorithm.
    whiteflags' suggestion is good for me,because I didn't learn generic algorithm.Thank you for your reply!

  8. #8
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,666
    The biggest mistake you made was writing "Sorted!" and displaying the array each time around the loop. You won't know until you've compared each element in turn once. Your if statement is fine, but you don't do anything if the if condition is false, which is a mistake.

  9. #9
    Registered User
    Join Date
    Aug 2012
    Posts
    11

    Question

    Quote Originally Posted by whiteflags View Post
    The biggest mistake you made was writing "Sorted!" and displaying the array each time around the loop. You won't know until you've compared each element in turn once. Your if statement is fine, but you don't do anything if the if condition is false, which is a mistake.
    hi,someone send me a piece of code as follows,but i can not understand this code well,so please do me a favor!Thank you!
    Code:
    #include <cstdlib>
    #include <ctime>
    #include <iostream>
    using namespace std;
    int main()
    {
     int i;
     int p[4];
     cout << "The original array is:" << endl;
     srand(time(NULL));
     for(i=0;i<4;i++)
     {
     p[i] = rand()%10;
     cout << p[i] << "  ";
    }
     for(i=0;i<3;i++)
     {
     if(p[i]>p[i+1])
     {
     break;
     }
     }
     if(i==3)
     {
     printf("Ascending array!\n");
     }
     else
     {
     for(i=0;i<3;i++)
     {
     if(p[i]<p[i+1])
     {
     break;
     }
     }
     if(i==3)
     {
     printf("Descending array!\n");
     }
     else
     {
     printf("Unsorted array!\n");
     }
     }
     free(p);
     return 0;
    }
    Last edited by just_rookie; 09-09-2012 at 09:11 PM.

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,632
    If I were you, I would write a function like this:
    Code:
    bool array_is_sorted(int arr[], int size)
    {
        // ...
    }
    Then call it from the main function.

    Quote Originally Posted by just_rookie
    hi,someone send me a piece of code as follows,but i can not understand this code well,so please do me a favor!Thank you!
    Concentrate on your own code. You are not that far away from a working solution.
    just_rookie likes this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Aug 2005
    Posts
    266
    just_rookie, it looks like the logic you have in your previous post's code is correct.

    What is the problem?
    Check out my programming / algorithm blog @ http://www.swageroo.com

  12. #12
    Registered User
    Join Date
    Aug 2012
    Posts
    11
    Quote Originally Posted by rodrigorules View Post
    just_rookie, it looks like the logic you have in your previous post's code is correct.

    What is the problem?
    My problem is why we need the "if(i==3)" statement?

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,632
    Quote Originally Posted by just_rookie
    My problem is why we need the "if(i==3)" statement?
    That is one way to check if all elements of the array have been checked. The array has 4 elements, so you only need to check for 3 elements (since you are checking the current and next). However, if you write the function that I suggested, you don't need to do this since you would just return true after the loop ends.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Registered User
    Join Date
    Aug 2012
    Posts
    11
    Quote Originally Posted by laserlight View Post
    That is one way to check if all elements of the array have been checked. The array has 4 elements, so you only need to check for 3 elements (since you are checking the current and next). However, if you write the function that I suggested, you don't need to do this since you would just return true after the loop ends.
    But when i =2,we can get "if(p[2]>p[3])…" or "if(p[2]<p[3])…",so i mean that we already checked "p[3]",why we need to do it again?

  15. #15
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,666
    You actually never check p[3] because p[3] is outside the valid range of array elements. The only reason the if (i==3) is necessary is because the implementation you were gifted is so ad hoc that there is no other way to determine the results. You were doing better on your own. You were also given fairly blunt hints in the thread, so I earnestly believe you have this.
    just_rookie likes this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Selecting pivot in sorted array.
    By infantheartlyje in forum General Discussions
    Replies: 4
    Last Post: 10-14-2011, 09:43 AM
  2. how delete 1th element of a sorted array
    By vicky_4040 in forum C Programming
    Replies: 4
    Last Post: 10-11-2009, 06:12 AM
  3. finding max/min in a sorted array
    By Crcullen3916 in forum C++ Programming
    Replies: 9
    Last Post: 09-23-2008, 02:18 AM
  4. Well and truly sorted
    By intrepid_is in forum C++ Programming
    Replies: 15
    Last Post: 11-15-2006, 03:06 AM
  5. Sorted List Example
    By chad101 in forum C++ Programming
    Replies: 3
    Last Post: 11-20-2005, 01:26 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21