2
\$\begingroup\$

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

}
\$\endgroup\$

2 Answers 2

3
\$\begingroup\$
  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.

\$\endgroup\$
1
\$\begingroup\$

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';  
}
\$\endgroup\$
1
  • \$\begingroup\$ it seems like you dont know about std::less<>. \$\endgroup\$ Aug 28, 2017 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.