String vector sorting

[salmanmanekia]

I havent used sorting and alogorithms much and am Ok with vectors. Recently i faced an interesting question and want your suggestions with how to solve it. So, below is my question.

Q, I have been given 4 character strings in a vector and have to arrange those in a particular order depending on what those characters are. So, that the last character of any string should match with the first character of any other string and the last character of this string should be matched with the first character of any other string and this way i have to create a longest possible string.

For eg if i have a string vector like "ABCD" "TGHI" "DADC" "IYUR" "CXYT" so it would be arrange like "ABCD"then there would be the third string"DADC" then there would be the fifth string"CXYT" and so on So, the result will be "ABCD""DADC""CXYT""TGHI""IYUR".

Now,i was wondering if it would be a good idea to check each string with other string if it is 'compatible' according to the above rules.. so if i have 5 strings in the vector then i would have 5+4+3+2+1 possiblties and if for eg i have 20 strings then it would increase alot, so is this a good idea or is there any other good efficient solution to this... Thanks alot and hope (most of) you understand.

[Azagaros]

Have we tried the #including <algorithms> the c++ standard library. In there you should find sort routines of various kinds. You might find an example or two for the sort algorithms.

For your exact pattern, it might be better for you to sort as you build your list with out having a sorting algorithm. Your pattern would either be based on a check-sum or something similar to a cipher algorithm. The result sort pattern isn't based on anything normal that standard string matching would accomplish. Check-sum might be as simple as adding the characters up and dividing by the length of the string. Doing this you might end up with "DADC" being less than "CXYT". In other words the average of the sum of characters would specify where in the sort list it might land.

the code might look like this:

#include <string>
#include <vector>
#include <algoritm>

bool ChecksumSort(const std::string& stringOne, const std::string& stringTwo)
{
       int ValueOne = 0;
       int ValueTwo = 0;
       int index = 0;

       for(index = 0; index < stringOne.length(); index++)
       {
             ValueOne+=(int)stringOne[index];
       }
       ValueOne = ValueOne / stringOne.length();

       for(index = 0; index < stringTwo.lenght(); index++)
       {
             ValueTwo+=(int)stringTwo[index];
       }
       ValueTwo = ValueTwo / stringTwo.length();

       return ValueOne < ValueTwo;       
}

int main()
{
       std::vector<std::string> myList;
       vector<string>::Iterator myIterator;

       myList.push_back("ABCD");
       myList.push_back("TGHI");
       myList.push_back("DADC");
       myList.push_back("IYUR");
       myList.push_back("CXYT");

       sort(myList.begin(), myList.end(), ChecksumSort);

       for(myItorator = myList.begin(); myItorator != myList.end(); myItorator++)
       {
             std::cout << myList[myItorator] << std::endl;
       }
       return 0;
}
 

if I read your description a little better when I wasn't falling asleep it might look something like this:

int main()
{
       std::vector<std::string> myInQuad;
       std::vector<std::string> myOutQuad;

       // do my filling of the inQuad vectors...

       std::vector<std::string>::iterator nScanPos;
       bool done = false;

       // push the first one over so we have a working output.
       myOutQuad.push_back( myInQuad[ myInQuad.begin() ] );
       std::string workString;
       char scanChar;

       // erase the first one so we don't find it in the scan of the remaining ones.
       myInQuad.erase( myInQuad.begin() );

       while(!myInQuad.empty())
       {
             workString = myOutQuad[ myOutQuad.end() ];
             // get the last character in the string.
             scanChar = workString[ workString.length() -1 ];
             for(nScanPos = myInQuad.begin(); nScanPos !=  myInQuad.end(); nScanPos++)
             {
                    workString = myInQuad[nScanPos];
                    if(workString[0] == scanChar)
                    {
                           // push the found one on to the out quads...
                           myOutQuad.push_back(workString);
                          // erase the found one from the search queue
                           myInQuad.erase(nScanPos);
                           // break out of the loop this is assuming that we only have one or the first one
                           break;
                    }
              } // end of for loop
        }  // end of while loop.

        for(nScanPos = myOutQuad.begin(); nScanPos != myOutQuad.end(); nScanPos++)
        {
               std::cout << myOutQuad[nScanPos] << std::endl;
         }
         return 0;
}