1
\$\begingroup\$

I wanted to practice using templates since I have no experience with them, so I implemented these sorting algorithms.

Selection Sort:

template<typename Container>
void selectionSort(Container& numbers)
{
    for (auto iter = std::begin(numbers), iterEnd = std::end(numbers); iter != iterEnd; ++iter)
    {
        auto minNum = minIndex(numbers, iter, iterEnd);

        std::swap(*iter, *minNum);
    }
}

template<typename Container, typename Iter>
Iter minIndex(const Container& numbers, Iter start, Iter end)
{
    Iter minIdx = start;
    auto minNum = *start;

    while (++start != end)
    {
        if (*start < minNum)
        {
            minNum = *start;
            minIdx = start;
        }
    }
    return minIdx;
}

Insertion Sort:

template<typename Container>
void insertionSort(Container& numbers)
{
    for (auto iter = std::begin(numbers) + 1, iterEnd = std::end(numbers); iter != iterEnd; ++iter)
    {
        if (*iter < *(iter-1))
        {
            resort(numbers, iter);
        }
    }
}
template<typename Container, typename Iter>
void resort(Container& numbers, Iter containerIter)
{
    auto temp = *containerIter;

    while (containerIter != std::begin(numbers) && temp < *(containerIter-1))
    {
        *containerIter = *(containerIter - 1);
        --containerIter;
    }

    *containerIter = temp;
}
\$\endgroup\$
  • \$\begingroup\$ Your includes are missing. Please add them to your code. \$\endgroup\$ – Zeta Jan 23 at 6:10
  • \$\begingroup\$ I don't see any question, just a statement along the lines of "I did this". That's great, but is there a more specific question regarding your implementation? \$\endgroup\$ – Juho Jan 24 at 12:47
  • \$\begingroup\$ @Juho Sorry, I guess I was just looking for opinions on whether my use of templates were correct, as well as just general critiques one may have for my implementations. \$\endgroup\$ – codewriter Jan 24 at 23:40
3
\$\begingroup\$

First tip: use more aggressive warnings, this way you would be warned by the compiler about passing unused parameters into functions, that is you would automatically made:

template<typename Iter>
Iter minIndex(Iter start, Iter end)

Another thing would be, to write your algorithms in similar way as the standard ones. That is avoid passing the reference to the container, but rather pass iterators into it. So your sort functions should look similarly to:

<typename InputIt>
void someSort (InputIt first, InputIt last)

This will e.g. allow you to sort specific parts of your container with no extra effort.

\$\endgroup\$
1
\$\begingroup\$

There is no need for minIndex, this functionality is already available in the standard. So you could do e.g.,:

template<typename Container>
void selectionSort(Container& numbers)
{
    for (auto it = std::begin(numbers); it != std::end(numbers); ++it)
    {
        std::iter_swap(it, std::min_element(it, v.end()));
    }
}

A similar comment holds for insertion sort, see this question and one of its answers.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.