2
\$\begingroup\$

I was wondering if this implementation of selection sort could be improved. Are there any things that I have done wrong?

template<typename Element>
void selection_sort(Element arr[], size_t size) {
    auto index_toSort = 0u;
    while (index_toSort < size) {
        auto index_smallest = index_toSort;
        for (auto index = index_toSort; index < size; ++index) {
            if (arr[index] < arr[index_smallest]) {
                index_smallest = index;
            }
        }
        std::swap(arr[index_toSort], arr[index_smallest]);
        ++index_toSort;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Seems fine to me as-is (though I'd probably rename index_toSort to index_to_sort for consistency/personal aesthetics). Of course, one could always generalize for different ordering and/or iterators, but those aspects seem out of scope for your sort implementations (at least to me). \$\endgroup\$ – hoffmale Nov 14 '17 at 12:48
  • 1
    \$\begingroup\$ @hoffmale, I disagree. The asker is the new generation of C++ programmers. We should try to teach them modern (or at least C++) ways first. Otherwise, there is no real reason to learn or use C++, as their code will be easily ported to other languages. They're getting worst of all worlds when using C way. Idioms are there for a reason. C way is very prideful way, because then programmers will need to reimplement everything to fit their ecosystem. That doesn't end well if they are not team of experts in the domain of their problem. Using them in general is not bad, but bad if better tool exists. \$\endgroup\$ – Incomputable Nov 14 '17 at 19:09
2
\$\begingroup\$

In all three of your examples you limit yourself to using arrays.

This is not very C++ like (even if you templatize the object). I would change the interface to use iterators. That way your sort can be applied to any container with a random access iterator.

template<typename I>
void selection_sort(I begin, I end) {
    std::size_t size = std::distance(begin, end);
\$\endgroup\$
  • \$\begingroup\$ Thank you for the advice. I will try in the future to use the C++ way. Should I stop using normal arrays? Are the iterators the way to go when writing such algorithms? Is there any speed difference? \$\endgroup\$ – puls99 Nov 14 '17 at 20:02
  • 1
    \$\begingroup\$ @puls99, usually compiler is able to understand what you mean, and will be able to generate good code in both cases. Identifying situations where it is not the case is quite hard in general. I would recommend sticking to C++ way. The way in the question is quite similar to C, or some ancient Java. There is a good chance that index based algorithms are prevalent in other languages, so you will learn them later. For now, it is better to learn iterator based algorithms. In the future (2020), it might be a time to move ranges. \$\endgroup\$ – Incomputable Nov 14 '17 at 20:35
  • \$\begingroup\$ @Incomputable Hello, I tried using the C++ way with iterators. Is it ok? At the moment I am learning new algorithms and I was wondering if is it ok to code like this or should I write them using both ways. The standard library is doing the job for me which is not necessarily good when learning how stuff works behind the scenes. Could you recommend me a book on the new C++? Thanks. \$\endgroup\$ – puls99 Nov 14 '17 at 21:01
  • 1
    \$\begingroup\$ @puls99, I believe you should try to implement all of them. I mean, getting feedback on each atomic step might be effective in cases where you have a tutor, but for this site I’d recommend more self-reflection and research. If we would be of size of Stackoverflow, may be we could’ve guided you step by step, but currently we have other matters to worry about. \$\endgroup\$ – Incomputable Nov 14 '17 at 21:08

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.