Hello;
what would be the qickest way to determine if a vector of strings is in dorted order
A-Z
strings will have all punctuation removed and be converted to uppercase
Printable View
Hello;
what would be the qickest way to determine if a vector of strings is in dorted order
A-Z
strings will have all punctuation removed and be converted to uppercase
Walk through the vector and make sure that each string is less in value to the string after it. If this rule applies all the way though the vector then you've verified ascending order.
Yes, but that will be order O(n) i was hoping to find something quicker if it exists
>Yes, but that will be order O(n) i was hoping to find something quicker if it exists
Good luck with that. Testing for sorted order is like printing the contents of any data structure, a correct algorithm has to visit every item, so the best you'll ever get is O(N).
The only way I can think of to get something faster in terms of checking might be to create a wrapper around the vector that contains the vector and a sorted boolean variable initialized to true. Each time you insert a value into the vector you would need to check the values around where you are doing the insert and validate whether the insert would affect the sorted status. Each time you insert a string at the end you check to make sure that it is greater than the string already at the end, each time you insert at the beginning you make sure it is less than the string already at the beginning of the vector, and each time you insert somewhere in the middle you make sure the string inserted is greater than the previous string and less than the next string. If these conditions are not met you set the sorted variable to false. Then, anytime you need to check if the vector is sorted, you call the wrapper's getSorted member function (or whatever) which returns the value of the sorted data member. This would result in a constant time check (O(1)) regardless of the number of elements in the vector with a small bit of extra overhead when performing insertions. Anytime you clear the vector's contents you reset sorted back to true.
Other than that, you must check each element in the vector like Prelude said which is of course always going to be an O(n) operation.