### Sorting question

hi , so I have to see my the input is sorted or not.

here is my code.

 ``12345678910111213141516171819202122232425262728293031`` ``````#include using namespace std; bool isSorted(const int list[], int size); int main() { const int size = 5; int list[size]; for ( int i=0; i<5; i++) cin >> list[i]; isSorted(list,size); return 0; } bool isSorted(const int list[], int size) { for(int i=0; i<5; ++i) [ This is the part where I am messing up] { if ( list[i] > list[i+1]) { cout<<"This list is unsorted";} else cout << "The list is sorted" << endl; } return 0; } ``````
Last edited on
Two problems in isSorted().
Line 24: You're making an out of bounds reference to list when i is 4. Line 22 should be i<4.

The other problem is that you will do a cout everyu time you do a comparison. You have a couple of options: 1) Set a flag false before the loop. If any element is unsorted, set the flag true, then AFTER the loop test the flag and do the appropriate cout. 2) The other option is if you find an unsorted element, do the cout and return immediately. If you fall through the loop you know the list is sorted.
sorry dont understand your 2nd part ? I dont think we use that in our CS class. can you show me may

edit : Nvm we do use false just didnt know I saw it , let me try it and ill let you know
Last edited on
hahaha I got it thanks man! also One last Question that is I need to make it "Stop" entering numbers when I enter a negative number. So Like right now my limit is 5 but I need to make it so that I type in as many numbers as I like BUT as soon as I type a negative numbers the program stop accepting numbers and THEN tells me if the program is sorted or not. thanks
Last edited on
When I need to do an early exit, I like to use a function.
Something like this (not tested):
 ``12345678910111213`` ``````// Returns number of entries in list int get_list (int list[], int size) { int n; int i; for (i = 0; i < size; i++) { cin >> n; if (n < 0) return i; // Early exit list[i] = n; } return i; }``````
Last edited on
ok I tired that But when I type in a negative number the program just exits and doesnt say if its sorted or not ! what I want the program to do is tell is if its sorted after I put in a negative number ! so please let me know how to do that thanks!

Here is what I tried!

 ``123456789101112131415161718192021222324252627282930313233343536373839404142`` ``````#include using namespace std; bool isSorted(const int list[], int size); int main() { const int size = 5; int list[size]; int j; for ( int i=0; i> j; if ( j< 0) return i; } isSorted(list,size); return 0; } bool isSorted(const int list[], int size) { for(int i=0; i<4; i++) { if ( list[i] > list[i+1]) { cout<<"This list is unsorted"; return false; } } cout << "The list is sorted" << endl; return true; }``````
Last edited on
Lines 18-19: Yeah, your return statement exits main. What did you expect to happen? That is why I wrote a separate function.

Line 24: You want to pass the number of values collected, otherwise you're going to be comparing entries in your array that were never filled.

Line 31: You should specify the terminating condition as size-1, where size is the number of entries collected. You should probably call your argument something other than size to avoid confusion with the size of the array.

im sorry can you please show me in code ? what you are talking about ? Im really confused about what you are telling me to do. thanks
 ``123456789101112131415161718192021222324252627282930313233343536373839`` ``````#include using namespace std; bool isSorted(const int list[], int size); // Returns number of entries in list int get_list(int list[], int size) { int n; int i; for (i = 0; i < size; i++) { cin >> n; if (n < 0) return i; // Early exit list[i] = n; } return i; } int main() { const int size = 5; int list[size]; int n; // Number of entries in list n = get_list(list, size); isSorted(list, n); return 0; } bool isSorted(const int list[], int n) { for (int i = 0; i < n-1; i++) { if (list[i] > list[i + 1]) { cout << "This list is unsorted"; return false; } } cout << "The list is sorted" << endl; return true; }``````
Also there is std::is_sorted(). See http://www.cplusplus.com/reference/algorithm/is_sorted/
ok thanks guys , just wondering what exactly does line 25 "n = get_list(list, size);" do?
Last edited on
get_list() is a function call passing the array and the maximum number of numbers to get.
It returns how many numbers were actually entered and stores that value in n.
`bool isSorted(const int list[], int size);` This hints (screams really) that the function returns true or false if the list is sorted or not. It should not generate any output. That should happen in the main program.

To input numbers up to a limit, you should first distinguish between the size of the data and the capacity of the array.
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445`` ``````#include using namespace std; bool isSorted(const int list[], int size); int main() { const int capacity = 5; int list[capacity]; int j; int size; for (size=0; size < capacity; ++size) { cin >> j; if (j < 0) break; // exits the for loop list[size] = j; } if (isSorted(list, size)) { cout << "The list is sorted.\n"; } else { cout << "The list is unsorted.\n"; } // Or if you want to get fancy: cout << "The list is " << (isSorted(list, size) ? "" : "un") << "sorted.\n"; return 0; } bool isSorted(const int list[], int size) { for (int i = 0; i < size-1; i++) { if (list[i] > list[i + 1]) { return false; } } return true; }``````

when I try 5 5 5 2 -1 in dhayden code I get unsorted ? ? while I am supposed to get sorted!
Change the > to <:
 ``12345678910`` ``````bool isSorted(const int list[], int size) { for (int i = 0; i < size-1; i++) { if (list[i] < list[i + 1]) { // Note < return false; } } return true; }``````
 when I try 5 5 5 2 -1 in dhayden code I get unsorted ? ? while I am supposed to get sorted!
My code detects if it's sorted in increasing order. If you mean to detect whether it's sorted in either increasing or decreasing order then it needs something different. It can still be done in one pass but the code is a little more complicated.
Detecting both increasing and decreasing:

 ``12345678910111213141516`` ``````bool isSorted(const int list[], int size) { int flags{0}; constexpr int Increasing=1, Decreasing=2; // bits in flags for (int i = 0; i < size-1; i++) { if (list[i] > list[i + 1]) { flags |= Decreasing; // the list decreases from this one to the next } else if (list[i] < list[i+1]) { flags |= Increasing; // the list increases from this one to the next } } // It's sorted if it's increasing, or decreasing, or neither. But if // It's both increasing AND decreasing, then it's not sorted. return flags != (Increasing | Decreasing); }``````

 ``` dhayden@DHAYDENHTZK3M2 ~/tmp \$ ./foo 1 2 3 4 5 The list is sorted. dhayden@DHAYDENHTZK3M2 ~/tmp \$ ./foo 5 4 3 2 1 The list is sorted. dhayden@DHAYDENHTZK3M2 ~/tmp \$ ./foo 5 5 3 3 3 The list is sorted. dhayden@DHAYDENHTZK3M2 ~/tmp \$ ./foo 4 4 4 -1 The list is sorted. dhayden@DHAYDENHTZK3M2 ~/tmp \$ ./foo 3 4 3 2 1 The list is unsorted.```