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'; 
}

• Incomputable: it seems like you dont know about std::less<>.