What is the quickest way

This is a discussion on What is the quickest way within the C++ Programming forums, part of the General Programming Boards category; Hello; what would be the qickest way to determine if a vector of strings is in dorted order A-Z strings ...

  1. #1
    Registered User
    Join Date
    Sep 2005
    Posts
    85

    What is the quickest way

    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

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    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.
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Sep 2005
    Posts
    85
    Yes, but that will be order O(n) i was hoping to find something quicker if it exists

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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).
    My best code is written with the delete key.

  5. #5
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,794
    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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 10-17-2002, 10:09 PM
  2. Error: explicit type cast cannot convert 'void* to 'int*'
    By juschillin in forum C++ Programming
    Replies: 5
    Last Post: 09-04-2002, 09:19 AM
  3. Best game ever(because its the quickest and easiest)
    By Esparno in forum C++ Programming
    Replies: 4
    Last Post: 03-20-2002, 07:35 AM

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