How to write a generic selection sort?

[stereoMatching]

Below is my code

template<typename iterator>
void selSort(iterator begin, iterator end)
{
  iterator minIt = begin;  
  iterator it2 = begin + 1;   
  for(iterator it = begin; it != end; ++it)
  {
    minIt = it;
    for(; it2 != end; ++it2)
    {
      if(*it2 < *minIt)
        *minIt = *it2;  //line X
    }
    std::swap(it2, minIt);
  }
}

i am reading the book--"The C++ Standard Library -
A Tutorial And Reference (1999)"(haven't finished it yet)
I quite wonder how could the std::sort is possible?
At line X, befoure I overwrite the value of *it2 to *minIt
I have to save the value of *minIt
But I don't know how to declare a variable to save the value
of *minIt, do you have any ideas to solve this?

Thanks a lot

[ne555]

Why do you want to save the value of *minIt?
I think that you need to do std::swap( *minIt, *it2 );. However you better work with iterators as long as you can, that's the copy of objects and might be costly.

[stereoMatching]

thanks, ne555, I solved my problem

template<typename iterator>
void selSort(iterator begin, iterator end)
{
  iterator minIt;  
  iterator it2;
  for(iterator it = begin; it != end; ++it)
  {
    
    minIt = it;
    for(it2 = it + 1; it2 != end; ++it2)
    {
      if(*it2 < *minIt)
        Swap(*it2, *minIt);
    }   
  }
}

[ne555]

for(it2 = it + 1; it2 != end; ++it2)
    {
      if(*it2 < *minIt)
         minIt = it2;
    }   
    std::swap(*it, *minIt);

So you will have just n copies of objects.
Try to use auxiliar functions.

template<typename iterator>
void selSort(iterator begin, iterator end){
  for( ; begin != end; begin++){
    iterator minIt = std::min_element(begin, end);
    std::swap( *minIt, *begin);
  }
}

Edit:
it2 = it + 1 Don't do that, not all iterators support adding an integer. So it wouldn't compile if you try to use, by instance, list::iterator

[stereoMatching]

thanks, I forget the restriction of iterator

  iterator minIt;
  iterator it2;  
  
  for(iterator it = begin; it != end; ++it)
  {
    minIt = it;
    it2 = it;
    ++it2;
    for(; it2 != end; ++it2)
    {
      if(*it2 < *minIt)
         minIt = it2;
    }       
    Swap(*it, *minIt);
  }

template<typename T>
inline void Swap(T& src1, T& src2)
{
  T temp(src1);  
  src1 = src2;
  src2 = temp;
}

PS:I try not to use the algorithm of stl to implement selSort
I want to realize how to implement something similar to stl
Because stl are quite cool for me
I hope someday I could design something like the way stl did
Still have a long way to go...

[jsmith]

But by writing your own Swap() method you reduce the generality of your sort function.

It would be best to do this:

template< typename Iter >
void selection_sort( Iter first, Iter last )
{
    using std::swap;

    // ...

    swap( *it, *minIt );
}

In this way, you allow the user to implement their own swap function for their type, and if they don't provide one, the default std::swap gets used instead.

Your way, the user is sorta forced to use your Swap function.

Also, for even more generality, you could provide an overload that allows the user to specify a comparator.

template< typename Iter, typename Compare >
void selection_sort( Iter first, Iter last, Compare comp )
{
    using std::swap;

    // ...
    if( comp( *it2, *minIt ) )
        swap( *it2, *minIt );
    // ...
}

[stereoMatching]

Thanks a lot
I study C++ because I need some basis about it before I study SystemC
I never thought C++ would be so interesting