読者です 読者をやめる 読者になる 読者になる

C++と色々

主にC++やプログラムに関する記事を投稿します。

選択ソート書いてみた

C++ アルゴリズム

普通のと、デバッグ用ストリーム出力ありのやつ

#include <algorithm>
#include <iterator>
#include <functional>
#include <utility>

template <typename Iterator>
void selection_sort(Iterator first, Iterator last)
{
  selection_sort(first, last, std::less<>{});
}

template <typename Iterator, typename Compare>
void selection_sort(Iterator first, Iterator last, Compare comp)
{
  for (auto i = first; i != last; ++i) {
    bool is_sorted = true;
    auto min = std::min_element(i, last, comp);
    if (min != i) {
      is_sorted = false;
    }
    std::iter_swap(i, min);
    if (is_sorted) {
      break;
    }
  }
}

template <typename Iterator, typename OStream>
void debug_selection_sort(Iterator first, Iterator last, OStream&& out)
{
  debug_selection_sort(first, last, std::forward<OStream>(out), std::less<>{});
}

template <typename Iterator, typename OStream, typename Compare>
void debug_selection_sort(Iterator first, Iterator last, OStream&& out, Compare comp)
{
  for (auto i = first; i != last; ++i) {
    bool is_sorted = true;
    using type = typename std::iterator_traits<Iterator>::value_type;
    std::copy(first, last, std::ostream_iterator<type>(out, ","));
    out << "\n";
    auto min = std::min_element(i, last, comp);
    if (min != i) {
      is_sorted = false;
    }
    std::iter_swap(i, min);
    if (is_sorted) {
      break;
    }
  }
}

#include <cassert>
#include <iostream>
#include <list>

int main() {
  std::list<int> v = {5, 1, 4, 3, 2};
  debug_selection_sort(std::begin(v), std::end(v), std::cout);

  std::cout << "\n";
  std::copy(std::begin(v), std::end(v), std::ostream_iterator<int>(std::cout, ","));
  assert(std::is_sorted(std::begin(v), std::end(v)));
}