Search code examples
stringsortingstdbubble-sort

Is it possible to sort a vector of string with std::sort(), based on a complex criteria?

I need to sort a std::vector<std::wstring> which contains folder names, in a such manner that the parent folder is always located after all its children, e.g:

C:\Main\App\QtGraphicalEffects\private
C:\Main\App\QtGraphicalEffects
C:\Main\App\Qt\labs\platform
C:\Main\App\Qt\labs
C:\Main\App\Qt
C:\Main\App
C:\Main\

To reach a such sorting I may use a Bubble Sort algorithm, as the following one:

void BubbleSortDirs(std::vector<std::wstring>& dirs)
{
    bool swapped = false;

    do
    {
        swapped = false;

        for (std::size_t i = 0; i < dirs.size() - 1; ++i)
            // swap positions if first dir is entirely contained in the second
            if (dirs[i] != dirs[i + 1] && dirs[i + 1].find(dirs[i]) == 0)
            {
                std::swap(dirs[i], dirs[i + 1]);
                swapped = true;
            }
    }
    while (swapped);
}

This code works well, but I feel that a better solution should exist. So I tried to use the std::sort function in order to optimize my sorting, at least to provide a more elegant solution.

I tried the following implementation:

bool SortDirs(const std::wstring& first, const std::wstring& second)
{
    // swap positions if first dir is entirely contained in the second
    return (first == second || first.find(second) == 0);
}

...

std::sort(dirs.begin(), dirs.end(), SortDirs);

I expected that std::sort() would provide the same result as the BubbleSortDirs() function, but it wasn't the case and the result failed in several locations. At this point I strongly suspect that std::sort() isn't adapted for a complex sorting criteria like the one I'm trying to apply.

So my questions are:

  • What is the reason why my call to std::sort doesn't provide the expected result?
  • Is there a way to achieve the above described sorting using the std::sort() function?
  • If yes, what am I doing wrong?
  • If no, is the above BubbleSortDirs() function the best way to achieve a such sorting, or does it exist something better?
Solution

  • I finally resolved my issue this way:

    std::sort(dirs.rbegin(), dirs.rend());