Selection Sort implementation using modern C++

Question

I have written this code for Selection sort. I want to use more C++11, C++14 or C++17. Please sugest some better alternatives.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

template <typename InputItr>
void selectionSort(InputItr first, InputItr last)
{
  while(first != last)
  {
    InputItr min = std::min_element(first, last);
    if(*min < *first)
    {
      std::swap(*min, *first);
    }
    ++first;
  }
}

template <typename Itr>
void print(Itr first, Itr last)
{
  while(first != last)
  {
    std::cout << *first <<" ";
    ++first;
  }
  std::cout << "\n";
}

int main()
{
  std::vector<int> v({5, 3, 12, 2, 8});
  std::cout << "Original Array :";
  print(v.begin(), v.end());
  selectionSort(v.begin(), v.end());
  std::cout <<"Sorted Array :";
  print(v.begin(), v.end());
  std::cout << '\n';

  std::vector<char> c({'t', 'q', 'a', 'r', 'p'});
  std::cout << "Original Array :";
  print(c.begin(), c.end());
  selectionSort(c.begin(), c.end());
  std::cout <<"Sorted Array :";
  print(c.begin(), c.end());
  std::cout << '\n';

  std::vector<std::string> str({"code", "live", "love", "sing", "create"});
  std::cout << "Original Array :";
  print(str.begin(), str.end());
  selectionSort(str.begin(), str.end());
  std::cout <<"Sorted Array :";
  print(str.begin(), str.end());
  std::cout << '\n';

}

Answer 1

1. InputItr doesn't appropriately describe the iterator requirement of your selection sort, which multi-passes the range. Consider naming the type after forward iterator.

2. Allow for custom overloads of swap by calling swap in an unqualified context.

       using std::swap;
       swap(*min, *first);
   

   which is just std::iter_swap

       std::iter_swap(min, first);
   

3. You don't need to conditionally check if min is smaller than first. Just swap.

     for (; first != last; ++first) {
       auto min = std::min_element(first, last);
       std::iter_swap(min, first);
     } 
   

4. Your print function is just a reimplementation of std::copy.

5. Make sure you include everything (missing <string>).

6. Assert liberally. See the CPPCoreGuidelines.

Answer 2

I would add a predicate function, so one can perform custom comparisons. Then you can define a lambda function at the selectionSort call. You can also change the print function to use range based loop. Here are these two implemented.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

template <typename InputItr, class Compare>
void selectionSort(InputItr first, InputItr last, Compare &&comp)
{
  while(first != last)
  {
    InputItr min = std::min_element(first, last, std::forward<Compare> ( comp) );
    if( comp( *min , *first ))
    {
      std::iter_swap(*min, *first);
    }
    ++first;
  }
}
// Specific to less than comparator
template <typename InputItr>
void lessThanSelectionSort(InputItr first, InputItr last)
{
  selectionSort( first, last, [](const auto &a, const auto &b ){ return a<b; } );
}

template < class T >
void print( const T& a)
{
  for ( const auto&v: a ) std::cout << v << ' ';
  std::cout << '\n';
}

int main()
{
  std::vector<int> v({5, 3, 12, 2, 8});
  auto v2 = v;
  std::cout << "Original Array :";
  print( v );
  lessThanSelectionSort(v.begin(), v.end());
  std::cout <<"Sorted Array :";
  print (v );

  selectionSort( v.begin(), v.end(), [](const auto &a, const auto &b){ return a>b ; } );
  std::cout <<"Descending :";
  print ( v );
  std::cout << '\n';



  std::vector<char> c({'t', 'q', 'a', 'r', 'p'});
  std::cout << "Original Array :";
  print( c );
  lessThanSelectionSort(c.begin(), c.end());
  std::cout <<"Sorted Array :";
  print( c );
  selectionSort( c.begin(), c.end(), [](const auto &a, const auto &b){ return a>b ; } );
  std::cout <<"Descending :";
  print ( c );
  std::cout << '\n';

  std::vector<std::string> str({"code", "live", "love", "sing", "create"});

  std::cout << "Original Array :";
  print( str );
  lessThanSelectionSort(str.begin(), str.end());
  std::cout <<"Sorted Array :";
  print( str );
  selectionSort( str.begin(), str.end(), [](const auto &a, const auto &b){ return a>b ; } );
  std::cout <<"Descending :";
  print ( str );
  std::cout << '\n';  
}