Selection sort - loop stops too early

Question

I'm trying to write selection sort. Everything works but my algorithm is not looping through whole vector _item leaving my v_sorted too short. Elements are sorted properly.

sort.hpp

template<typename T>
std::vector<T> selection_sort(std::vector<T>);

sort.cpp

template<typename T>
std::vector<T> selection_sort(std::vector<T> _item) {
    std::vector<T> v_sorted;
    for(int i = 0; i < _item.size(); ++i) {
        T smallest = _item[0];
        for(auto const& j : _item) {
            if(j < smallest) {
                smallest = j;
            }
        }
        v_sorted.push_back(smallest);

        auto it = std::find(_item.begin(), _item.end(), smallest);
        if (it != _item.end()) {
            // to prevent moving all of items in vector
            // https://stackoverflow.com/a/15998752
            std::swap(*it, _item.back());
            _item.pop_back();
        }
    }
    return v_sorted;
}

template std::vector<int> selection_sort(std::vector<int> _item);

sort_tests.hpp

BOOST_AUTO_TEST_CASE(selection_sort_int)
{
    std::vector<int> v_unsorted = {3, 1, 2, 7, 6};
    std::vector<int> v_sorted = {1, 2, 3, 6, 7};
    auto v_test = exl::selection_sort(v_unsorted);
    BOOST_CHECK_EQUAL_COLLECTIONS(v_sorted.begin(), v_sorted.end(), 
                                  v_test.begin(), v_test.end());
}

This test is failing with Collections size mismatch: 5 != 3. Any test is failing with size mismatch. Loop is stopping (in this case) after three iterations. Thanks in advance for any clues.

If you're unsure, add `std::cout << "i = " << i << ", _item.size() = " << _item.size() << std::endl;` at the beginning of your loop. — molbdnilo, Oct 19 '17 at 11:22

score 1 · Accepted Answer · answered Oct 19 '17 at 11:24

1

The simultaneous effects of the for loop's ++i and the _item.pop_back() has the effect of incrementing twice, when you only wanted to increment once.

Change the for loop to a while loop:

while(!_item.empty())

Live Demo

answered Oct 19 '17 at 11:24

AndyG

39,700
8
109
143

That was it! Thank you very much! – EdwinKepler Oct 19 '17 at 11:38

Caleth · Answer 2 · 2017-10-19T12:05:17.443

1

You are re-implementing std::min_element, and you if you use it, you don't need to find the element again, you also don't want to change the size of _item whilst looping over it's size().

You can also sort in place, as follows:

template<typename T>
std::vector<T> selection_sort(std::vector<T> _item) {
    for(auto it = _item.begin(); it != _item.end(); ++it) {
        auto smallest = std::min_element(it, _item.end());
        std::iter_swap(it, smallest);
    }
    return _item;
}

edited Oct 19 '17 at 12:05

answered Oct 19 '17 at 11:29

Caleth

52,200
2
44
75

@SirGuy Oops, good catch. And I've now arrived at approximately [this example](http://en.cppreference.com/w/cpp/algorithm/iter_swap) – Caleth Oct 19 '17 at 12:05

Selection sort - loop stops too early

2 Answers2

Live Demo