Selection Sort for Linked List and Vectors Using Iterators

[lin0524]

I have to write a generic selection sort that will work with single linked lists, double linked lists, and vectors.

It receives is a begin iterator (first valid element), and an end iterator (after the last valid element). The selection sort should start at the first element, look through the list for the smallest element and swap it with the first. Then move on to the second element and swap it with the second smallest element...and on going.

After i attempted this I received errors at the declarations of both for loops. At the first loop the errors were: "Invalid operands to binary expression (List::iterator and List::iterator)" "Calling a private constructor of class 'std::_1::_wrap_iter; "Invalid operands to binary expression ('DList::iterator and DList ::iterator)

The error at the second for loop was: "Invalid operands to binary expression ('std::_1::wrap_iter' and 'typename_wrap_iter::difference_type'(aka'long'))"

template <class Iter>
void selectionSort (Iter begin, Iter end){

for (Iter k=0; k!=last; ++k){
Iter minidx=k;
bool sorted = true;

for (Iter i = k+1; i< last-k; ++i){
    if (*i < *minidx) minidx =i;
}

if (minidx!=k){
    Iter tmp = k;
    *k = *minidx;
    *minidx = *tmp;
    sorted = false;
}

if (sorted) break;
}

}

[ne555]

Learn to indent

Make sure that your code does reproduce your problem.
¿what's `last'? ¿why you don't use `end'?

The error comes because of the operations that you try to perform on linked list iterators. They are not random access iterators and so you can't increase them by `n', can't go back and makes no sense the `less than' comparison.

Your algorithm is incorrect. You can't affirm that the container is sorted just because one element was in the correct position.


By the way
http://www.cplusplus.com/reference/algorithm/min_element/
http://www.cplusplus.com/reference/algorithm/iter_swap/
if you cannot use them, at least create a replacement for them.