Search code examples
c++vectorinsertion-sort

Insertion sort with a string vector

I am trying to sort a string vector using insertion sort.

This is my code:

void insertionsort(std::vector<std::string> &strings) 
{
    typedef std::vector<std::string>::size_type size_type;
    for(size_type i = 0;i < strings.size(); i++) 
    {
        std::string const tmp = strings[i];
        size_type j = i - 1;
        while(j >= 0 && tmp < strings[j]) //this is the problem
        {
            strings[j + 1]= strings[j];
            j--;

        }
        strings[j + 1]=tmp;
    }
}

It gives me the error:

comparison of unsigned expression >= 0 is always true

The function works fine if I use j > 0. But it completely ignores the first line of the string.

If for example i have:

2 line1
3 line2
4 line3
5 line4
1 line5

Then it gives me:

2 line1
1 line5
3 line2
4 line3
5 line4
Solution

  • vector<T>::size_type is by definition unsigned so j >= 0 can't be false. You should use vector<T>::difference_type.